如何最大化每個btree節點的元素數量

Question

我正在構建一些數據的btree。一旦我構建btree（即插入所有元素），我不再插入或移除元素。然而，由此產生的b樹不是最優的，因爲如果我可以非常頻繁地得到每個節點的最大元素，那麼我的節點包含少於n個元素（問題變得更糟，大的n是）。這是從我的B樹的部分時，幾百個元素和ñ等於5的部分包含根節點和幾個最底層的節點

正如你可以看到不少的節點較少比5個元素。我的問題是： 有沒有一種方法可以在構建完成後「壓縮」btree，以便所有元素（除了可能是最底部的一些節點）都包含n元素。將要存儲在節點中的密鑰將是32位值，但我不能保證它們將以任何特定順序插入。

Answer 1

如果因爲鍵/記錄沒有按鍵的順序交付獲得打包B樹的經典方法是不可行的，那麼基本上有兩種選擇：

• 離線：建立從一個新的，裝B樹刮
• 在線：通過使用節點相反分裂

建立一個新的B樹是簡單和快速的程序壓縮就地B樹，並且是可以做到的「幾乎」原地。唯一額外的空間需求包括一個頁面（或頁面緩衝區），用於btree的每個級別，以保持正在構建的新btree的正確脊柱。一旦它們被清空，舊樹的頁面可以被回收用於新樹。

該計劃通常被稱爲'金字塔'計劃或'自下而上'打包。不用說，它要求btree在打包過程中完全脫機，或者根據查詢的鍵將查詢分發到正確的樹（舊的或新的）。

在線壓縮採用基本相同的邏輯，只有細節有點不同，因爲密鑰（記錄）是從右邊的鄰居而不是從輸入來的。樹必須向上壓實一層一層，從底部，從最左邊的葉子：

• 下拉從右邊鄰居
• 水蛭鍵父節點分隔鍵，直到該節點全
• 推右鄰居的新的最左邊的鍵向上作爲分隔
• 做出正確的鄰居你的當前節點，沖洗和重複

兩種方案 - 包裝的建設和網上緊湊離子 - 可以使樹的右側脊上的節點充滿或甚至空着。如果這是不可取的，那麼可以通過在關卡的最後兩個節點之間重新分配鍵來修復它。這可以通過調用與正常btree操作中使用的相同的借用/平衡過程來完成。就像包裝和壓縮一樣，這種脊椎再平衡必須從下往上進行。即從最右邊的葉子到根部。