data-structures - 持久与不可变的数据结构

Question

持久和不可变的数据结构有什么区别吗？Wikipedia 在讨论持久性时指的是不可变数据结构，但我感觉两者之间可能存在细微差别。

Answer 1

不变性是一种实现技术。除此之外，它还提供持久性，这是一个接口。持久性 API 类似于：

• version update(operation o, version v)o对 version执行操作v，返回一个新版本。如果数据结构是不可变的，则新版本是一个新结构（可能共享旧结构的不可变部分）。如果数据结构不是不可变的，则返回的版本可能只是一个版本号。该版本v仍然是有效版本，并且不应observe因为此更新而以任何方式更改 - 更新仅在返回的版本中可见，而不是在v.
• data observe(query q, version v)在版本中观察数据结构v而不更改它或创建新版本。

有关这些差异的更多信息，请参阅：

• Haim Kaplan 在Handbook on Data Structures and Applications中的“持久数据结构”一章
• Driscoll 等人的“使数据结构持久化”。
• 麻省理工学院 6.851 的 2012 年春季第一讲：高级数据结构

Answer 2

是，有一点不同。不可变数据结构在创建后不能以任何方式修改。有效修改它的唯一方法是制作一个可变副本或类似的东西（例如稍微修改您传递给新的构造函数的参数）。另一方面，持久数据结构是可变的，因为公开的 API 似乎允许对数据结构进行更改。但实际上，任何更改都将保留指向现有数据结构（以及每个先前结构）的指针；它们似乎只是改变了数据结构，因为公开的 API 返回一个新指针，该指针可能包括指向先前数据结构子集的指针（在树中，例如，我们将指向其子树未因操作）。