一蚌本、B樹性質

1、初識B樹

image

• B樹是一種平衡的多路搜索樹堂竟，多用于文件系統(tǒng)魂毁，數(shù)據(jù)庫的實現(xiàn)。
• B樹特點：
  • 一個節(jié)點可以存儲超過2個元素出嘹，可以擁有超過2個子節(jié)點席楚。
  • 擁有二叉樹的一些性質。
  • 平衡税稼，每個節(jié)點的所有子樹高度一致烦秩。
  • 比較矮。

2郎仆、m階B樹的性質（m >= 2）

• 假設一個節(jié)點存儲的元素個數(shù)為x只祠。
  • 根節(jié)點個數(shù)：1 <= x <= m-1，三階B樹根節(jié)點數(shù)大于等于1并且小于等于2扰肌。
  • 非根節(jié)點：(m / 2)(向下取整) - 1 <= x <= m - 1
  • 如果有子節(jié)點抛寝，子節(jié)點個數(shù) y = x + 1
    • 根節(jié)點：2 <= y <= m
    • 非根節(jié)點：(m / 2)(向下取整) <= y <= m

image

3、B樹 VS 二叉搜索樹

• 將二叉搜索樹的節(jié)點合并曙旭，可以成為B樹盗舰。
• 多代（父和子）節(jié)點合并，可以獲得一個超級節(jié)點（類似3階B樹中的18和33節(jié)點桂躏，23和30節(jié)點）钻趋。
  • 2代合并的超級節(jié)點，最多擁有4個子節(jié)點（至少是4階B樹）剂习。
  • 3代合并的超級節(jié)點蛮位，最多擁有8個子節(jié)點（至少是8階B樹）。
  • n代合并的超級節(jié)點鳞绕，最多擁有2^n個子節(jié)點（至少是2^n階B樹）失仁。

image

• 將18和33合并，23和30合并们何，20和21合并萄焦，45和47合并，50和52合并垂蜗。即將一個B樹變?yōu)?code>二叉搜索樹楷扬。

image

二、B樹的操作

1贴见、搜索

• 先在節(jié)點內(nèi)部從小到大搜索元素烘苹。
• 如果命中，搜索結束片部。
• 如果未命中镣衡，再去對應的子節(jié)點中搜索元素，重復步驟1档悠。

image

• 假設搜索72廊鸥，首先在根節(jié)點做比較，72大于40辖所，所以接著在根節(jié)點的右子樹搜索惰说，72大于60小于80，繼續(xù)在60和80之間的子樹尋找缘回，因為72大于70吆视，所以需要繼續(xù)往70的右子樹尋找，但是右子樹為空酥宴，所以得出結論72不在該B樹上啦吧。

2、添加

• 新添加的元素必定是添加到葉子節(jié)點拙寡。

image

• 假設插入55授滓，首先在根節(jié)點做比較，55大于40肆糕，所以接著在根節(jié)點的右子樹搜索般堆，55小于60，繼續(xù)在60的左子樹尋找擎宝，55大于50郁妈，所以將55插入在節(jié)點50的右側。

image

• 假設插入95绍申，首先在根節(jié)點做比較噩咪，95大于40，所以接著在根節(jié)點的右子樹搜索极阅，95大于80胃碾，繼續(xù)在80的右子樹尋找，95大于90小于100筋搏，所以將95插入在節(jié)點90和100的中間仆百。

3、上溢

image

• 假設再插入98呢奔脐？（假設這是一顆4階B樹）
  • 最右下角的葉子節(jié)點的元素個數(shù)將超過限制俄周。
  • 這種現(xiàn)象可以稱之為：上溢（overflow）吁讨。

4、上溢的解決

• 假設5階B樹峦朗。

image

