首先糾正下：B樹(shù)也叫B-tree(B-樹(shù))【B-不可以讀B減樹(shù) 應(yīng)該是B-tree】锰什，所以B樹(shù)和B-tree迈螟，B-樹(shù)是同一個(gè)東西弄息，只是不用的叫法 本文統(tǒng)一叫B-樹(shù)
回歸正題海渊，先各自介紹下B樹(shù)和B+樹(shù)

B-樹(shù)：平衡多路查找樹(shù)绵疲，一顆度為m的B-樹(shù)稱為m階B-樹(shù)。一個(gè)節(jié)點(diǎn)有k個(gè)孩子時(shí)切省，必有k-1個(gè)關(guān)鍵字才能將子樹(shù)中所有關(guān)鍵字劃分為k個(gè)子集最岗。B-樹(shù)中所有孩子節(jié)點(diǎn)最大值稱為B-樹(shù)的階，通常用m表示朝捆。從查找效率考慮般渡，一般要求m>=3。
B-樹(shù)滿足一下要求：
1.樹(shù)中的每個(gè)節(jié)點(diǎn)最多含有k個(gè)孩子，即滿足m/2≤k≥m
2.除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外驯用，其他每個(gè)節(jié)點(diǎn)至少有m/2個(gè)孩子
3.根節(jié)點(diǎn)至少有兩個(gè)孩子
4.所有的子節(jié)點(diǎn)都出現(xiàn)在同一層
5.每個(gè)節(jié)點(diǎn)中的元素從小到大排序
6.中間節(jié)點(diǎn)有k-1個(gè)關(guān)鍵字和k個(gè)孩子
B-樹(shù)的基本操作
1.查詢

image.png

如上是一個(gè)三階B-樹(shù)
假設(shè)我們要查詢8是否在B-樹(shù)中
1.從根節(jié)點(diǎn)出發(fā)脸秽，發(fā)現(xiàn)根節(jié)點(diǎn)關(guān)鍵字是9,8＜9往樹(shù)的左邊走，進(jìn)入節(jié)點(diǎn)（2,6）
2.發(fā)現(xiàn)節(jié)點(diǎn)（2,6）有兩個(gè)關(guān)鍵字蝴乔，其中 8＞6记餐，往樹(shù)的右邊走，進(jìn)入（8）節(jié)點(diǎn)
3.發(fā)現(xiàn)（8）節(jié)點(diǎn)有關(guān)鍵字8薇正，返回
說(shuō)明下片酝，在B-樹(shù)中查找節(jié)點(diǎn)是在磁盤(pán)上進(jìn)行的
在節(jié)點(diǎn)中查找關(guān)鍵字是將節(jié)點(diǎn)中的信息讀到內(nèi)存中，在利用順序查找或者二分法查找
在內(nèi)存中的效率要高與磁盤(pán)的效率
B-樹(shù)的插入
1.通過(guò)上面的查找算法找到插入的位置
如果在B-樹(shù)中找到關(guān)鍵字則直接返回挖腰，否會(huì)報(bào)錯(cuò)
2.判斷查找到的節(jié)點(diǎn)上面的關(guān)鍵字是否滿足n≤m-1雕沿，不滿足就要對(duì)節(jié)點(diǎn)進(jìn)行分裂
3.分裂的方法是：產(chǎn)生一個(gè)新的節(jié)點(diǎn)，把原節(jié)點(diǎn)上的關(guān)鍵字和要插入的關(guān)鍵字進(jìn)行排序猴仑，然后從中間關(guān)鍵字分成兩部分审轮，左邊部分的關(guān)鍵字放在原節(jié)點(diǎn)中，右邊的關(guān)鍵字放在新的節(jié)點(diǎn)中辽俗，中間節(jié)點(diǎn)放到父節(jié)點(diǎn)中疾渣，如果父節(jié)點(diǎn)還是不滿足條件，就繼續(xù)分裂

