最近學習了算法導輪里B樹相關的知識，在此寫一篇博客作為總結。

?

1.引言

B樹是為磁盤或其他直接存取的輔助存儲設備而設計的一種平衡搜索樹。B樹類似于紅黑樹，但它與紅黑樹最大不同之處在于B樹的節(jié)點可以擁有很多孩子，因此B樹的高度會比紅黑樹小很多，也因此B樹在磁盤I/O方面表現(xiàn)要比紅黑樹好。（對于磁盤操作最耗時的部分在于磁盤讀寫，而每次讀取一個新的樹的節(jié)點就必須進行一次磁盤讀取，因此節(jié)點較大、樹高度較小的B樹會進行較少的磁盤I/O操作）

2.B樹的定義

一顆B樹的定義如下：

每個節(jié)點x均有如下屬性：

• n表示存儲在該節(jié)點的關鍵字個數(shù)
• n個關鍵字本身key1、key2……keyn以非降序存放，即key1 <= key2 <= …… <= keyn
• 一個leaf布爾值表示該節(jié)點是否為葉節(jié)點

每個內部節(jié)點包含了n+1個孩子，葉節(jié)點沒有孩子

關鍵字keyi對存儲在各子樹中的關鍵字范圍加以分割：即比keyi小的元素在其左子樹，比keyi大的元素在其右子樹

每個葉節(jié)點具有相同的深度

每個節(jié)點包含的關鍵字個數(shù)有上界與下界。我們定義B樹的最小度數(shù)為t，則除根節(jié)點外的每個節(jié)點至少有t-1個關鍵字，每個節(jié)點最多有2t-1個關鍵字（即每個節(jié)點最少有t個孩子，最多有2t個孩子）（當一個節(jié)點有2t-1個關鍵字時，我們稱它為滿的）。

B樹的示意圖如下： 上圖是一個最小度數(shù)為2的B樹，因此每個節(jié)點擁有1個、2個或3個元素，擁有2個、3個或4個孩子，也被稱為2-3-4樹。 根節(jié)點只有一個元素，因此它擁有兩個孩子；兩個孩子分別擁有3個和2個元素，因此他們分別擁有4個和3個孩子。 看到DEF葉節(jié)點位于關鍵字C與G的中間，表明了關鍵字對于存儲在各子樹中的關鍵字范圍進行了分割，其余同理。

3.B樹的插入

要講到樹，就不得不提樹中關鍵的插入與刪除操作，這里我們先總結B樹的插入操作。 當我們往B樹中插入一個新的關鍵字時，由于B樹節(jié)點的關鍵字是受到限制的，因此當一個節(jié)點關鍵字數(shù)目為2t-1時（該節(jié)點是滿的），我們就必須進行分裂操作。

分裂節(jié)點

分裂節(jié)點的主要操作為把滿節(jié)點的中間關鍵字提升至父節(jié)點，把原滿節(jié)點分裂為中間關鍵字的兩個左右節(jié)點 其示意圖如下： 對于某個非滿的節(jié)點x，若其孩子節(jié)點x.ci為滿的（即孩子節(jié)點的關鍵字數(shù)目為2t-1)。則把其孩子節(jié)點的中間關鍵字（S）提升為父節(jié)點（x節(jié)點）的關鍵字，并把原孩子節(jié)點（x.c節(jié)點）分成兩個t-1個關鍵字的節(jié)點，分別位于中間關鍵字（S）的左、右。 還有一種比較特殊的情況就是B樹根的分裂： 分裂是B樹長高的唯一途徑，因此分裂是非常重要的。

插入

講完分裂操作在講插入操作就非常簡單了。插入的時候我們通過比較不斷地根據關鍵字的值尋找孩子節(jié)點，當發(fā)現(xiàn)一個滿的節(jié)點時便分裂，最后找到對應的葉節(jié)點時根據關鍵字的值插入相應位置即可。 下面是一個插入關鍵字的例子： B樹的初始狀態(tài)如圖所示，這是一顆最小度數(shù)為3的B樹，即他的關鍵字個數(shù)為2～5個。 插入關鍵字B，在根節(jié)點由于（B < G）往進入G的左節(jié)點，到達葉節(jié)點后添加至A與C關鍵字之間。 插入關鍵字Q：

在根節(jié)點，由于P < Q 而且 Q < X，進入P與X之間的子節(jié)點

發(fā)現(xiàn)該子節(jié)點是滿的，則進行分裂，把關鍵字T上升到父節(jié)點，原子節(jié)點分為RS與UV，分為在T關鍵字的左右

