關係數據庫的高效永久數據結構

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

它是關於如何創建基於普通（臨時）一個持續性的數據結構中的原創作品。