B-樹和B+樹資料結構及B-樹的建立和删除操作詳細過程

衆所周知，mysql的索引用的是B+樹

那麼到底啥是B+樹呢？今天學習了一下

下面總結一下我今天學到的知識！

若有錯誤感謝糾正

首先

B-樹念作B樹（而不是B減樹）

B+樹念作B加樹

1、B-樹

1.1、B樹概念

1. 每個結點最多有m個分支(子樹) ;而最少分支數要看是否為根結點，如果是根結點且不是葉子結點則至少有2個分支，非根非葉結點至少有「m/2⌉ 個分支。
2. 有n (k<=n<=m) 個分支的結點有n-1個關鍵字，它們按遞增順序排列。k=2(根結點)或「m/2⌉ (非根結點)
3. 結點内各關鍵字互不相等。
4. 葉結點處于同一層;可以用空指針表示，是查找失敗到達的位置。

階數是人為規定的，下圖為五階B樹。

節點結構體定義示意圖：

p所指向的結點關鍵字小Key+1大于Keyi。

1.2、關鍵字的查找

從根節點開始，從左往右掃描關鍵字，如果找不到就沿着适當的分支到下一節點中去查找。因為節點的關鍵字很少，是以可以用順序查找

1.3、關鍵字的插入（建樹方法）

用以下關鍵字序列{1，2，6, 7，11，4，8, 13, 10，5，17，9, 16,20, 3, 12, 14, 18, 19， 15}建立一棵5階B-樹。

1. 五階B樹最多有四個關鍵字，是以插入前四個關鍵字

   

2. 然後插入11

   

   但是超過了四個關鍵字，是以進行節點拆分的操作

   節點拆分：把目前節點中的5/2向上取整的位置上的關鍵字提出來

   

   5/2向上取整為3

   3位置上的關鍵字是6

   把6提出來，并把它左邊的關鍵字，右邊的關鍵字分别裝在兩個新的節點中

   

   插入時，先查找再插入（如插入4的時候找到了2的右分支的位置）
3. 插入到如下情況時需要再次進行節點拆分，如下圖所示

   

   将10提出來并入上層節點，如下圖所示

   

4. 不斷插入後，成如下圖所示時需要再次才分

   

   将13提出來并入上一次節點

   

   發現還需要再次拆分，将10提出來進行拆分（進行一次插入進行了兩次拆分操作，這就叫連鎖反應）

   

1.4、關鍵字的删除

對于上面建好的B-樹，給出删除關鍵字8、16、 15、 4的過程。

1. 删除8如下圖所示

   

2. 删除16時，16所在節點非葉子結點，删除後可以用左分支節點的最大關鍵字或者右分支節點的最小關鍵字代替16，因為左分支節點隻有兩個關鍵字，已到達節點的最小數量2（最小分支數是5/2向上取整為3，最小關鍵字數就是3-1為2）是以用17取代16，删除後的數結構如下圖所示

   

3. 删除15時因為15所在的節點關鍵字數目已經達到下限，是以想起兄弟節點借關鍵字。先讓17下來，然後讓右兄弟節點的關鍵字上去，效果如圖所示。然後再删除15即可。

   

4. 删除4時，所有兩邊的兄弟節點都無法借關鍵字。于是不借關鍵字，直接删除4然後進行節點合并操作。

   删除4

   

   關鍵字5所在的節點與左邊的節點或右邊的節點進行合并，此處是與右邊節點合并。将上層節點的6拉下來與左右分支節點形成一個新節點。

   

   但是此時發現關鍵字3所在的節點隻有一個關鍵字，不符合B樹要求，于是再次進行合并，将上層節點關鍵字10拉下來與左右節點合并，效果如下圖所示。

   

2、B+樹

B+樹與B-樹的不同

1. 在B+樹中，具有n個關鍵字的結點含有n個分支;而在B-樹中，具有n個關鍵字的結點含有n+1個分支。
2. 在B+樹中，每個結點(除根結點以外)中的關鍵字個數n的取值範圍為「m/2⌉ <=n<=m,根結點的取值範圍為2<=n<=m;而在B-樹中，它們]的取值範圍分别是「m/2⌉-1<=n<=m-1和1<=n<=m-1。
3. 在B+樹中葉子結點包含資訊，并且包含了全部關鍵字，葉子結點引出的指針指向記錄。
4. 在B+樹上有一個指針指向關鍵字最小的葉子結點，所有葉子結點連結成一個線性連結清單，而B-樹沒有。B+樹可以根據P指針進行順序查找。

學習視訊來源：

https://www.bilibili.com/video/BV1Aa4y1j7a4?t=1605