缺失 - M = 5

Question

我處理在B樹的刪除在非常特殊的情況下

M = 5 - 即 - 在節點密鑰的最大數目是4並且在鍵的最小數量節點是2

現在當使用防禦方法（我必須使用這個）在BTree中刪除時，當我接近一個節點時，我必須保證它有一個以上所需的關鍵字。

這是我的問題 - 比方說，我有一個根和一個鍵，兩個孩子每個都有兩個鍵。 當我接近這些孩子時，我必須保證它至少有三把鑰匙（因爲M = 5）。

我有兩種方式來做到這一點 - 從鄰居借用或從父親借來併入。我不能借用鄰居，因爲它擁有至少2個密鑰，但是從父親借用並且合併會創建一個包含5個密鑰的節點 - 並且它超過了允許密鑰的最大值（如M = 5）。

在這種情況下該怎麼辦？ 更具體地說 - 對待這種情況的正確方法是什麼

Answer 1

古典B樹約束非根節點的密鑰計數位於d和2d之間，對於某些d。這意味着僅當下溢具有已經發生且合併中涉及的其他節點具有最小佔用率時纔可能合併節點。與從父節點拉出的分隔符​​一起，這使得（d-1）+ d + 1 = 2d的關鍵點數是適合節點的最大值。一路下滑，「萬一」是不可能的。