可持久化数据结构

在计算机编程中，可持久化数据结构（Persistent data structure）是一种能够在修改之后其保留历史版本（即可以在保留原来数据的基础上进行修改——比如增添、删除、赋值）的数据结构。这种数据结构实际上是不可变对象，因为相关操作不会直接修改被保存的数据，而是会在原版本上产生一个新分支。这个术语是在1986年Driscoll、Sarnak、Sleator和Tarjans的文章中提出的。

如果一个数据结构包括当前版本在内的所有历史版本都可以被访问，但只有当前版本可以被修改，那么该数据结构就是部分可持久化数据结构。如果该数据结构的所有版本都可以被查询或修改，那么这种数据结构就是完全可持久化数据结构。如果存在能够创建基于两个历史版本的新版本（即合并两个版本 meld() （浇铸（？）混合（？））或 merge() （合并）操作），那么这种数据结构就是可汇合的可持久化数据结构。不可持久化的数据结构被称为短暂性数据结构。

这些类型的数据结构在逻辑编程和函数式编程之中非常常见。

部分可持久化与完全可持久化

在部分可持久化模型中，编程者可以查询该类数据结构的任一历史版本，但是只能修改（更新）最新版本。这意味着数据结构的每个版本之间是线性排序的。在完全持久化模型中，编程者可以查询和修改（更新）该类数据结构的所有版本，在某些情况之下，允许查询和或修改（更新）历史版本的功能会削减，比如 Rope 数据结构就是如此。另外，如果一个数据结构除了完全可持久化外，还可以将同种数据结构的两个版本合并成一个新的版本，且这个新版本仍然是完全持久化的，那么这个数据结构就可以被称为可汇合的持久化的。

保留历史版本的方法

“Copy on Write”（写入时复制）

创建可持久化数据结构的一种方式是使用平台提供的短暂数据结构（比如数组）来存储数据结构中的数据，并对对于数据结构的任何更改使用复制整个数据结构的方式来记录每次更改。这是一种效率低下的技术，因为每次写入都必须复制整个数据结构，这使得对一个大小为 $n$ 的数组进行 $m$ 次修改时，出现最差情况下的时间复杂度为 ${\text{O}}(nm)$ 。

“Fat node”（胖节点）

“胖节点”的方法是将对于该节点的所有更改记录在节点本身，但是在修改时不覆盖节点上原来的数值。这就要求允许节点能任意“变胖”。换句话说，每一个胖节点都包含了与它的历史版本的信息和指针字段，同时还拥有任意数量的额外字段值空间。每个额外的字段值都有一个相关联的字段名和一个版本戳，它表示该节点在哪个版本中被更改和被改为值。此外，每个胖节点都有自己的版本戳，用于记录该版本是在那个版本中被修改的。节点的版本戳的唯一目的是确保每个节点在被一个版本中的每一个字段仅仅包含一个唯一的值。为了浏览结构，每个节点中每个原始字段值的版本戳为零。

“胖节点”算法的时间复杂度

使用“胖节点”算法完成可持久化，每次修改需要 ${\text{O}}(1)$ 的空间：只需要存储新数据。每一次修改都需要额外的 ${\text{O}}(1)$ 的时间来在历史版本的结尾处存储更改。这是均摊分析的（假设修改历史存储在一个可以扩大的数组之中）。在查询时，必须遍历整个结构以找到每个节点的正确的版本。如果要进行 $m$ 次修改，那么每一次查询操作都会遭到 ${\text{O}}(\log m)$ 的减速——这是在数组中寻找最近修改的版本造成的。

“Path copying”（路径复制）

路径复制算法，将即将被修改的点路径上的所有节点克隆出一个新的。这些修改必须通过数据结构逐级连接：克隆而得的所有节点指向旧节点的指针必须被修改为指向新节点。这些修改会引起连锁更改，直达根节点。