1、概述

B樹是一種平衡的多路搜索樹，多用于文件系統(tǒng)、數(shù)據(jù)庫的實(shí)現(xiàn)。

3階B樹.png

4階B樹.png

5階B樹.png

• 1、一個節(jié)點(diǎn)可以存儲超過2個元素，可以擁有超過2個子節(jié)點(diǎn)。
• 2、擁有二叉搜索樹的性質(zhì)。
• 3、平衡，每個節(jié)點(diǎn)的所有子樹高度一致。
• 4、比較矮。

2、m階B樹的性質(zhì)（m>=2）

2.1、元素個數(shù)和子節(jié)點(diǎn)個數(shù)

• 1、假設(shè)一個節(jié)點(diǎn)存儲的元素個數(shù)為x
  • 根節(jié)點(diǎn)：1 <= x <= m-1
  • 非根節(jié)點(diǎn)：ceil(m/2)-1 <= x <= m-1
• 2、如果有子節(jié)點(diǎn)，那么子節(jié)點(diǎn)的個數(shù)y = x + 1
  - 根節(jié)點(diǎn)：2 <= y <= m
  - 非根節(jié)點(diǎn)：ceil(m/2) <= y <= m
  比如 m = 3，2 <= y <= 3，因此可以稱為（2,3）樹。
  比如 m= 4，2 <= y <= 4，因此可以稱為（2,4）樹。
  比如 m=5，3 <= y <= 5，因此可以稱為（3,5）樹。
  比如 m=6, 3 <= y <= 6，因此可以稱為（3,6）樹。
  比如 m=7，4 <= y <= 7，因此可以稱為（4,7）樹。

3、B樹 VS 二叉搜索樹

• 1、B樹和二叉搜索樹邏輯上是等價(jià)的。

  
  
  二叉搜索樹.png
  
  

  和二叉搜索樹等價(jià)的B樹

  
  
  image.png
• 2、多代合并
• 2代合并：將上圖二叉搜索樹中的節(jié)點(diǎn)18和節(jié)點(diǎn)33合并或者將節(jié)點(diǎn)18、節(jié)點(diǎn)12、節(jié)點(diǎn)33合并就表示2代合并。
  2代合并（將多個節(jié)點(diǎn)合成一個擁有多個元素的節(jié)點(diǎn)）后的超級節(jié)點(diǎn)，最多有4個子節(jié)點(diǎn)。（至少是4階B樹）
• 3代合并：將二叉搜索樹中節(jié)點(diǎn)18、 節(jié)點(diǎn)33 、節(jié)點(diǎn)48合并成超級節(jié)點(diǎn)，最多有8個子節(jié)點(diǎn)。（至少是8階B樹）
• n代合并：n代合并的超級節(jié)點(diǎn)，最多有2?個子節(jié)點(diǎn)。（至少是n階B樹）
• m階B樹，最多需要log2(m)代合并。

4、搜索

B樹的搜索和二叉搜索樹的搜索類似。

image.png

• 1、先從節(jié)點(diǎn)內(nèi)部從小到大進(jìn)行搜索。
• 2、如果命中則返回。
• 3、如果未命中，則去對應(yīng)的子節(jié)點(diǎn)中進(jìn)行搜索，先從節(jié)點(diǎn)內(nèi)部從小到大進(jìn)行搜索。
  比如搜索52，先和40進(jìn)行比較，發(fā)現(xiàn)大于40，然后去右子節(jié)點(diǎn)中搜索，發(fā)現(xiàn)52小于60，則去左子節(jié)點(diǎn)中進(jìn)行搜索，發(fā)現(xiàn)52大于50，則在節(jié)點(diǎn)內(nèi)部向右搜索，找到52返回。

4、添加

• 新添加的元素必定是葉子節(jié)點(diǎn)（二叉搜索樹也是如此）。
  
  image.png
  
  示例一：在上述B樹中插入55，過程如下

和40比較，大于40，然后和右子樹節(jié)點(diǎn)元素比較，小于60，則和其左子元素進(jìn)行比較，大于50，將元素插入到50的右邊。結(jié)果如下圖

image.png

image.png

image.png

