关系数据库的高效持久化数据结构

将无处不在的 B 树修改为持久性是很简单的。只需在修改节点时始终分配一个新节点，并将新节点返回给递归调用者，递归调用者将通过分配新节点等方式将其插入该级别。最终，将返回新的根节点。每个操作分配的节点不超过 O（log N）。

这是函数式语言中用于实现的技术，例如，2-3 棵树。

SQLite有一个b树数据结构实现，你可以看看;

我已经为 BergDB （http://bergdb.com/） 实现了这样的数据结构 - 一个具有持久数据结构的数据模型的数据库。

我建议阅读

http://www.cs.cmu.edu/~sleator/papers/Persistence.htm

这是关于如何基于普通（短暂）数据结构创建持久性数据结构的原始工作。