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

原文地址

“ 长久化 ” 的含意

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

1. 半长久化 (Partial Persistance) – 能够读数据结构过来任意版本，只能在最新版本
   写。
2. 全长久化 (Full Persistance) – 能够读数据结构过来任意版本，能够在数据结构任意
   版本写。
3. 可合并长久化 (Confluent Persistent) – 不光能够在任何版本上读写，还能够将两个版
   本合并以创立一个新的版本。
4. 函数式长久化 (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 \) , 如上图所示，每个节点有三类成员。

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

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

1. read(node, field, version) – 在节点的批改记录区 node.mods 查找批改 field
   成员的最大版本 \(w \)，使得 \(w\leq version \)。如果没找到，那么只读的数据成员
   区域的 field 成员就是以后值。

2. 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 除了保留数据
成员的批改，也要保留反向指针的批改。

实现读写操作如下。

1. read(node, field, version) – 在 mods 中应用 order-maintenance 构造找到
   \(version \) 或它的最近前驱，返回其值。

2. 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 实现
  了这个数据结构的函数式长久化。

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