由于Q < T，于是進入T的左子節(jié)點

在RS葉節(jié)點中找到對應位置并加入

插入關鍵字L：

發(fā)現(xiàn)根節(jié)點是滿的，分裂根節(jié)點，上移P

L < P 進入P的左子節(jié)點

G < L < M，進入G與M關鍵字間的節(jié)點

在葉節(jié)點的相應位置中插入

插入關鍵字F：

F < P，進入P的左子節(jié)點

F < G，進入G的左子節(jié)點

發(fā)現(xiàn)滿的節(jié)點，分裂，上移C

F > C，進入C的右子節(jié)點

在葉節(jié)點的相應位置中插入

4.B樹的刪除

講完了B樹的插入操作，我們再來講講B樹的刪除操作。 對于刪除操作，我們必須保證每個節(jié)點在刪除前必須至少有t（最小度數(shù)）個關鍵字。 首先我們把要刪除的關鍵字（假設為k）分兩種情況：

• 關鍵字k在葉節(jié)點中：直接刪除
• 關鍵字k在內部節(jié)點中，分三種情況：
  • k的左子節(jié)點擁有t個關鍵字，則把k的左子節(jié)點的最后一個關鍵字（假設為j）上移到父節(jié)點，然后遞歸的刪除j
  • k的右子節(jié)點擁有t個關鍵字，則把k的右子節(jié)點的第一個關鍵字（假設為l）上移到父節(jié)點，然后遞歸的刪除l
  • k的左右子節(jié)點都只有t-1個關鍵字，則把k下降與左右子節(jié)點合并成一個擁有2t-1個關鍵字的節(jié)點，然后遞歸的刪除k

然后我們再定義一些在尋找刪除節(jié)點路上的操作：如果在尋找刪除節(jié)點的路上，我們發(fā)現(xiàn)某個節(jié)點關鍵字數(shù)只有t-1個關鍵字，則分兩種情況：

看該節(jié)點的相鄰兄弟節(jié)點是否含有至少t個關鍵字，如果是則向相鄰的兄弟節(jié)點“借一個關鍵字”（一該節(jié)點的左節(jié)點為例：把左節(jié)點的最后一個關鍵字上升至父節(jié)點，然后父節(jié)點位置的節(jié)點下移到關鍵字個數(shù)為t-1的節(jié)點上）

如果該節(jié)點相鄰的兄弟節(jié)點都只含有t-1個關鍵字，則選擇一個兄弟節(jié)點合并，并把兩兄弟之間的父節(jié)點下移

下面我們來看一個B樹刪除的例子： B樹的初始狀態(tài)如圖，這是一顆最小度數(shù)為3的B樹，即每個節(jié)點擁有2～5個關鍵字。 刪除F操作：

F < P，進入P的左子節(jié)點

C < F < G，進入C與G之間的子節(jié)點

在葉節(jié)點中刪除F

刪除M操作：

M < P，進入P的左子節(jié)點

在內部節(jié)點中發(fā)現(xiàn)M，查看M的左子節(jié)點JKL，擁有3個關鍵字，則把最后一個關鍵字L上升至M的位置，遞歸的刪除L

節(jié)點JKL是葉節(jié)點，直接刪除L即可

刪除G操作：

G < P，進入P的左子節(jié)點

在內部節(jié)點中發(fā)現(xiàn)G，查看G的左右子節(jié)點均只有2個關鍵字（不足最小度數(shù)3個），下降G關鍵字并合并其左右子節(jié)點

節(jié)點DEGJK為葉節(jié)點，直接刪除G即可

刪除D操作：

D < P，進入P的左子節(jié)點

發(fā)現(xiàn)內部節(jié)點CL只有2個關鍵字（不足最小度數(shù)3個），其兄弟節(jié)點也只有2個關鍵字，下降父節(jié)點P，與兄弟節(jié)點一起合并成一個節(jié)點

由于C < D < L，進入C與L間的子節(jié)點

DEJK節(jié)點是葉節(jié)點，直接刪除D即可

刪除B操作：

B < C，進入E的左子節(jié)點

發(fā)現(xiàn)節(jié)點AC只有兩個關鍵字，其兄弟節(jié)點EJK有三個關鍵字，則E上移到父節(jié)點，C下移到子節(jié)點，變?yōu)楣?jié)點ABC

節(jié)點ABC為葉節(jié)點，直接刪除B即可

轉載于:https://www.cnblogs.com/KingIceMou/p/6984141.html

總結

以上是生活随笔為你收集整理的算法导轮之B树的学习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。