拆分B +樹根

Question

當拆分b +樹的根節點時，我知道你需要n/2 +1，並創建新的根目錄並相應地拆分所有的東西。

我的問題是當n等於一個奇數。就像在這種情況下，n = 5。

所以讓我們用一個簡單的例子：

10 20 30 40 
/ | | | \ 

，所有的孩子都是空。可以說我想爲此添加50個。

會是什麼樣子

 30 
    /\ 
(10,20) (40,50) 

或

  40 
     /\ 
(10,20,30) (50) 

或不同的東西？

Answer 1

如果拆分包含n鍵節點 - 包括導致分裂進入關鍵 - 然後(n - 1)/2鍵去一個新的孩子，n - 1 - (n - 1)/2轉到其他，和一個鍵上升到母公司層面（如分離器鍵）。上升的關鍵不一定是導致分裂的關鍵。如果分隔符無處可去，那麼您將擁有一個新根，分隔符將成爲其單個單獨佔據者（最小佔用要求不適用於根節點）。 r = n - 1給r/2爲一方和r - r/2爲其他：

當然，公式，如果你看看這仍然採取了新的分離後，其他人看起來更友好。

換句話說，在正常情況下，這兩個'半部分'最多相差一個，如果總密鑰數爲偶數，則會發生這種情況，因此在分隔符鍵被取出時會留下一個奇怪的休息。無論多餘的鑰匙是向左還是向右都無關緊要。

但是，這並不是一成不變的。還有其他有效的重新分配策略，最顯着的是Knuth's B*，其中兩個完整節點構成三個已經滿足2/3的節點，依此類推。這也表明分割/合併邏輯與不改變結構的重新分配措施緊密相關，即，在同胞之間捐贈和借用密鑰。