关系数据库的高效永久数据结构

Question

我正在寻找可用于实现关系模型的持久数据结构的材料。

坚持不变数据结构的含义。

任何人都知道一些好的资源，书籍，论文等？

（我已经有这本书Purely Functional Data Structures，这是什么，我正在寻找一个很好的例子。）

Answer 1

它是直接修改无处不B-tree是持久的。每当一个节点被修改时，总是分配一个新节点，然后将新节点返回给递归调用者，递归调用者将通过分配一个新节点将其插入到该级别。等等，最终返回新的根节点。每个操作不会多于O（log N）个节点。

这是在功能语言中使用的技术，例如2-3树。

Answer 2

SQLite有b-tree data structure implementation你可以看看;

Answer 3

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

我建议阅读

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

它是关于如何创建基于普通（临时）一个持续性的数据结构中的原创作品。