添加導(dǎo)致上溢的解決

下圖為5階B樹的一部分

image.png

• 上溢節(jié)點(diǎn)的元素個數(shù)必定等于m（元素個數(shù)最大等于m-1）。
• 假設(shè)上溢節(jié)點(diǎn)最中間元素的位置k

• 將k位置的元素向上與父節(jié)點(diǎn)合并。
• 將上溢節(jié)點(diǎn)[0,k-1]和[k+1,m-1]分成兩個子節(jié)點(diǎn)。作為k位置元素的左右子節(jié)點(diǎn)。（不用擔(dān)心這兩個子節(jié)點(diǎn)的個數(shù)小于ceil(m/2)-1）。

分裂完成圖如下：

image.png

• 一次分裂完成，有可能導(dǎo)致父節(jié)點(diǎn)上溢，依然按照上述方法解決。最極端情況可能要一直分裂到根節(jié)點(diǎn)。
  假設(shè)上圖已經(jīng)分裂到了根節(jié)點(diǎn)

• 取出上溢根節(jié)點(diǎn)中間元素40，將其作為新的根節(jié)點(diǎn)，假設(shè)位置為k
• 將[0,k-1]、[k=1,m-1]分裂成2個字節(jié)點(diǎn)，作為根節(jié)點(diǎn)的左右子節(jié)點(diǎn)

結(jié)果如下圖

image.png

添加練習(xí)

下圖是一個4階B樹

image.png

• 插入98

  
  
  image.png

• 插入 52

  
  
  image.png

• 插入 54

  
  
  image.png

5、刪除節(jié)點(diǎn)

5.1、刪除葉子節(jié)點(diǎn)

如果刪除的是葉子節(jié)點(diǎn)，那么直接刪除即可。

image.png

比如刪除30

image.png

5.2、刪除非葉子節(jié)點(diǎn)

• 如果刪除的是非葉子節(jié)點(diǎn)

1. 先找到前驅(qū)或后繼元素，覆蓋所要刪除的元素。

2. 再把前驅(qū)或后繼元素刪除。

   
   
   image.png
   
   

   比如刪除60

找前驅(qū)節(jié)點(diǎn)和二叉樹相同，node.left.right.right.....
60的前驅(qū)元素為55，用55覆蓋60
由于55是在葉子節(jié)點(diǎn)中，直接刪除即可

image.png

5.3、刪除導(dǎo)致的下溢

看下圖中的5階B樹

image.png

5.4、下溢的解決

旋轉(zhuǎn)操作

• 下溢節(jié)點(diǎn)的元素必然等于ceil(m/2)-2
• 如果下溢節(jié)點(diǎn)臨近的兄弟節(jié)點(diǎn)中的元素個數(shù)至少有ceil(m/2)個，可以向兄弟節(jié)點(diǎn)借一個元素。

• 將父節(jié)點(diǎn)中的b元素插入到下溢節(jié)點(diǎn)的0的位置，即最小位置。
  用兄弟節(jié)點(diǎn)的最大元素a替代父節(jié)點(diǎn)的元素b。
  這種操作其實(shí)是**旋轉(zhuǎn) **。
  上面操作是右旋操作，所以原先a元素的右子節(jié)點(diǎn)d變成了b元素的左子節(jié)點(diǎn)。
  
  image.png
• 下面看下左旋操作
  
  image.png
  
  刪除左子節(jié)點(diǎn)元素，會下溢，將b元素插入到下溢節(jié)點(diǎn)的最大位置，用兄弟節(jié)點(diǎn)的最小元素a替代父節(jié)點(diǎn)元素b。

合并操作

• 如果下溢節(jié)點(diǎn)臨近的兄弟節(jié)點(diǎn)元素，只有ceil(m/2)-1個元素。

將父節(jié)點(diǎn)的元素b挪下來和左右子節(jié)點(diǎn)進(jìn)行合并。
合并后的元素個數(shù)=ceil(m/2)+ceil(m/2)-2，不超過m-1。
這樣操作可能會造成父節(jié)點(diǎn)下溢，依然按照上述方法解決，下溢現(xiàn)象可能會一直向上傳播。

練習(xí)

