B-樹，就是B樹棋恼，B樹的原英文名是B-tree,所以很多翻譯為B-樹,就會(huì)很多人誤以為B-樹是一種樹返弹、B樹是另外一種樹。其實(shí)蘸泻，B-tree就是B樹琉苇。
B樹是一種多叉平衡查找樹，我們之前所介紹的紅黑樹是二叉查找樹結(jié)構(gòu)悦施，B樹由于是多叉結(jié)構(gòu)，對(duì)于元素?cái)?shù)量非常多的情況下去团，樹的深度不會(huì)像二叉結(jié)構(gòu)那么大抡诞，可以保證查詢效率。
B樹的性質(zhì)（m階的B樹）
- 樹中每個(gè)結(jié)點(diǎn)最多含有m個(gè)孩子（m>=2）土陪；
- 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外昼汗，其它每個(gè)結(jié)點(diǎn)至少有[ceil(m / 2)]個(gè)孩子（其中ceil(x)是一個(gè)取上限的函數(shù)）；
- 根結(jié)點(diǎn)至少有2個(gè)孩子（除非B樹只包含一個(gè)結(jié)點(diǎn)：根結(jié)點(diǎn)）鬼雀；
- 所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層顷窒，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息(可以看做是外部結(jié)點(diǎn)或查詢失敗的結(jié)點(diǎn)，指向這些結(jié)點(diǎn)的指針都為null)源哩；（注：葉子節(jié)點(diǎn)只是沒有孩子和指向孩子的指針鞋吉，這些節(jié)點(diǎn)也存在，也有元素励烦。類似紅黑樹中谓着，每一個(gè)NULL指針即當(dāng)做葉子結(jié)點(diǎn)，只是沒畫出來而已）坛掠。
- 每個(gè)非終端結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字信息： (n赊锚，P0，K1屉栓，P1舷蒲，K2，P2友多，......牲平，Kn，Pn)夷陋。其中：
a) Ki (i=1...n)為關(guān)鍵字欠拾，且關(guān)鍵字按順序升序排序K(i-1)< Ki胰锌。
b) Pi為指向子樹根的結(jié)點(diǎn)，且指針P(i-1)指向子樹種所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki藐窄，但都大于K(i-1)资昧。
c) 關(guān)鍵字的個(gè)數(shù)n必須滿足： [ceil(m / 2)-1]<= n <= m-1。比如有j個(gè)孩子的非葉結(jié)點(diǎn)恰好有j-1個(gè)關(guān)鍵碼荆忍。
B樹的插入
根據(jù)B樹的性質(zhì)格带，一個(gè)m階的B樹需要滿足：
- 樹中每個(gè)結(jié)點(diǎn)含有最多含有m個(gè)孩子，即m滿足：ceil(m/2)<=m<=m刹枉。
- 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外叽唱，其它每個(gè)結(jié)點(diǎn)至少有[ceil(m / 2)]個(gè)孩子（其中ceil(x)是一個(gè)取上限的函數(shù)）；
- 除根結(jié)點(diǎn)之外的結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)n必須滿足： [ceil(m / 2)-1]<= n <= m-1（葉子結(jié)點(diǎn)也必須滿足此條關(guān)于關(guān)鍵字?jǐn)?shù)的性質(zhì)）微宝。
針對(duì)一棵高度為h的m階B樹棺亭，插入一個(gè)元素時(shí)，首先在B樹中是否存在蟋软，如果不存在镶摘，一般在葉子結(jié)點(diǎn)中插入該新的元素，此時(shí)分3種情況：
如果葉子結(jié)點(diǎn)空間足夠岳守，即該結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)小于m-1凄敢，則直接插入在葉子結(jié)點(diǎn)的左邊或右邊；
如果空間滿了以致沒有足夠的空間去添加新的元素湿痢，即該結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)已經(jīng)有了m個(gè)涝缝，則需要將該結(jié)點(diǎn)進(jìn)行“分裂”，將一半數(shù)量的關(guān)鍵字元素分裂到新的其相鄰右結(jié)點(diǎn)中譬重，中間關(guān)鍵字元素上移到父結(jié)點(diǎn)中拒逮，而且當(dāng)結(jié)點(diǎn)中關(guān)鍵元素向右移動(dòng)了，相關(guān)的指針也需要向右移害幅。
此外消恍，如果在上述中間關(guān)鍵字上移到父結(jié)點(diǎn)的過程中，導(dǎo)致根結(jié)點(diǎn)空間滿了以现，那么根結(jié)點(diǎn)也要進(jìn)行分裂操作狠怨，這樣原來的根結(jié)點(diǎn)中的中間關(guān)鍵字元素向上移動(dòng)到新的根結(jié)點(diǎn)中，因此導(dǎo)致樹的高度增加一層邑遏。
插入以下字符字母到一棵空的5階B 樹中：C N G A H E K Q M F W L T Z D P R X Y S
分析： 根據(jù)上面的性質(zhì)總結(jié)佣赖，5階的B樹，非根節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)n滿足2<=n<=4,每個(gè)節(jié)點(diǎn)最多含有5個(gè)孩子记盒，除根節(jié)點(diǎn)葉子節(jié)點(diǎn)之外憎蛤，其他節(jié)點(diǎn)至少3個(gè)孩子。
-
關(guān)鍵字個(gè)數(shù)最大4，先取前4個(gè)插入到相同的節(jié)點(diǎn)中俩檬。
1.jpg -
插入H萎胰，因?yàn)椴襟E一后空間不夠，就需要將中間關(guān)鍵字元素上移到父結(jié)點(diǎn)中棚辽，樹增加一層
2.jpg -
在步驟二的圖中技竟，可以繼續(xù)插入E,K,Q三個(gè)節(jié)點(diǎn)，繼續(xù)插就得分裂
3.jpg -
插入M將進(jìn)行分裂屈藐，M剛好是中間元素榔组，直接上移到父節(jié)點(diǎn)中，HK联逻、NQ分開為兩個(gè)節(jié)點(diǎn)
4.jpg -
如步驟四的圖中可以繼續(xù)插入F,W,L,T
5.jpg -
在步驟五之后搓扯，插入Z就得進(jìn)行分裂，T上移到父節(jié)點(diǎn)
6.jpg -
如步驟六的圖中插入D,進(jìn)行分裂包归，D上移到父節(jié)點(diǎn)中锨推，然后插入后續(xù)的P,R,X,Y節(jié)點(diǎn)沒有分裂
7.jpg -
插入最后一個(gè)S，含有N,P,Q,R的節(jié)點(diǎn)需要分裂公壤，Q上移爱态，導(dǎo)致父節(jié)點(diǎn)D,G,M,T也滿了，也需要進(jìn)行分裂境钟，繼續(xù)將中間元素M上移，產(chǎn)生新的節(jié)點(diǎn)俭识，樹高度再加一層慨削。
8.jpg
B樹的刪除
首先查找B樹中要?jiǎng)h除的元素，若元素存在套媚，則進(jìn)行刪除缚态。刪除該元素后，需要判斷該元素是否有左右孩子節(jié)點(diǎn)
- 如果有堤瘤，則上移孩子節(jié)點(diǎn)中的相近元素(左孩子中最右邊的節(jié)點(diǎn)或者右孩子中最左邊的節(jié)點(diǎn))到父節(jié)點(diǎn)中去玫芦，移動(dòng)之后的情況。
- 如果沒有本辐，直接刪除桥帆，移動(dòng)之后的情況。
刪除元素慎皱，然后進(jìn)行元素移動(dòng)之后老虫，如果節(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)目不滿足條件(小于ceil(m/2)-1),則需要看其相鄰的兄弟節(jié)點(diǎn)是否豐滿(關(guān)鍵字個(gè)數(shù)大于ceil(m/2)-1)
- 如果豐滿，則向父節(jié)點(diǎn)借一個(gè)元素來滿足
- 如果其相鄰兄弟都剛脫貧茫多，即借了之后其結(jié)點(diǎn)數(shù)目小于ceil(m/2)-1祈匙，則該結(jié)點(diǎn)與其相鄰的某一兄弟結(jié)點(diǎn)進(jìn)行“合并”成一個(gè)結(jié)點(diǎn)，以此來滿足條件。
對(duì)剛剛插入的樹進(jìn)行刪除操作夺欲，依次刪除H,T,R,E
-
刪除H,在葉子節(jié)點(diǎn)H,K,L中跪帝，刪除后還剩兩個(gè)關(guān)鍵字，能夠滿足不小于ceil(m/2)-1=2些阅，進(jìn)行簡(jiǎn)單的刪除元素后面的元素向前移動(dòng)即可伞剑。
d1.jpg -
刪除T,QT節(jié)點(diǎn)不滿足關(guān)鍵字要求，需要上移孩子節(jié)點(diǎn)中相近元素W
d2.jpg -
刪除R,刪除后RS節(jié)點(diǎn)只剩一個(gè)關(guān)鍵字扑眉，根據(jù)上面的分析纸泄，兄弟節(jié)點(diǎn)豐滿，就向父節(jié)點(diǎn)借一個(gè)W,同時(shí)X需要上移到父節(jié)點(diǎn)中去腰素。
d3.jpg -
刪除E,刪除后EF節(jié)點(diǎn)只剩一個(gè)關(guān)鍵字聘裁，根據(jù)上面分析，兄弟節(jié)點(diǎn)剛脫貧弓千，則需要跟相鄰兄弟節(jié)點(diǎn)合并衡便，D在兩個(gè)需要合并的節(jié)點(diǎn)之間，所以需要下移到之前的AC節(jié)點(diǎn)中洋访，將僅剩的F進(jìn)行合并镣陕，形成ACDF節(jié)點(diǎn)
d4.jpg
但是我們發(fā)現(xiàn)中間有一個(gè)節(jié)點(diǎn)只包含一個(gè)關(guān)鍵字，并且該節(jié)點(diǎn)非根節(jié)點(diǎn)姻政，這個(gè)就需要進(jìn)行修改呆抑。接下來進(jìn)行分析：如果相鄰兄弟節(jié)點(diǎn)豐滿，可以從父節(jié)點(diǎn)中進(jìn)行借一個(gè)元素汁展，但是我們右邊的QX節(jié)點(diǎn)并不豐滿鹊碍，所以只能下移M節(jié)點(diǎn)，減少樹的高度食绿。最終圖如下：
d5.jpg
B+樹
B樹的一種變形樹侈咕，m階的B+樹和m階的B樹區(qū)別：
- 所有葉子節(jié)點(diǎn)包含全部關(guān)鍵字信息，及指向含有這些關(guān)鍵字記錄的指針器紧，且葉子節(jié)點(diǎn)中關(guān)鍵字進(jìn)行有序鏈接
- 非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引）耀销，葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；
B+樹比B樹更適合操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引的原因：
- B+樹的磁盤讀寫代價(jià)更低铲汪，B+樹的內(nèi)部節(jié)點(diǎn)沒有指向關(guān)鍵字具體信息的指針熊尉，因此內(nèi)部節(jié)點(diǎn)相對(duì)B樹更小。如果把所有同一內(nèi)部節(jié)點(diǎn)的關(guān)鍵字放在同一塊磁盤中桥状，盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也就越多帽揪，一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多辅斟，相對(duì)IO讀寫次數(shù)降低
舉個(gè)例子，假設(shè)磁盤中的一個(gè)盤塊容納16bytes蔗崎，而一個(gè)關(guān)鍵字2bytes缓苛，一個(gè)關(guān)鍵字具體信息指針2bytes未桥。一棵9階B-tree(一個(gè)結(jié)點(diǎn)最多8個(gè)關(guān)鍵字)的內(nèi)部結(jié)點(diǎn)需要2個(gè)盤塊冬耿。而B+
樹內(nèi)部結(jié)點(diǎn)只需要1個(gè)盤快亦镶。當(dāng)需要把內(nèi)部結(jié)點(diǎn)讀入內(nèi)存中的時(shí)候，B 樹就比B+ 樹多一次盤塊查找時(shí)間(在磁盤中就是盤片旋轉(zhuǎn)的時(shí)間)绊起。
- B+樹的查詢效率更加穩(wěn)定
由于非終結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)燎斩，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引瘫里。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路荡碾。所有關(guān)鍵字查詢的路徑長(zhǎng)度相同坛吁，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)。
總而言之哆姻，B樹在提高了磁盤IO性能的同時(shí)并沒有解決元素遍歷的效率低下的問題。正是為了解決這個(gè)問題箕昭，B+樹應(yīng)運(yùn)而生落竹。B+樹只要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹的遍歷朱转，支持基于范圍的查詢藤为，而B樹不支持range-query這樣的操作（或者說效率太低）凉蜂。
B樹*
B*樹是B+樹的變體性誉，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針窿吩；
B+樹的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)错览，分配一個(gè)新的結(jié)點(diǎn)，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)倾哺，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針；B+樹的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)羞海，而不會(huì)影響兄弟結(jié)點(diǎn)忌愚，所以它不需要指向兄弟的指針。
B*樹的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)硕糊，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中鄙早，再在原結(jié)點(diǎn)插入關(guān)鍵字胰默，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）场斑；如果兄弟也滿了，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)碟刺，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)锁保，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針。
總結(jié)
B-樹：多路搜索樹半沽，每個(gè)結(jié)點(diǎn)存儲(chǔ)M/2到M個(gè)關(guān)鍵字爽柒，非葉子結(jié)點(diǎn)存儲(chǔ)指向關(guān)鍵字范圍的子結(jié)點(diǎn)；所有關(guān)鍵字在整顆樹中出現(xiàn)者填，且只出現(xiàn)一次浩村，非葉子結(jié)點(diǎn)可以命中；
B+樹：在B-樹基礎(chǔ)上占哟，為葉子結(jié)點(diǎn)增加鏈表指針心墅，所有關(guān)鍵字都在葉子結(jié)點(diǎn) 中出現(xiàn)，非葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)的索引榨乎；B+樹總是到葉子結(jié)點(diǎn)才命中怎燥；
B*樹：在B+樹基礎(chǔ)上，為非葉子結(jié)點(diǎn)也增加鏈表指針蜜暑，將結(jié)點(diǎn)的最低利用率從1/2提高到2/3铐姚；
借鑒于July大神的分析
