关于算法:详解记录历史的可持久化数据结构

文本编辑器里的 “undo” 和 “redo”，数据库系统的 MVCC，git 的历史记录，mac 的
Time Machine，等等性能，他们都有一个共同点，就是记录历史。这个性能依赖一种数据结
构：长久化数据结构 (Persistent data structure)。长久化数据结构记录所有历史版本，
你能够读取任意版本的数据。

原文地址

“ 长久化(persistence)” 是指领有查问数据历史版本的能力，它有以下 4 个级别：

半长久化 (Partial Persistance) – 能够读数据结构过来任意版本，只能在最新版本
写。
全长久化 (Full Persistance) – 能够读数据结构过来任意版本，能够在数据结构任意
版本写。
可合并长久化 (Confluent Persistent) – 不光能够在任何版本上读写，还能够将两个版
本合并以创立一个新的版本。
函数式长久化 (Functional Persistance) – 函数式编程中实现的长久化数据结构，对
象都是只读的，任意批改都是创立一个新的节点，而不是在旧节点上批改。参考
Puerly functional data structure。

以上四种长久化是逐渐加强的，函数式长久化蕴含可合并长久化，合并长久化蕴含全长久化，
全长久化蕴含半长久化。函数式长久化蕴含合并长久化是因为在函数式长久化中咱们只限度
了实现形式。如果在合并长久化中咱们不容许合并，那么它就是全长久化。在全长久化中限
制只能在最新版本上写，它就变成了半长久化。

4 种长久化示意图如下所示。

半长久化就像是 undo 和 redo，它是线性的记录历史。全长久化就像是 emacs 上的
undo-tree，它记录了分支。合并长久化就像是 gitflow，它容许分支与合并操作。

gitflow:

先看半长久化链表的实现，很容易扩大出其余数据结构半长久化版本。

失常链表节点蕴含三个成员：(val, next, prev)，val 示意节点值，next 指向链表下一
个节点，prev 指向链表上一个节点。要实现半长久化，还须要一个区域 mods，用来保留
节点的批改历史。

(1) 写操作, new_version = write(node, variable, value)

半长久化写操作参数为变量，目标值，返回版本号。

如果节点 n 的 mods 区域没有满，还能包容新的批改历史，就把批改历史间接写到
mods 区域。

如果节点 n 曾经的 mods 区域曾经写满了，再也不能包容新的批改历史了：

