B +樹中的非葉節點

Question

假設一個m階的B +樹。爲什麼非葉子節點必須至少有小孩（m/2）？或者如果這個屬性不滿意會發生什麼。

Answer 1

如果您不執行半滿規則，您可以（有效）獲得不平衡的樹，例如，

     [root] 
        / \_________________________ 
        /        \ 
      [branch]         [branch] 
     /  \        ____/ | \___ 
     /  \       /  |  \ 
[1-record leaf] [1-record leaf] [100-record leaf] [100-record leaf] [100-record leaf] 

在這棵樹中找到第一條或第二條記錄比找到其他300條記錄需要的時間要少得多。

如果你讓樹葉只有一條記錄，樹枝只有一個鍵（因此有兩個孩子），我相信查找時間的差異可能會像log（m）那樣差（其中m是樹的順序）。沿完整節點的路徑查找記錄需要Θ（log（N）* log（m））時間（其中N =記錄的總數，因此log（N）與樹的高度成正比）沿着最小尺寸節點的路徑記錄一個記錄只需要Θ（log（N））時間（因爲你在每個分支處只進行一次比較，而在葉子處沒有）。

通過執行半滿規則，可以確保所有查找時間都是Θ（log（N）* log（m）），並且在彼此的常數因子內。