下圖是一棵5階B樹

image.png

1. 葉子節(jié)點(diǎn)元素個數(shù)為1，小于ceil(m/2)-1。
   2.由于臨近兄弟節(jié)點(diǎn)的元素個數(shù)ceil(m/2)-1，所以不能從兄弟節(jié)點(diǎn)中接元素。只能將父節(jié)點(diǎn)中的元素20挪下來和其左右子節(jié)點(diǎn)合并成一個節(jié)點(diǎn)。
   3.挪下來之后發(fā)現(xiàn)父節(jié)點(diǎn)元素個數(shù)小于ceil(m/2)-1。則需要將根節(jié)點(diǎn)30挪下來和其左右子節(jié)點(diǎn)進(jìn)行合并。

image.png

6、4階B樹

學(xué)習(xí)4階B樹是為了更好的理解紅黑樹，這也是本文的目的。
4階B樹的性質(zhì)：

• 1、所有節(jié)點(diǎn)能存儲的元素的個數(shù)：1 <= x <= 3
• 2、所有非葉子節(jié)點(diǎn)的節(jié)點(diǎn)的個數(shù)： 2 <= y <= 4

6.1、添加

元素從1添加到22，組成一個4階B樹。

• 1、首先在根節(jié)點(diǎn)中添加1、2、3,3個元素，當(dāng)添加4時(shí)，會發(fā)生上溢，取出中間位置元素2，放入新的根節(jié)點(diǎn)中，分裂出[1]和[3,4]來作為2的左右子節(jié)點(diǎn)。

  
  
  image.png

• 2、在3、4所在節(jié)點(diǎn)中添加5、6，又會發(fā)生上溢，取出中間元素4和父節(jié)點(diǎn)合并，分裂出[3]和[5,6]作為4的左右子節(jié)點(diǎn)。

  
  
  image.png

• 3、在5、6所在節(jié)點(diǎn)中添加7、8，又會上溢，取出中間元素6和父節(jié)點(diǎn)合并，分裂出[5]和[7,8]作為6的左右子節(jié)點(diǎn)。

  
  
  image.png

• 4、在子節(jié)點(diǎn)7、8中加入9、 10會發(fā)生上溢，取出中間元素8和父節(jié)點(diǎn)合并，分裂出[7]和[9,10]作為8的左右子節(jié)點(diǎn)，第一次分裂完成后，根節(jié)點(diǎn)會發(fā)生上溢。取出中間元素4作為新的根節(jié)點(diǎn)，[2]和[6,8]作為根節(jié)點(diǎn)的左右子節(jié)點(diǎn)。

  
  
  image.png

• 5、其他添加過程類似，最終結(jié)果如下

  
  
  image.png

6.2、刪除

從1刪除到22

• 1、刪除葉子節(jié)點(diǎn)1，直接刪除，導(dǎo)致下溢，臨近的兄弟節(jié)點(diǎn)元素個數(shù)為ceil(m/2)-1，無法從兄弟節(jié)點(diǎn)借元素，只能將父節(jié)點(diǎn)元素2下移和3進(jìn)行組合，這樣父節(jié)點(diǎn)2也會下溢，將父節(jié)點(diǎn)4下移和6進(jìn)行組合，父節(jié)點(diǎn)依然會下溢，此時(shí)可以從兄弟節(jié)點(diǎn)借元素12，進(jìn)行左旋操作，結(jié)果如下
  
  image.png

• 2、刪除元素2并不會下溢，直接刪除即可。刪除元素3會造成下溢，將父節(jié)點(diǎn)元素4挪下來和左右子節(jié)點(diǎn)進(jìn)行合并即可。

  
  
  image.png

• 3、刪除元素4不會造成下溢，直接刪除即可。刪除5操作下溢，將父元素6向下和左右子節(jié)點(diǎn)進(jìn)行合并，這樣父節(jié)點(diǎn)依然下溢，將父元素8向下和左右子節(jié)點(diǎn)合并，父元素依然下溢，將根節(jié)點(diǎn)12向下和左右子節(jié)點(diǎn)合并

  
  
  image.png
• 4、繼續(xù)刪除情況類似不再贅述。