持久化数据结构

普通可变结构只有一条被不断覆盖的现在；持久化结构把每次更新变成历史中的新节点，并让多个版本共享没有变化的部分。每次更新只从一个已有版本分叉时，逻辑版本图是一棵树，partial persistence 的更新历史则是一条链；confluent 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 复制根叶路径，其他子树共享，新增空间与树高同阶。若节点含可变父指针或外部缓存，并在新版本中原地改写，共享节点会把变化泄露回旧版本，破坏持久性；所有跨版本可观察字段都必须遵守版本规则。

Eppstein游走枚举理路Eppstein的k条最短游走Eppstein k shortest paths · Eppstein sidetrack algorithm · k shortest walks用到终点的最短路树和非负偏离差价编码游走，通过共享偏离堆将无限候选空间改造成常数分支堆序树，按费用输出隐式记录。给出另一项路径复制工作负载：每个顶点沿最短路树继承后继的完全二叉根堆，再插入本地最小偏离边。插入只复制根到新末叶的位置链，保留其他子树共享；旧根仍供其他起点查询，因此每次O(log(n+1))的新节点有具体形状与不变量支撑。

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

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

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