• 上溢節(jié)點的元素個數(shù)必然等于m（5）建丧。
• 假設上溢節(jié)點最中間元素的位置為k（3）。
• 將k位置的元素向上與父節(jié)點合并波势。
• 將[0,k-1]和[k+1,m-1]位置的元素分裂成2個子節(jié)點翎朱，這2個子節(jié)點的元素個數(shù)，必然都不會低于最低限制（m / 2(向下取整) - 1）尺铣。

image

• 一次分裂完畢后拴曲，有可能導致父節(jié)點上溢凛忿，依然按照上述方法解決澈灼。

image

• 最極端的情況，有可能一致分裂到根節(jié)點侄非。
• 添加元素導致的上溢蕉汪，是唯一一種可能導致B樹長高的操作。

5逞怨、添加導致上溢的例子

image

• 插入98

image

• 98大于根節(jié)點者疤，繼續(xù)往根節(jié)點右子樹比較，98大于60和80叠赦，繼續(xù)往80右子樹比較驹马，98大于90，95除秀，小于100糯累，所以將98插入在95和100中間。
• 插入98之后册踩，90 95 98 100節(jié)點溢出泳姐，需要上溢，將中間元素95或98向上與父節(jié)點合并暂吉，將90胖秒，98，100節(jié)點分裂成2個子節(jié)點慕的。
• 插入52

image

• 插入54

image

6阎肝、刪除

• 假如需要刪除的元素在葉子節(jié)點中，那么直接刪除即可肮街。

image

• 刪除30

image

• 假如需要刪除的元素在非葉子節(jié)點中风题。
  • 先找到前驅或后繼元素，覆蓋所需刪除元素的值。
  • 再把前驅或后繼元素刪除沛硅。
• 刪除60

image

• 60的前驅為55眼刃，將55從54和55節(jié)點中刪除，并將55覆蓋60摇肌。

image

• 非葉子節(jié)點的前驅或后繼元素鸟整，必定在葉子節(jié)點中。
  • 所以這里的刪除前驅或后繼元素朦蕴，就是最開始提到的情況：刪除的元素在葉子節(jié)點中。
  • 真正的刪除元素都發(fā)生在葉子節(jié)點中弟头。

7吩抓、下溢

image

• 假設一顆5階B樹，刪除22赴恨。
• 葉子節(jié)點被刪除一個元素后疹娶，元素個數(shù)可能會低于最低限制（>= m/2(向下取整) - 1）。
• 這種現(xiàn)象稱為：下溢（underflow）伦连。

8雨饺、下溢的解決

• 下溢節(jié)點的元素數(shù)量必然等于(m/2(向下取整) - 2)。
• 如果下溢節(jié)點臨近的兄弟節(jié)點惑淳，有至少m/2(向下取整)個元素额港，可以向其借一個元素。

image

• 綠色節(jié)點在刪除一個元素后歧焦，節(jié)點元素個數(shù)低于最低限制（>= m/2(向下取整) - 1）移斩。
  • 為了使樹繼續(xù)滿足B樹的要求，需要對綠色節(jié)點進行下溢操作绢馍。
  • 將父節(jié)點的元素b插入到下溢節(jié)點的0位置（最小位置）向瓷。
  • 用兄弟節(jié)點的元素a（最大的元素）替代父節(jié)點的元素b。
  • 這種操作其實就是：旋轉舰涌。
  • 注意子節(jié)點d也需要調(diào)整猖任。

image

• 如果下溢節(jié)點臨近的兄弟節(jié)點，只有（>= m/2(向下取整) - 1）個元素瓷耙。
  • 將父節(jié)點的元素b挪下來跟左右子節(jié)點進行合并朱躺。
  • 合并后的節(jié)點元素個數(shù)等于m/2(向下取整) + m/2(向下取整) - 2，不超過m-1哺徊。
  • 這個操作可能會導致父節(jié)點下溢室琢，依然按照上述方法解決，下溢現(xiàn)象可能會一直往上傳播落追。
• 添加元素導致的下溢盈滴，是唯一一種可能導致B樹變矮的操作。