下面我們來(lái)舉例說(shuō)明崖飘，首先假設(shè)這個(gè)B-樹(shù)的階為：3榴捡。樹(shù)的初始化時(shí)如下：

這里寫(xiě)圖片描述

首先，我需要插入一個(gè)關(guān)鍵字：30朱浴，可以得到如下的結(jié)果：

這里寫(xiě)圖片描述

再插入26薄疚，得到如下的結(jié)果：

這里寫(xiě)圖片描述

OK，此時(shí)如圖所示赊琳，在插入的那個(gè)終端結(jié)點(diǎn)中，它的關(guān)鍵字?jǐn)?shù)已經(jīng)超過(guò)了m-1=2砰碴，所以我們需要對(duì)結(jié)點(diǎn)進(jìn)分裂躏筏，所以我們先對(duì)關(guān)鍵字排序，得到：26 30 37 呈枉，所以它的左部分為（不包括中間值）：26趁尼，中間值為：30，右部為：37猖辫，左部放在原來(lái)的結(jié)點(diǎn)酥泞，右部放入新的結(jié)點(diǎn)，而中間值則插入到父結(jié)點(diǎn)啃憎，并且父結(jié)點(diǎn)會(huì)產(chǎn)生一個(gè)新的指針芝囤，指向新的結(jié)點(diǎn)的位置，如下圖所示：

這里寫(xiě)圖片描述

OK，然后我們繼續(xù)插入新的關(guān)鍵字：85悯姊，得到如下圖結(jié)果：

這里寫(xiě)圖片描述

正如圖所示羡藐，我需要對(duì)剛才插入的那個(gè)結(jié)點(diǎn)進(jìn)行“分裂”操作，操作方式和之前的一樣悯许，得到的結(jié)果如下：

這里寫(xiě)圖片描述

哦仆嗦，當(dāng)我們分裂完后，突然發(fā)現(xiàn)之前的那個(gè)結(jié)點(diǎn)的父親結(jié)點(diǎn)的度為4了先壕，說(shuō)明它的關(guān)鍵字?jǐn)?shù)超過(guò)了m-1瘩扼，所以需要對(duì)其父結(jié)點(diǎn)進(jìn)行“分裂”操作，得到如下的結(jié)果：

這里寫(xiě)圖片描述

好垃僚，我們繼續(xù)插入一個(gè)新的關(guān)鍵字：7集绰，得到如下結(jié)果：

這里寫(xiě)圖片描述

同樣，需要對(duì)新的結(jié)點(diǎn)進(jìn)行分裂操作冈在，得到如下的結(jié)果：

這里寫(xiě)圖片描述

到了這里倒慧，我就需要繼續(xù)對(duì)我們的父親結(jié)點(diǎn)進(jìn)行分裂操作，因?yàn)樗年P(guān)鍵字?jǐn)?shù)超過(guò)了：m-1.

這里寫(xiě)圖片描述

哦包券，終于遇到這種情況了纫谅，我們的根結(jié)點(diǎn)出現(xiàn)了關(guān)鍵子數(shù)量超過(guò)m-1的情況了，這個(gè)時(shí)候我們需要對(duì)父親結(jié)點(diǎn)進(jìn)行分列操作溅固，但是根結(jié)點(diǎn)沒(méi)父親啊付秕，所以我們需要重新創(chuàng)建根結(jié)點(diǎn)了。

這里寫(xiě)圖片描述

好了侍郭，到了這里我們也知道怎么進(jìn)行B-樹(shù)的插入操作询吴。
B-樹(shù)的刪除操作

B-樹(shù)的刪除操作同樣是分為兩個(gè)步驟：

