多路樹-B*樹

B* 樹，除根節點以外，所有節點至少是三分之二是滿的，。

B*樹的分裂：當一個結點滿時，如果它的下一個兄弟結點未滿，那麼将一部分

資料移到兄弟結點中，再在原結點插入關鍵字，最後修改父結點中兄弟結點的關鍵字

（因為兄弟結點的關鍵字範圍改變了）；如果兄弟也滿了，則在原結點與兄弟結點之

間增加新結點，并各複制1/3的資料到新結點，最後在父結點增加新結點的指針；

是以，B*樹配置設定新結點的機率比B+樹要低，空間使用率更高；

 分裂過程：

插入6以後

如果兄弟也滿了的情況：

插入4以後

小結

樹：二叉樹，每個結點隻存儲一個關鍵字，等于則命中，小于走左結點，大于

走右結點；

樹：多路搜尋樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵

字範圍的子結點；

所有關鍵字在整顆樹中出現，且隻出現一次，非葉子結點可以命中；

樹：在B-樹基礎上，為葉子結點增加連結清單指針，所有關鍵字都在葉子結點