持久数据结构与不可变数据结构

Question

持久化和不可变的数据结构有什么区别吗？维基百科在讨论持久性时提到了不可变的数据结构，但我有一种感觉，这两者之间可能有细微的区别。

Answer 1

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

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

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

• The chapter "Persistent data structures" by Haim Kaplan in
• "Making Data Structures Persistent" by Driscoll et al.
• The first lecture of the Spring 2012 incarnation of MIT's 6.851: Advanced Data Structures

Answer 2

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