1. 利用前述的B-樹(shù)的查找算法找出該關(guān)鍵字所在的結(jié)點(diǎn)戒悠。然后根據(jù) k（需要?jiǎng)h除的關(guān)鍵字）所在結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)有不同的處理方法令哟。如果沒(méi)有找到，則直接返回绵估。
2. 若該結(jié)點(diǎn)為非葉結(jié)點(diǎn)爆捞，且被刪關(guān)鍵字為該結(jié)點(diǎn)中第i個(gè)關(guān)鍵字key[i]奉瘤，則可從指針son[i]所指的子樹(shù)中找出最小關(guān)鍵字Y，代替key[i]的位置煮甥，然后在葉結(jié)點(diǎn)中刪去Y盗温。

如果是葉子結(jié)點(diǎn)的話，需要分為下面三種情況進(jìn)行刪除成肘。

• 如果被刪關(guān)鍵字所在結(jié)點(diǎn)的原關(guān)鍵字個(gè)數(shù)n>=[m/2] ( 上取整）卖局，說(shuō)明刪去該關(guān)鍵字后該結(jié)點(diǎn)仍滿足B-樹(shù)的定義。這種情況最為簡(jiǎn)單双霍，只需刪除對(duì)應(yīng)的關(guān)鍵字：k和指針：A 即可砚偶。
• 如果被刪關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)n等于( 上取整）[ m/2 ]-1批销，說(shuō)明刪去該關(guān)鍵字后該結(jié)點(diǎn)將不滿足B-樹(shù)的定義，需要調(diào)整蟹演。

調(diào)整過(guò)程為：如果其左右兄弟結(jié)點(diǎn)中有“多余”的關(guān)鍵字,即與該結(jié)點(diǎn)相鄰的右兄弟(或左兄弟)結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目大于( 上取整）[m/2]-1风钻。則可將右兄弟(或左兄弟)結(jié)點(diǎn)中最小關(guān)鍵字(或最大的關(guān)鍵字)上移至雙親結(jié)點(diǎn)。而將雙親結(jié)點(diǎn)中芯魄搿（大）于該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點(diǎn)中骡技。

• 被刪關(guān)鍵字所在結(jié)點(diǎn)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目均等于（上取整）[m/2]-1。假設(shè)該結(jié)點(diǎn)有右兄弟羞反，且其右兄弟結(jié)點(diǎn)地址由雙親結(jié)點(diǎn)中的指針Ai所指布朦，則在刪去關(guān)鍵字之后，它所在結(jié)點(diǎn)中剩余的關(guān)鍵字和指針昼窗，加上雙親結(jié)點(diǎn)中的關(guān)鍵字Ki一起是趴，合并到 Ai所指兄弟結(jié)點(diǎn)中(若沒(méi)有右兄弟，則合并至左兄弟結(jié)點(diǎn)中)澄惊。

下面唆途，我們給出刪除葉子結(jié)點(diǎn)的三種情況：
第一種：關(guān)鍵字的數(shù)不小于（上取整）[m/2]，如下圖刪除關(guān)鍵字：12

這里寫(xiě)圖片描述

刪除12后的結(jié)果如下掸驱，只是簡(jiǎn)單的刪除關(guān)鍵字12和其對(duì)應(yīng)的指針肛搬。

這里寫(xiě)圖片描述

第二種：關(guān)鍵字個(gè)數(shù)n等于( 上取整）[ m/2 ]-1，而且該結(jié)點(diǎn)相鄰的右兄弟(或左兄弟)結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目大于( 上取整）[m/2]-1毕贼。

這里寫(xiě)圖片描述

如上圖温赔，所示，我們需要?jiǎng)h除50這個(gè)關(guān)鍵字鬼癣，所以我們需要把50的右兄弟中最小的關(guān)鍵字：61上移到其父結(jié)點(diǎn)陶贼，然后替換小于61的關(guān)鍵字53的位置，53則放至50的結(jié)點(diǎn)中待秃。然后拜秧，我們可以得到如下的結(jié)果：

這里寫(xiě)圖片描述

第三種：關(guān)鍵字個(gè)數(shù)n等于( 上取整）[ m/2 ]-1，而且被刪關(guān)鍵字所在結(jié)點(diǎn)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目均等于（上取整）[m/2]-1

這里寫(xiě)圖片描述

如上圖所示章郁，我們需要?jiǎng)h除53腹纳，那么我們就要把53所在的結(jié)點(diǎn)其他關(guān)鍵字（這里沒(méi)有其他關(guān)鍵字了）和父親結(jié)點(diǎn)的61這個(gè)關(guān)鍵字一起合并到70這個(gè)關(guān)鍵字所占的結(jié)點(diǎn)。得到如下所示的結(jié)果：

這里寫(xiě)圖片描述

Ok驱犹，我已經(jīng)分別對(duì)上述的四種刪除的情況都做了舉例，大家如果還有什么不清楚的足画，可以看看代碼雄驹，估計(jì)就可以明白了

；

B+樹(shù)

   B+樹(shù)是B-樹(shù)的變體淹辞，也是一種多路搜索樹(shù)：

   1.其定義基本與B-樹(shù)同医舆，除了：

   2.非葉子結(jié)點(diǎn)的子樹(shù)指針與關(guān)鍵字個(gè)數(shù)相同；

   3.非葉子結(jié)點(diǎn)的子樹(shù)指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹(shù)

（B-樹(shù)是開(kāi)區(qū)間）蔬将；

   5.為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針爷速；

   6.所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)；

   如：（M=3）

image

B+的搜索與B-樹(shù)也基本相同霞怀，區(qū)別是B+樹(shù)只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹(shù)可以在

非葉子結(jié)點(diǎn)命中）惫东，其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找；

   B+的特性：

   1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（稠密索引）毙石，且鏈表中的關(guān)鍵字恰好

是有序的廉沮；

   2.不可能在非葉子結(jié)點(diǎn)命中；

   3.非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引）徐矩，葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)

（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層滞时；

   4.更適合文件索引系統(tǒng)；

B樹(shù)*

   是B+樹(shù)的變體滤灯，在B+樹(shù)的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針坪稽；

image

B樹(shù)定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)M，即塊的最低使用率為2/3

