B + - Java中的樹

Question

我想在Java中創建一個B + -Tree的簡單實現，我需要一些幫助。 我希望我的程序能夠實現這些功能：搜索，插入，刪除。

我的問題：

1. 什麼是用來表示樹的最佳數據結構？我想着 想着TreeMap。
2. 在B +樹中，數據存儲在節點（K，V）的葉節點 中，並且在內部節點中，而不是每個記錄中的數據 存在指向子節點（K，P）的指針。我想建議 關於如何指向另一個節點，因爲我不能在java中使用指針。

此外，如果您有任何建議，或者你有一個簡單的實施，我可以用作參考，請告訴我。

由於

Answer 1

整點B樹的（或任何存在的小的變化的）是存儲在磁盤上的數據，使得它可以與少量的磁盤訪問被讀取。如果你想把所有內容都保存在內存中，你應該使用一個平衡的二叉搜索樹（也許是一棵紅黑樹或splay樹），或者甚至是一個香草BST，但是你的問題似乎都沒有考慮到這個事實。

1. 什麼是用來表示樹的最佳數據結構？我在想TreeMap。

TreeMap是在內存中的數據結構，因此目前還不清楚這將如何幫助表示磁盤上的樹。此外，這爲您實現了一個二叉搜索樹，所以如果您使用TreeMap，那麼您自己並沒有真正實現B樹。

在B +樹的數據被存儲olny在葉節點（K，V），並在內部節點，而不是在每一個記錄數據有一個指針指向一個子節點（K，P）。我想建議如何指向其他節點，因爲我不能在java中使用指針。

您不需要實際的指針來表示B樹，只是文件偏移量。您需要定義一種表示這些偏移量的方法（根據文件開頭的字節或塊的數量，具體取決於實現的其他部分的結構），並根據文件偏移量訪問所有內容。實際上，您應該使用標準的C風格指針來指向B +樹中的節點，而不是而不是。如果你這樣做了，下一次程序啓動時這些指針就沒有意義了，所以你將失去磁盤數據結構的持久性優勢。

要乾淨地訪問文件內容，我推薦memory mapping。在Java中創建內存映射文件對象的一種有用方法是FileChannel.map。該方法返回一個MappedByteBuffer，您可以使用它來讀取特定文件偏移量處的一大塊字節。