Persistent data structure 不可变数据结构 - Deflect-o-Bot

Persistent data structure 不可变数据结构

持久性变数据不要和持久储存相混淆

在计算机中持久性数据或非临时数据是一种数据结构，在修改时始终保持其自身的先前版本。这些数据实际上是不可变的，因为对这类数据操作不会明显的改变数据结构，而是始终产生新的数据结构。

部分持久性数据：如果可以访问某个数据所有版本，但只能修改最新的版本，则数据是部分持久的。

汇合持久性数据：如果可以从之前的两个数据版本通过合并或者融合，可以创建一个新版本数据，则数据是汇合持久的。

数据结构不是持久的则称之为临时的。

持久性数据结构在逻辑编程和函数式编程中特别常见，因为这些范式中的语言不鼓励或者完全禁用可变的数据结构。

部分持久和完全持久

在部分持久数据结构中，开发者可以查看任意的之前的版本，但只能更新最新版本，这意味着数据结构每个版本之间呈线性排序的。

在完全持久数据中，可以在任何版本的数据上进行更新和查询。

复制后重写

创建持久数据结构的一种方法是使用平台提供的临时数据结构（如数组）将数据存储在数据结构中，并使用写入时复制语义复制整个数据结构，以便对数据结构进行任何更新。这是一种低效的技术，因为每次写入都必须复制整个后备数据结构，从而导致对大小为 n 的数组进行 m 次修改的最坏情况 O（n·m） 性能特征。

扩展节点

扩展节点方法是在节点本身中记录对节点字段所做的所有更改，而不擦除字段的旧值。这就要求允许节点变得任意“胖”。换句话说，每个节点都包含与临时节点相同的信息和指针字段，以及任意数量的额外字段值的空间。每个额外的字段值都有一个关联的字段名称和一个版本标记，该标记指示命名字段更改为具有指定值的版本。此外，每个节点都有自己的版本标记，指示创建节点的版本。具有版本戳的节点的唯一用途是确保每个节点每个版本的每个字段名称仅包含一个值。为了在结构中导航，节点中的每个原始字段值都有一个零的版本戳。

路径重联

使用路径复制方法，将在路径上创建所有节点的副本，以指向即将修改的任何节点。然后，这些更改必须通过数据结构级联回来：必须将指向旧节点的所有节点修改为指向新节点。这些修改会导致更多的级联更改，依此类推，直到到达根节点。

上述两种的结合方式

在每个节点中，存储一个修改框。此框可以保存对节点的一次修改（对其中一个指针的修改，或者对节点的键的修改，或者对某个其他特定于节点的数据的修改），以及应用该修改时的时间戳。最初，每个节点的修改框都是空的。每当访问节点时，都会选中修改框，并将其时间戳与访问时间进行比较。（访问时间指定要考虑的数据结构的版本。)如果修改框为空，或者访问时间早于修改时间，则忽略修改框，只考虑节点的正常部分。如果访问时间晚于修改时间，则使用修改框中的值，覆盖节点中的该值。
修改节点的工作方式如下所示。（假定每个修改都涉及一个指针或类似字段。)如果节点的修改框为空，则用修改填充该框。否则，修改框已满。将创建节点的副本，但仅使用最新值。修改直接在新节点上执行，无需使用修改框。（新节点的某个字段将被覆盖，其修改框将保持为空。) 最后，此更改将级联到节点的父级，就像路径复制一样。（这可能涉及填写父级的修改框，或以递归方式制作父级的副本。如果节点没有父节点（它是根），则会将新根添加到排序的根数组中。
使用此算法，给定任何时间t，在时间t的数据结构中最多存在一个修改框。因此，时间 t 的修改将树拆分为三个部分：一部分包含时间 t 之前的数据，一部分包含时间 t 之后的数据，一部分不受修改的影响。