（代替B+樹(shù)的1/2）鳞骤；

   B+樹(shù)的分裂：當(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+樹(shù)的分裂只影響原結(jié)點(diǎn)和父

結(jié)點(diǎn)，而不會(huì)影響兄弟結(jié)點(diǎn)拂募，所以它不需要指向兄弟的指針庭猩；

   B*樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，如果它的下一個(gè)兄弟結(jié)點(diǎ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)的指針优炬；

   所以，B*樹(shù)分配新結(jié)點(diǎn)的概率比B+樹(shù)要低厅贪，空間使用率更高蠢护；

小結(jié)

   B-樹(shù)：多路搜索樹(shù)，每個(gè)結(jié)點(diǎn)存儲(chǔ)M/2到M個(gè)關(guān)鍵字养涮，非葉子結(jié)點(diǎn)存儲(chǔ)指向關(guān)鍵

字范圍的子結(jié)點(diǎn)葵硕；

   所有關(guān)鍵字在整顆樹(shù)中出現(xiàn)眉抬，且只出現(xiàn)一次，非葉子結(jié)點(diǎn)可以命中懈凹；

   B+樹(shù)：在B-樹(shù)基礎(chǔ)上蜀变，為葉子結(jié)點(diǎn)增加鏈表指針，所有關(guān)鍵字都在葉子結(jié)點(diǎn)

中出現(xiàn)介评，非葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)的索引库北；B+樹(shù)總是到葉子結(jié)點(diǎn)才命中；

   B*樹(shù)：在B+樹(shù)基礎(chǔ)上威沫，為非葉子結(jié)點(diǎn)也增加鏈表指針贤惯，將結(jié)點(diǎn)的最低利用率

從1/2提高到2/3；