新建节点 n'。
将节点 n 的最新值 (包含 val, next, prev) 复制到 n'。
对所有 n 指向的节点 x (x=n->next)，批改反向指针指向 n'
(x->prev=n' )。
对于所有领有指针指向 n 的节点 x (x->next=n )，递归的调用
write(x, next, n')。

(2) 读操作，read(node, variable, version)

读操作 read(node, var, v) 查问 mods 记录，找到版本最大的记录版本 $w $ 使得
$w\leq v $，版本批改记录 $w $ 中的值就是要查问的值。

以上述链表为例，要批改第二个节点 v1=write(node2, val, 20)，只须要增加 mods 批改历史，如
图所示。

再多加几次批改:

v2=write(node2,val,33)
v3=write(node2,val,50)    
v4=write(node2,val,21)

构造如下图，mods 区域曾经写满了。

记没批改过的初始值为 v0。
要查问这个链表 v3 版本，从根节点开始：(val,v0)=1,(next,v0)=node2；node2
节点查问到满足 $\leq v3 $ 的版本 (val,v3)=50,(next,v0)=node3,(prev,v0)=node1 ;
node3 节点查问到满足 $\leq v3 $ 的版本
(val,v0)=3,(next,v0)=nullptr,(prev,v0)=node2。得悉链表在版本 v3 为
<1,50,3>。

再批改 node2 的值 v5=write(node2,val,200)，此时 mods 曾经满了，须要新建节
点 new_node2：

此时查问链表版本 v5，从根节点开始：(val,v0)=1,(next,v5)=new_node2 ; new\_node2
节点 (val,v0)=200,(next,v0)=node3，node3 节点 (val,v0)=3,(next,v0)=nullptr
。得悉链表版本 v5 为 <1,200,3>。

不难看出如果 write() 办法要递归批改多处，均批改实现后返回版本的最大值。

应用相似的办法，能够实现半长久化二叉树等数据结构。根本数据结构都能够应用节点和
指针来示意，稍作变动就能够半长久化简直所有根本数据结构。

链表、树、图能够形象为 Pointer Machine。咱们扩大 Pointer Machine，将其变成半持
久化数据结构，这样就相当于扩大了任意根底数据结构。

只思考入度确定的 Pointer Machine，设入度为 $p $ , 如上图所示，每个节点有三类成员。

只读的数据成员，共 $d $ 个数据成员。这是原有数据结构原本就存在的，数据成员包
括数值和指针。
可写的反向指针区域 (back pointers)。这些反向指针能通知咱们哪些节点的数据成员
指向了以后节点。入度是 $p $ 所以反向指针成员数量为 $p $。
可写的批改历史区域 (mods)。保留对节点数据成员的批改，内容构造是
(field,version)=value。留神批改反向指针并不需记录 mods。

实现任意节点的读写操作如下：

read(node, field, version) – 在节点的批改记录区 node.mods 查找批改 field
成员的最大版本 $w $，使得 $w\leq version $。如果没找到，那么只读的数据成员
区域的 field 成员就是以后值。
write(node, field, value) – 如果 node.mods 没满，就向其中增加一个记录
(field,version)=value。如果 node.mods 满了：
- [新建节点] node'
- [设置最新值] 将旧节点的数据成员区域 (数据和指针) 的最新值复制到 node' 的数据成员区域。
- [批改其余节点的反向指针] 任意 node 指向的节点 x，批改 x 的反向指针指向新节点 node'。
- [递归批改其余节点的指针成员] 任意指向 node 的节点 x , 递归调用
  write(x, pointer_to_node, node') 使得最新版本的指针指向新节点。

演示半长久化二叉树实现如下图。

咱们只思考度数是指定常数的数据结构。节点入度数为 $p $ , 令节点的 mods 的最大记
录数量为 $2p $。

读操作 read(node, field, version) 是很快的，只须要读取 node.mods，$O(1) $。
写操作 write(node, field, value) 有两种状况，如果节点没满，间接写入一个批改日
志，复杂度是 $O(1) $；如果节点满了，可能会递归调用 write() 批改指针：

$$
cost(n) = c + \sum_{all\ node\ x\ point\ to\ n}\left(cost(x)\right)
$$

其中 $c $ 示意新建一个节点并复制旧节点数据，批改反向指针的 $O(1) $ 操作。递归步骤
是很贵的，但只有节点满的时候才会执行递归操作，而后节点又会变空，直到节点变满之前
都不会引起递归操作。均匀下来 write() 耗时很少。咱们应用摊还剖析
(amortize analysis) 来计算写操作的事件复杂度。

设势能函数 $\phi $，每次操作的摊还代价等于这次操作的理论代价加上此操作引起的势
能变动：

$$
amortized\_cost(n) = cost(n) + \Delta\phi
$$

势能函数为：

$$
\phi = c\times (mods\ number)
$$

节点之前是满的，起初空了，所以势能变动为 $-2cp $。

$$
amortized\_cost(n) \leq c + c – 2cp + p \times amortized\_cost(x)
$$

对于节点 $x $，公式中第二个 $c $ 是找到 mods 对应地位并增加个记录的次数，所以
造成势能减少 $c $。

将左边开展容易的出均摊复杂度是 $O(1) $。
更具体的剖析见此文档。

在半长久化数据结构中，版本是线性的、全序的，版本号应用数字就能够，数字大小体现了
版本的新旧关系。全长久化能够批改任意版本，它的版本变动造成树形构造，版本是个偏序
关系，并不是任意两个版本都能够比拟的。如下图，版本 $a $ 和版本 $b $ 的关系是 $a<b $
，但版本 $b $ 和版本 $d $ 是不可比拟的。因而版本应用数字大小来代表就不适合了，全持
久化中的版本只是一个标识，他的序关系只能在版本树中展现，这意味着每次比拟版本号都
执行一个 $O(n) $ 操作。

侥幸的是，树形构造能够通过中序遍历的程序转化为线性构造，中序遍历过程中记录每个节
点首次拜访和末次访问的程序。如上图的树，线性示意为：

$$
b_{a}b_{b}e_{b}b_{c}b_{d}e_{d}e_{c}e_{a}
$$

$b_{a} $ 示意首次拜访节点 $a $，$e_{a} $ 示意末次访问节点 $a $。这样，就很容易判
断后继、前序的关系，例如 $b_{c}>b_{d}>e_{d}>e_{c} $ 可知 $d $ 是 $c $ 的后继。
有一个数据结构
order maintenance 能够在 $O(1) $ 的工夫复杂度上实现这个版本号序的解答。这样就能够
在 $O(1) $ 工夫内解答版本 $v $ 是否是版本 $w $ 的后继。

如下图所示，全长久化的数据结构与半长久化数据结构相似。同样值思考入度为 $p $ 的数
据构造。每个节点存储 $d $ 个成员 (包含数据和指针)，$p $ 个反向指针，留神出度也受
到成员数量 $d $ 的限度。mods 区域大小减少到 $2(d+p+1) $，mods 除了保留数据
成员的批改，也要保留反向指针的批改。

实现读写操作如下。

read(node, field, version) – 在 mods 中应用 order-maintenance 构造找到
$version $ 或它的最近前驱，返回其值。
write(node, field, value, version) – 如果 node.mods 还有空间，就增加一个
记录 (field,version_next)=value，其中 $version_next>version $。如果
node.mods 满了：
- [以版本 $ k $ 为界切分子树] 新建节点 $m $。将节点 $node $ 的 mods 记录分为两
  份，使得存在某个版本 $k $ 和它的的所有后继都在其中一份，另一份中不蕴含 $k $
  或任何 $k $ 的后继。
  新节点 $m $ 保留所有 $k $ 的后继的 mods；老节点 $node $ 保留其它的。
  如下图所示。
- [保留版本 $ k $ 的值] 计算老节点 $node $ 的最近 $m $ 的前驱版本所有数据和反向指
  针，复制到 $m $ 的数据区。
- [批改指针] 递归调用 write() 更新所有街坊的指针(正向和反向)，最多须要更新
  $d+p+(d+p+1) $ 次。

显然读操作复杂度是 $O(1) $。

写操作如果不切分节点的话是 $O(1) $，如果要切分节点就比较复杂。同样应用 amortize
技术：

$$
\phi = -c(numer\ of\ empty\ mods)
$$

势能函数是 mods 空间数量的正数（其实每次操作的势能变动都加上 mods 空间总量就
是 mods 记录数，与半长久化时一样）。如果切分 $\Delta\phi = -2c(d+p+1) $ 否则
$\Delta\phi=c $。所以

$$
amortized\_cost(n) \leq c + c – 2c(d+p+1)+(d+p+(d+p+1))*amortized_cost(x)
$$

开展后常数局部隐没了，所以写操作是 $O(1) $。

实现办法能够参照以上全长久化数据结构。版本从树结构变成了有向无环图，然而偏序关系
仍在。

合并操作很麻烦，比如说某个版本，本人跟本人合并，合并后的新版本再跟本人合并，
这样合并 $n $ 次之后版本就有 $2^{n} $ 了。

可合并长久化数据结构的工夫复杂度剖析很麻烦，每种特定的数据结构能够定义本人的合并
操作，就可能呈现不同的工夫复杂度。
具体参考 Making Data Structures Confluently Persistent。

相比与前述构造，它只规定了应用函数式办法来实现。有几个成熟的数据结构实现了函数式
长久化：

二叉树 (Functional balanced BST) – 次要是复制一份要批改的节点，并把它的前驱节
点都复制一份因为要批改。
Confluently Persistent Tries for Efficient Version Control 这篇文章实现了
$O(log(n)) $ 的函数式长久化实现。
列表 – Purely Functional Worst Case Constant Time Catenable Sorted Lists 实现
了这个数据结构的函数式长久化。

能够参照这几个数据结构实现函数式长久化的其余数据结构。

关于算法:详解记录历史的可持久化数据结构

“ 长久化 ” 的含意

半长久化数据结构

半长久化链表的实现办法

更个别的半长久化数据结构

半长久化数据结构的工夫复杂度

全长久化数据结构

全长久化版本号的问题

全长久化数据结构实现

全长久化数据结构的工夫复杂度

合并长久化数据结构

函数式长久化数据结构