複製鏈接
請複製以下鏈接發送給好友

B*樹

鎖定
B*樹是B+樹的變體,在B+樹的非根和非葉子結點再增加指向兄弟的指針;B*樹定義了非葉子結點關鍵字個數至少為(2/3)*M,即塊的最低使用率為2/3(代替B+樹的1/2)。
中文名
B*樹
簡    介
是B+樹的變體
分    裂
一個結點滿時,分配一個新的結點
優    點
B*樹分配新結點的概率比B+樹要低

目錄

B*樹分類介紹

B+樹的分裂:當一個結點滿時,分配一個新的結點,並將原結點中1/2的數據複製到新結點,最後在父結點中增加新結點的指針;B+樹的分裂隻影響原結點和父結點,而不會影響兄弟結點,所以它不需要指向兄弟的指針;
B*樹的分裂:當一個結點滿時,如果它的下一個兄弟結點未滿,那麼將一部分數據移到兄弟結點中,再在原結點插入關鍵字,最後修改父結點中兄弟結點的關鍵字(因為兄弟結點的關鍵字範圍改變了);如果兄弟也滿了,則在原結點與兄弟結點之間增加新結點,並各複製1/3的數據到新結點,最後在父結點增加新結點的指針;

B*樹結論

B*樹分配新結點的概率比B+樹要低,空間使用率更高;