B樹

B樹即平衡查找樹竖慧，一般理解為平衡多路查找樹季研，也稱為B-樹鸽疾、B_樹熊尉。是一種自平衡樹狀數(shù)據(jù)結(jié)構(gòu)焚挠，能對存儲的數(shù)據(jù)進(jìn)行O(log n)的時(shí)間復(fù)雜度進(jìn)行查找、插入和刪除碳胳。B樹一般較多用在存儲系統(tǒng)上递沪，比如數(shù)據(jù)庫或文件系統(tǒng)豺鼻。

B樹特點(diǎn)

1.B樹可以定義一個(gè)m值作為預(yù)定范圍，即m路(階)B樹款慨。
1.每個(gè)節(jié)點(diǎn)最多有m個(gè)孩子儒飒。
2.每個(gè)節(jié)點(diǎn)至少有ceil(m/2)個(gè)孩子，除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外檩奠。
3.對于根節(jié)點(diǎn)桩了，子樹個(gè)數(shù)范圍為[2,m]附帽，節(jié)點(diǎn)內(nèi)值的個(gè)數(shù)范圍為[1,m-1]。
4.對于非根節(jié)點(diǎn)井誉，節(jié)點(diǎn)內(nèi)的值個(gè)數(shù)范圍為[ceil(m/2)-1,m-1]蕉扮。
5.根節(jié)點(diǎn)(非葉子節(jié)點(diǎn))至少有兩個(gè)孩子。
6.一個(gè)有k個(gè)孩子的非葉子節(jié)點(diǎn)包含k-1個(gè)值颗圣。
7.所有葉子節(jié)點(diǎn)在同一層喳钟。
8.節(jié)點(diǎn)內(nèi)的值按照從小到大排列。
9.父節(jié)點(diǎn)的若干值作為分離值分成多個(gè)子樹在岂，左子樹小于對應(yīng)分離值奔则，對應(yīng)分離值小于右子樹。

以下是一個(gè)四階B樹蔽午，

image

插入
假設(shè)現(xiàn)在構(gòu)建一棵四階B樹易茬，開始插入“A”，直接作為根節(jié)點(diǎn)及老，

image

插入“B”疾呻，大于“A”，放右邊写半，

image

插入“C”，按順序排到最后尉咕，

image

繼續(xù)插入“D”叠蝇，直接添加的結(jié)果如下圖，此時(shí)超過了節(jié)點(diǎn)可以存放容量年缎，對于四階B樹每個(gè)節(jié)點(diǎn)最多存放3個(gè)值悔捶，此時(shí)需要執(zhí)行分裂操作，

image

分裂操作為单芜，先選取待分裂節(jié)點(diǎn)的中值蜕该，這里為“B”，然后將中值“B”放到父節(jié)點(diǎn)中洲鸠，因?yàn)檫@里還沒有父節(jié)點(diǎn)堂淡，那么直接創(chuàng)建一個(gè)新的父節(jié)點(diǎn)存放“B”，而原來小于“B”的那些值作為左子樹扒腕，原來大于“B”的那些值作為右子樹绢淀。

image

繼續(xù)插入“E”，”E”大于“B”瘾腰，往右子節(jié)點(diǎn)皆的，

分別于“C”和“D”比較，大于它們蹋盆，放到最右邊费薄，

image

插入“F”硝全，“F”大于“B”，往右子樹楞抡，

image

“F”分別與“C””D”“E”比較伟众，大于它們，放到最右邊拌倍，此時(shí)觸發(fā)分裂操作赂鲤，

image

選取待分裂節(jié)點(diǎn)的中值“D”，然后將中值“D”放到父節(jié)點(diǎn)中柱恤，父節(jié)點(diǎn)中的“B”小于“D”数初，于是放到“B”右邊，而原來小于“D”的那些值作為左子樹梗顺，原來大于“D”的那些值作為右子樹泡孩。

image

繼續(xù)插入“M”，結(jié)果為寺谤，

image

插入“L’仑鸥，大于“B”“D”，往右子樹变屁，

image

“L”大于“E”“F”小于“M”眼俊，于是放到第三個(gè)位置，此時(shí)觸發(fā)分裂操作粟关，

image

選取待分裂節(jié)點(diǎn)的中值“F”疮胖，然后將中值“F”放到父節(jié)點(diǎn)中，父節(jié)點(diǎn)中的“B”“D”都小于“F”闷板，于是放到最右邊澎灸，而原來小于“F”的那些值作為左子樹，原來大于“F”的那些值作為右子樹遮晚。

image

插入“K”性昭，結(jié)果為，

image

插入“J”县遣，大于“B”“D”“F”糜颠，往右子樹，

image

“J”小于“K”“L”“M”萧求，于是放到第一個(gè)位置括蝠，此時(shí)觸發(fā)分裂操作，

image

選取待分裂節(jié)點(diǎn)的中值“K”饭聚，然后將中值“K”放到父節(jié)點(diǎn)中忌警，父節(jié)點(diǎn)中的“B”“D”“F”都小于“K”，于是放到最右邊，而原來小于“K”的那些值作為左子樹法绵，原來大于“K”的那些值作為右子樹箕速。此時(shí)父節(jié)點(diǎn)也觸發(fā)分裂操作，

image

選取待分裂節(jié)點(diǎn)的中值“D”朋譬，然后將中值“D”放到父節(jié)點(diǎn)中盐茎，由于還沒有父節(jié)點(diǎn)，那么直接創(chuàng)建一個(gè)新的父節(jié)點(diǎn)存放“D”徙赢，而原來小于“D”的那些值作為左子樹字柠，原來大于“D”的那些值作為右子樹。

image

插入“I”狡赐，大于“D”窑业，往右子樹，

image

右子樹不是葉子節(jié)點(diǎn)枕屉，繼續(xù)往下常柄，這時(shí)“I”大于“F”而小于“K”，所以往第二個(gè)分支搀擂，

image

“I”小于“J”西潘，于是放到左邊，

image

類似地哨颂，插入“H”喷市，結(jié)果如下，

image

插入“G”威恼，往左子樹品姓，

image

往中間分支，

image

觸發(fā)分裂操作沃测，

image

選取待分裂節(jié)點(diǎn)的中值“H”，然后將中值“H”放到父節(jié)點(diǎn)中食茎，”H”大于父節(jié)點(diǎn)中的“F”而小于“K”蒂破，于是放到中間，而原來小于“H”的那些值作為左子樹别渔，原來大于“H”的那些值作為右子樹附迷。

image

綜上所述，插入操作的核心是分裂操作哎媚。無需分裂的情況比較簡單喇伯，直接插入即可；如果插入后超過節(jié)點(diǎn)容量拨与，這個(gè)容量可預(yù)先自定義稻据，則需要進(jìn)行分裂操作，需要注意的是分裂可能引起父節(jié)點(diǎn)需要繼續(xù)分裂买喧。

查找
對B樹進(jìn)行查找就比較簡單捻悯，查找過程有點(diǎn)類似二叉搜索樹匆赃，從根節(jié)點(diǎn)開始查找，根據(jù)比較數(shù)值找到對應(yīng)的分支今缚，繼續(xù)往子樹上查找算柳。

比如查找“I”，”I”大于“D”姓言，往右子樹瞬项，

image

“I”分別與節(jié)點(diǎn)內(nèi)值比較，大于“F”“H”而小于“K”何荚，往第三個(gè)分支囱淋，

image

逐一比較節(jié)點(diǎn)內(nèi)的值，找到“I”兽泣。

image

轉(zhuǎn)自：https://blog.csdn.net/wangyangzhizhou/article/details/82215430