漫畫:什麼是B-樹?

————————————

————————————

二叉查找樹的結構：

第1次磁碟IO：

第2次磁碟IO：

第3次磁碟IO：

第4次磁碟IO：

下面來具體介紹一下B-樹（Balance Tree），一個m階的B樹具有如下幾個特徵：

1.根結點至少有兩個子女。

2.每個中間節點都包含k-1個元素和k個孩子，其中 m/2 <= k <= m

3.每一個葉子節點都包含k-1個元素，其中 m/2 <= k <= m

4.所有的葉子結點都位於同一層。

5.每個節點中的元素從小到大排列，節點當中k-1個元素正好是k個孩子包含的元素的值域分劃。

第1次磁碟IO：

在內存中定位（和9比較）：

第2次磁碟IO：

在內存中定位（和2，6比較）：

第3次磁碟IO：

在內存中定位（和3，5比較）：

自頂向下查找4的節點位置，發現4應當插入到節點元素3，5之間。

節點3，5已經是兩元素節點，無法再增加。父親節點 2， 6 也是兩元素節點，也無法再增加。根節點9是單元素節點，可以升級為兩元素節點。於是拆分節點3，5與節點2，6，讓根節點9升級為兩元素節點4，9。節點6獨立為根節點的第二個孩子。

自頂向下查找元素11的節點位置。

刪除11後，節點12隻有一個孩子，不符合B樹規範。因此找出12,13,15三個節點的中位數13，取代節點12，而節點12自身下移成為第一個孩子。（這個過程稱為左旋）

—————END—————

喜歡本文的朋友們，歡迎長按下圖關注訂閱號夢見，收看更多精彩內容