BTree實現 - 我需要先知道樹的順序嗎？

Question

所以我有一個我的數據結構類的項目，我必須實現一個非常簡單的信息數據庫。記錄必須存儲在一個文件中，當程序打開時 - 必須從文件中讀取並放入BTree。我的問題是我們還沒有談論BTrees，課本中的講座也不太清楚（它沒有任何代碼，只是解釋和幾個例子）。

我的問題是：我可以創建一個BTree而不必先知道它的順序嗎？或者我應該爲訂單設置一個非常高的數字，以便我可以確定它能夠適合很多記錄？有什麼建議麼？

Answer 1

你當然可以 - BTrees被設計用來整理他們的輸入。所需要的只是比較任何兩個對象的能力，並能夠確定哪一個「較大」或稍後應該去。 BTrees會隨着您添加更多項目而動態增長，從而爲它們增加更多級別。我希望你的教授能夠很好地涵蓋BTrees，因爲它們是一個非常吸引人的結構:-)。

如果您希望將BTree作爲您的任務的一部分來實施，那麼您需要轉到TA並詳細解釋它 - 總體思路是每個節點都是一個節點根據值的範圍對其進行排序，或指向其他節點的值。每次將節點添加到此樹時，都會走到節點所在的位置，並在可能的情況下添加節點。如果不是，則重新組織樹直到可能，然後添加節點。

魔鬼的細節，在這種情況下的細節將需要一些時間，並很好的解釋，以充分grok。人們忍受頭痛的所有複雜原因的原因是因爲BT預先不需要事先知道它們最終會有多大，或者這些元素會覆蓋什麼範圍，或者其他什麼。作爲獎勵，它們非常適合在磁盤上使用，甚至無法將所有元素存儲在內存中。

Answer 2

如果您正在實施自己的BTree，那麼您應該確保它可以支持不同的訂單，具體而言，因爲您要使用的訂單將取決於介質。 BTree的目的是儘量減少進行隨機訪問所需的時間，因此內存中的BTree（如果要這樣使用）需要單個節點適合緩存行，並且如果要要將BTree存儲在磁盤上（在這種情況下你將要做的），你會希望你的節點適合磁盤扇區。