持久化数据结构

形式陈述 ​

持久化数据结构为每次更新产生一个版本标识，旧版本不会被覆盖。partial persistence 允许查询任意版本但只能更新最新版本；full persistence 允许从任意版本分叉更新；confluent persistence 还允许合并多个版本；retroactivity 则修改历史操作并要求传播其后果，是另一种更强语义。这些能力必须分别声明。

Path copying 在更新根到目标的路径时复制被改动节点，新根指向复制链，未变化子树由新旧版本共享。Fat nodes 则在节点内保存带版本标签的字段修改记录，查询按版本选择有效值；记录溢出时再复制节点。正确性要求每个版本经抽象函数映射到相应ADT公理库抽象数据类型Abstract data type · ADT由值集合与操作语义定义、独立于具体表示的数据接口。状态，版本间共享不得让一次更新改变旧版本的可观察结果。

持久化成本需同时报告操作时间、新增空间和查询某版本的开销。结构不可变只保证语义上不覆盖，不保证实现高效；整份复制仍可能每次花 $\mathrm{\Theta }(n)$，有效技术应把复制限制在受控局部，并可能借助摊还分析公理库摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。。

直觉 ​

普通可变结构只有一条被不断覆盖的现在；持久化结构把每次更新变成历史中的新节点，并让多个版本共享没有变化的部分。版本图因此可以是一条链，也可以在 full persistence 下分叉成树或 DAG。

这里的 persistent 指旧逻辑状态仍可查询，不表示进程退出后写入磁盘仍存在。磁盘耐久性、事务日志和崩溃恢复属于存储系统的另一组保证。

例子与边界 ​

持久栈可用不可变链表公理库链表Linked list节点通过指针连接并支持局部插入删除的线性数据结构。实现。版本 $v_0=(b,c)$ 上执行 push(a) 得到 $v_1=(a,b,c)$，新版本只创建头节点 $a$，尾部 $(b,c)$ 与 $v_0$ 共享；从 $v_0$ 再执行 push(d) 得到分支 $v_2=(d,b,c)$。三个版本都能独立读取，且每次压入只新增一个节点。

对平衡搜索树更新一个叶，path copying 复制根叶路径，其他子树共享，新增空间与树高同阶。若节点含可变父指针或外部缓存，并在新版本中原地改写，共享节点会把变化泄露回旧版本，破坏持久性；所有跨版本可观察字段都必须遵守版本规则。

Confluent persistence 不能由“同时引用两个旧根”自动得到：合并可能制造重复边、循环或指数版本依赖，需要特定结构与算法。Retroactivity 更不是读取旧版本，它允许改写过去的操作并重新解释之后状态，两者的问题定义不同。

推论与应用 ​

持久化结构用于撤销、时间旅行查询、函数式程序、版本控制与离线算法。它能保留审计历史，也能让算法同时比较多个分支状态而不复制完整数据。

选择 path copying 还是 fat nodes 取决于每次更新触及的指针数、版本查询模式和节点布局。任何“每次只增常数空间”的结论都需前提；对高度为 $h$ 的树，朴素路径复制通常新增 $O(h)$，而不是无条件 $O(1)$。

参考资料

• James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan, “Making Data Structures Persistent,” Journal of Computer and System Sciences 38(1), 1989, pp. 86–124.
• Chris Okasaki, Purely Functional Data Structures, Cambridge University Press, 1998, Chs. 2–3.