我一直在玩Clojure的數據庫，並希望實現一個B +樹。當我開始思考它時，我意識到可能沒有辦法像Clojure中的其他節點那樣使用指針/引用。對於像BST或許多其他Tree結構這樣的東西無關緊要，因爲您只需要存儲Node的孩子。但是，我在做什麼像B +樹，我需要能夠引用一個節點的兄弟？在Clojure中寫入需要指針/引用的數據結構？
在尋找解決方案時，我在Google Groups中發現了一篇關於如何在Clojure中實現雙向鏈表的文章，因爲在Clojure中還有其他的做法。
雖然我該怎麼做B +樹？
這並不是說很難在clojure中引用對象;但一般來說，這些引用是不可變的。它是不可變的，它使得雙向鏈表不可能，因爲與單鏈表不同，如果不在某處創建突變，則不能更改它的任何部分。
看到這一點，假設我有一個單向鏈表，
a -> b -> c
，並假設我想改變它的頭。我可以這樣做，改變整個列表。我創建一個新的列表，爲頭值創建一個新的值，並重新使用尾部：
a'-> b -> c
但是雙向鏈表是不可能的。因此，在clojure和其他功能語言中，我們有時在這種情況下使用zipper。
現在，假設你真的需要Clojure中的可變引用 - 它是如何實現的？嗯，這取決於你所需要的併發語義，Clojure的有vars，refs，等
而且，與deftype，您可以創建一個具有可變字段的對象，而這些可變域可以包含到其他事情的引用。你也可以在clojure中使用原始的java數組來達到同樣的目的。
您的數據庫將成爲內存數據庫還是磁盤備份數據庫？如果在磁盤上，我認爲pointer swizzling的問題比具有可變引用的問題要棘手。
回到功能數據結構的問題，我認爲有可能創建具有純功能語義的B樹。這裏的第一條線索是它是一棵樹，樹是麪包黃油和功能數據結構的肉。其次，請注意，有些數據庫只能以append-only方式工作 - 例如couchDB。從某種意義上講，這有利於數據庫是自己的日誌。爲了更好地瞭解這種方法的成本和收益，您可能需要watch Slava Akhmechet's presentation。他的公司RethinkDB最終採用了一種混合方法，IIRC。
感謝您的回答，我會研究您指出的事情。 DB現在可能會在內存中看起來好像我要學習一堆關於Clojure的過程 – TriArc 2010-11-22 02:53:16
您可能希望查看Clojure中的Chouser's finger trees以查看如何使用功能樣式實現雙向鏈表的功能。
或者，您可能只是想退一步問自己，爲什麼您認爲B +是功能語言數據結構的不錯選擇。
如果您不熟悉替代方案，可以查看Chris Okazaki的書「Purely Functional Data Structures」。「
感謝這本書的建議我會盡量找到傳統B +樹的替代品 原因我想使用B +樹是因爲我想最終將數據存儲在磁盤上並且B +樹是非常適合這種情況，特別是在磁盤訪問很少的情況下進行範圍查詢 – TriArc 2010-11-24 15:32:19
我完全不明白這個問題，但出於好奇：爲什麼鏈表不能解決問題？ – Belun 2010-11-22 08:28:31
我並沒有試圖實現一個鏈表，而是提到它，因爲我在實現B +樹時遇到的問題，即處理對節點的引用，與我在處理鏈接列表時遇到的問題相同。 – TriArc 2010-11-24 15:33:32