快照分析法解决树形字典数据引用更新效率问题
背景
在实际业务中经常会用到树形的字典数据，如下所示我们称之为abc树，“a”和“b”是非叶子节点，“c”为叶子节点：
-a
--b
----c
，相应的业务数据会引用到具体的数据条目，如“a”，或者直接引用到“a”的下级数据条目“b”或“c”，但实际业务中往往会控制应用只能引用叶子节点，此时只能选择引用”c”。
约束业务只能引用叶子节点，这样的规则很正常，如选择收货地址时要求用户选择到最小行政区划，但是，依然存在更加复杂的情况，有些业务不仅约束引用只能指向叶子节点，且叶子节点还是不稳定的，其下可以新增其他节点，同时约定新增的第一个节点在意义能够自然取代上级节点，我们称之为“降级表达”，这种要求带有明显的具体业务特性，但确实存在，如预算里的科目。
回到abc树，如果该树形字典数据不是稳定的，c下再新增d作为其下第一个子节点，并在意义上取代c，这样，c就变成了非叶子节点，导致已经引用c的业务数据违背了非叶子节点不可被引用的约束，因此，要使业务数据对c的引用改为d的引用。
目前的方案
更新引用
“更新引用”是解决该问题的最直接的方案，该方案首先查找所有引用c的业务数据，然后将引用更新为d的引用，但这个代价太大，非叶子节点下只要新增一个节点，就会查询海量数据，甚至更新海量数据，数据库IO开销太大。
交换引用
聪明的程序员发明了“交换引用”，这是个很好的办法。依然以abc树为例，其中大写字母为字典数据的标识即引用，小写字母为字典数据的文本。
对树
-A a
--B b
---C c
在c下新增节点d，希望得到
-A a
--B b
---C c
----D d
，交换引用的办法是使C c和D d的标识互换，使之成为：
-A a
--B b
---D c
----C d
这样先前业务数据对c的引用C就自然指向d，不需要更新任何业务数据，代价相当小。
然而，交换引用存在一定的局限性。
复杂的字典数据具有访问控制能力，简单来说，一条初创的数据默认是隔离的，即私有数据，除了创建人外其他人无法访问，但创建人可以将该条数据共享出去，一旦共享，其他人也可访问。
如果我们赋予该abc树形字典访问控制能力，很可能出现a、b、c已经被共享出去，新增的d属于私有数据，此时是无法交换的，一旦交换过来就使业务数据引用C d，而此时,d是除了创建人外其他人无法访问的，又会违背访问控制约束。因此，交换引用对整棵字典数据都是共享的或都是私有的再或者父节点是私有的场景是行之有效的，但迫于其局限性，又不得不配合更新引用的方法一起解决问题。
快照分析法
在对目前的方案研究的基础上，重新回归分析问题的本质：问题很简单，就是历史数据持有的其他数据的引用发生变化，要使历史数据得到最新的引用，因此，“更新引用”的方案是正面解决问题，但是更新操作就像一场正面战场的战役，场面确实很悲壮。
快照分析法并不正面更新引用，它通过记录树形字典数据的创建过程，通过分析历史过程，能找到任何字典数据的历史引用。
另注，本文描述的方法是在原理级别上描述，并非最终的实现，最终实现可以再进行优化。
概念
首先统一一下概念：数据条目、快照条目、数据实体和新增快照。
数据条目：具体的字典数据，强调数据，如文本。
快照条目：快照条目是对新建动作做一记录，具有时间属性，是某时间下的字典数据的具体数据节点，具有确定层次，并指向具体的数据条目。和数据条目是1对1的关系。
数据实体：数据实体是数据字典的数据对象，其意义稳定，但外观和位置是易变的，在不同的时期可能由不同的快照条目来表达。在任何时间点，数据实体和数据条目都是1对1的关系，但从历史来看数据实体可能由不同快照条目来表达，所以数据实体和快照条目是“神”和“形”的关系。
新增快照：新建一个数据条目时，会自动新建一个数据实体、一条快照条目，快照条目指向数据条目，并说明其代表的数据实体。如果正好在叶子节点下新增快照条目，该叶子节点所代表的“神”（数据实体）将被该新“形”（长子快照条目）所代表，这个新建快照条目以及长子快照条目代表其父快照条目的数据实体的过程会形成记录，这些记录我们称之为新增快照，通过快照分析我们能够快速得到一个数据实体（“神”）在任何历史时期被哪个快照条目（“形”）所代表，从而找出具体数据，也能快速提出当前最新的树形。
因此，我们看到的数据字典树其实是由指定时间下的快照条目组成的树形，创建一个数据条目其实就是在创建一个数据实体，一个快照条目。
快照的创建
注：该处定义的实体并不代表最终的数据库表，只是为了方便描述快照的形成过程，稍加优化改造便能定义出最终的数据库表。
定义数据条目实体DataItem，目前只定义文本text信息，当然也可有其他信息：
id(标识) text(文本)
首先定义数据实体的实体DataEntry，其下只有id属性:
id(标识)
新增快照的实体Snapshot：
id(标识) item(数据条目id) parent(父条目id) entry(数据实体id) timestamp(时间戳)
创建一个数据条目时要遵循这样的逻辑：
begin；
声明 parentSnapshotItem = 父快照条目；
声明 newEntryId = 随机生成新的数据实体的id;
newEntryId插入DataEntry；
声明 itemId = 随机生成新的数据条目的id;
itemId插入DataItem；
声明timestamp = 新时间戳；
if(新建的是长子数据条目)
{
//新建item0，拷贝父条目parent和数据条目id，并使其指向最新的数据实体
声明快照数据条目item0;
item0.id= 随机生成id；
item0.item = parentSnapshotItem.item.id;
item0.parent = parentSnapshotItem.parent;
item0.entry=newEntryId;
item0.timestamp = timestamp;
//新建item1,指向新数据条目,parent为新item0，并指向父条目的数据实体
声明快照数据条目item1；
item1.id= 随机生成id；
item1.item = item.id;
item1.parent = item0.id;
item1.entry=parentSnapshotItem.entry;
item1.timestamp = timestamp;
}
else
{
略
}
快照分析
利用快照的最终目的是为避免更新，在应用数据字典时定位合适的数据版本。
我们对两种重要场景进行分析，一是如何获取最新的字典树，二是业务数据持有一个快照条目id后，后期如何获取其对应的当时数据信息，又如何获取最新的数据信息。
1、获取最新的字典树
查询Snapshot，找到parent为null的条目，此为第一层节点，如果有item属性相同（指向同一数据条目）的记录，则取时间戳最大者；
以第一层节点的id为条件，匹配parent，查找第二层次节点，同样，如果有item属性相同的记录，则取时间戳最大者；
以此类推。
获取当前字典树时，有一定的查询损耗，极端的情况下，如果每个非叶子节点都经过了“降级表达”的操作，此时，除了根节点的每个非叶子节点都存在两条指向相同数据条目即item相同的快照条目，需要比较这两条条目的时间戳，取最大的那个条目。
2、业务根据引用获取相应的数据版本
具体业务通过字典树可以拿到具体的快照条目的id，并持有在自己的业务数据中。
通过该id可以获取其指向的当时的条目信息，如果要获取当前的信息，只需获取该条目指向的数据实体，根据数据实体查找时间戳最大的记录。
快照的应用
以一棵无任何数据条目的数据字典树为例，如
-a
--b
---c
树，从无到c的创建过程演绎快照创建逻辑和分析逻辑的应用。
场景1:2014年创建a
此时创建数据条目a的数据实体A，并创建数据实体以及数据条目如下：
DataItem实体
id text
pa a
DataEntry实体
id
A
Snapshot实体
id item parent entry timestamp
A’ pa null A 2014******
通过快照分析逻辑，此时，字典的树形外观：
-a
以快照条目id来表达：
-A’
场景2：2015年在a下创建b
此时，除了老数据记录外，会新增如下记录：
DataItem实体
id text
pb b
DataEntry实体
id
B
Snapshot实体
id item parent entry timestamp
B’ pa null B 2015******
A’’ pb B’ A 2015******
通过快照分析逻辑，此时，字典的树形外观：
-a
--b
以快照条目id来表达：
-B’
--A’’
场景3：2016年在b下创建c
此时，除了老数据记录外，会新增如下记录：
DataItem实体
id text
pc c
DataEntry实体
id
C
Snapshot实体
id item parent entry timestamp
C’ pb B’ C 2016******
A’’’ pc C’ A 2016******
通过快照分析逻辑，此时，字典的树形外观：
-a
--b
---c
以快照条目id来表达：
-B’
--C’
---A’’’
总结
“更新引用”的方案正面解决了父节点“降级表达”的问题，但随着业务数据的积累，更新操作将会陷入海量更新的泥沼。“引用交换”在一定场景是非常高效的，但无法应用在某些访问控制的场景下，具有一定局限性。
快照分析法不用更新海量的业务数据，适合所有访问控制场景。是一种以一定的空间和一定的查询分析时间分摊“更新引用”带来的损耗的中和方案。
