B-樹(shù)如何插入

這篇文章將為大家詳細講解有關(guān)B-樹(shù)如何插入，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

插入過(guò)程和樹(shù)的構建過(guò)程本質(zhì)是一致的，即都是進(jìn)行插入操作，并對插入后的B-樹(shù)進(jìn)行調整。

我們設定B-樹(shù)的階為5。用關(guān)鍵字序列{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}來(lái)構建一棵B-樹(shù)。

因為樹(shù)的階為5，那么，每個(gè)節點(diǎn)最多有5個(gè)子節點(diǎn)，每個(gè)節點(diǎn)內的關(guān)鍵字個(gè)數為3~4個(gè)。

于是，第一步是插入1，2，6，7作為一個(gè)節點(diǎn)。

然后插入11，得到1，2，6，7，11. 因為節點(diǎn)個(gè)數超過(guò)4，所以需要對該節點(diǎn)進(jìn)行拆分。選取中間節點(diǎn)6，進(jìn)行提升，提升為父節點(diǎn)，于是得到：

有一個(gè)規則是新插入的節點(diǎn)總是出現在葉子節點(diǎn)上，接著(zhù)插入4，8，13，直接插入即可，得到

然后插入10. 得到

因為最右下的節點(diǎn)內有5個(gè)元素，超過(guò)最大個(gè)數4了，所以需要進(jìn)行拆分，把中間節點(diǎn)10進(jìn)行提升，上升到和6一起，形成如下結構。

然后插入5，17，9，16，得到如下

之后插入20，插入20后，最右下節點(diǎn)內元素個(gè)數為5個(gè)，超過(guò)最大個(gè)數4個(gè)，所以，需要把16進(jìn)行提升，形成如下結構

之后插入3、12、14、18、19，后，形成如下結構。

然后插入15，會(huì )導致13提升到根節點(diǎn)，這時(shí)，根節點(diǎn)會(huì )有5個(gè)節點(diǎn)，那么，根節點(diǎn)中的10會(huì )再次進(jìn)行提升，形成如下結構。

結束。