一、引言
1970年，R.Bayer和E.mccreight提出了一種適用于外查找的樹，它是一種平衡的多叉樹，稱為B樹（或B-樹、B_樹）。我們都知道二叉查找樹的查找的時(shí)間復(fù)雜度是Ｏ(log N)，其查找效率已經(jīng)足夠高了，那為什么還有Ｂ樹和Ｂ＋樹的出現(xiàn)呢？難道它兩的時(shí)間復(fù)雜度比二叉查找樹還小嗎？
答案當(dāng)然不是，Ｂ樹和Ｂ＋樹的出現(xiàn)是因?yàn)榱硗庖粋€(gè)問題，那就是磁盤ＩＯ；眾所周知，ＩＯ操作的效率很低，那么，當(dāng)在大量數(shù)據(jù)存儲(chǔ)中，查詢時(shí)我們不能一下子將所有數(shù)據(jù)加載到內(nèi)存中，只能逐一加載磁盤頁，每個(gè)磁盤頁對(duì)應(yīng)樹的節(jié)點(diǎn)。造成大量磁盤ＩＯ操作（最壞情況下為樹的高度）。平衡二叉樹由于樹深度過大而造成磁盤IO讀寫過于頻繁，進(jìn)而導(dǎo)致效率低下。
所以，我們?yōu)榱藴p少磁盤ＩＯ的次數(shù)，就你必須降低樹的深度，將“瘦高”的樹變得“矮胖”。一個(gè)基本的想法就是：
（1）、每個(gè)節(jié)點(diǎn)存儲(chǔ)多個(gè)元素
?。?）、摒棄二叉樹結(jié)構(gòu)，采用多叉樹
這樣就引出來了一個(gè)新的查找樹結(jié)構(gòu) ——多路查找樹。 根據(jù)AVL給我們的啟發(fā)，一顆平衡多路查找樹(B~樹)自然可以使得數(shù)據(jù)的查找效率保證在O(logN)這樣的對(duì)數(shù)級(jí)別上。
【注意】：B-樹，即為B樹。因?yàn)锽樹的原英文名稱為B-tree，而國內(nèi)很多人喜歡把B-tree譯作B-樹，其實(shí)，這是個(gè)非常不好的直譯，很容易讓人產(chǎn)生誤解。如人們可能會(huì)以為B-樹是一種樹，而B樹又是一種樹。而事實(shí)上是，B-tree就是指的B樹。
二、基本概念
1、B樹：B 樹是為了磁盤或其它存儲(chǔ)設(shè)備而設(shè)計(jì)的一種多叉（下面你會(huì)看到，相對(duì)于二叉，B樹每個(gè)內(nèi)結(jié)點(diǎn)有多個(gè)分支，即多叉）平衡查找樹。與本blog之前介紹的紅黑樹很相似，但在降低磁盤I/0操作方面要更好一些。許多數(shù)據(jù)庫系統(tǒng)都一般使用B樹或者B樹的各種變形結(jié)構(gòu)。
2、對(duì)比紅黑樹： B樹與紅黑樹最大的不同在于，B樹的結(jié)點(diǎn)可以有許多子女，從幾個(gè)到幾千個(gè)。那為什么又說B樹與紅黑樹很相似呢?因?yàn)榕c紅黑樹一樣，一棵含n個(gè)結(jié)點(diǎn)的B樹的高度也為O（lgn），但可能比一棵紅黑樹的高度小許多，應(yīng)為它的分支因子比較大。所以，B樹可以在O（logn）時(shí)間內(nèi)，實(shí)現(xiàn)各種如插入（insert），刪除（delete）等動(dòng)態(tài)集合操作
三、性質(zhì)
1、性質(zhì)：B 樹又叫平衡多路查找樹。一棵m階的B 樹 (m叉樹)的特性如下：（ceil代表向上取整）
（1）根結(jié)點(diǎn)至少有2顆子樹（除非B樹只包含一個(gè)結(jié)點(diǎn)）；
（2）每個(gè)中間結(jié)點(diǎn)都包含k-1個(gè)元素（關(guān)鍵字）和k個(gè)子樹，其中 ceil(m/2) ≤ k ≤ m；
（3）每一個(gè)葉子結(jié)點(diǎn)都包含k-1個(gè)元素（關(guān)鍵字），其中 ceil（m/2）-1 ≤ k-1 ≤ m-1；
（4）所有葉結(jié)點(diǎn)在同一層上，B樹的葉結(jié)點(diǎn)可以看成一種外部結(jié)點(diǎn)，不包含任何信息；
（5）每個(gè)結(jié)點(diǎn)中的元素（關(guān)鍵字）從小到大排列，結(jié)點(diǎn)當(dāng)中k-1個(gè)元素（關(guān)鍵字）正好是k個(gè)孩子包含的元素（關(guān)鍵字）的值域劃分；
（6）每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為：
其中，Ki(1≤i≤n)為關(guān)鍵字，且Ki<Ki+1(1≤i≤n-1)，Ai(0≤i≤n)為指向子樹根結(jié)點(diǎn)的指針。且Ai所指子樹所有結(jié)點(diǎn)中的關(guān)鍵字均小于Ki+1，n為結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)，滿足ceil(m/2)-1≤n≤m-1。
2、實(shí)例：下面我們通過一個(gè)實(shí)例進(jìn)行講解：
1）結(jié)點(diǎn)的分支數(shù)等于關(guān)鍵字?jǐn)?shù)+1，最大的分支數(shù)就是B-樹的階數(shù)，因此m階的B-樹中結(jié)點(diǎn)最多有m個(gè)分支，所以可以看到，上面的一棵樹是一個(gè)3-階B-樹。??
2）因?yàn)樯厦媸且豢?階B-樹，所以非根非葉結(jié)點(diǎn)至少要有ceil(3/2)=2個(gè)分支。根結(jié)點(diǎn)可以不滿足這個(gè)條件，圖中的根結(jié)點(diǎn)有兩個(gè)分支。? ? ? ? ? ??
3）如果根結(jié)點(diǎn)中沒有關(guān)鍵字就沒有分支，此時(shí)B-樹是空樹，如果根結(jié)點(diǎn)有關(guān)鍵字，則其分支數(shù)比大于或等于2，因?yàn)榉种?shù)等于關(guān)鍵字?jǐn)?shù)+1.? ?
4）上圖中除根結(jié)點(diǎn)外，結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)至少為1，因?yàn)榉种?shù)至少為2，分支數(shù)比關(guān)鍵字?jǐn)?shù)多1，還可以看出結(jié)點(diǎn)內(nèi)關(guān)鍵字都是有序的，并且在同一層中，左邊結(jié)點(diǎn)內(nèi)所有關(guān)鍵字均小于右邊結(jié)點(diǎn)內(nèi)的關(guān)鍵字，例如，第二層上的兩個(gè)結(jié)點(diǎn)，左邊結(jié)點(diǎn)內(nèi)的關(guān)鍵字為12，23,30，他們均小于右邊結(jié)點(diǎn)內(nèi)的關(guān)鍵字46。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?B-樹一個(gè)很重要的特征是，下層結(jié)點(diǎn)內(nèi)的關(guān)鍵字取值總是落在由上層結(jié)點(diǎn)關(guān)鍵字所劃分的區(qū)間內(nèi)，具體落在哪個(gè)區(qū)間內(nèi)可以由指向它的指針看出。例如，第二層左邊數(shù)第二個(gè)的結(jié)點(diǎn)內(nèi)的關(guān)鍵字劃分了三個(gè)區(qū)間，小于23，23到30，大于30，可以看出其下層中最左邊結(jié)點(diǎn)內(nèi)的關(guān)鍵字都小于23，中間結(jié)點(diǎn)的關(guān)鍵字在23和30之間，右邊結(jié)點(diǎn)的關(guān)鍵字大于30.
5）上圖中葉子結(jié)點(diǎn)都在第四層上，代表查找不成功的位置。
四、B樹的操作
B樹可視化的網(wǎng)站：[B-Trees]：(https://www.cs.usfca.edu/~galles/visualization/BTree.html)，假定對(duì)高度為h的m階B樹進(jìn)行操作。
1、查詢：
以上圖為例：若查詢的數(shù)值為５：
第一次磁盤ＩＯ：在內(nèi)存中定位（與17、35比較），比17小，左子樹；
第二次磁盤ＩＯ：在內(nèi)存中定位（與８、12比較），比８小，左子樹；
第三次磁盤ＩＯ：在內(nèi)存中定位（與3、5比較），找到5，終止。
整個(gè)過程中，我們可以看出：比較的次數(shù)并不比二叉查找樹少，尤其適當(dāng)某一節(jié)點(diǎn)中的數(shù)據(jù)很多時(shí)，但是磁盤IO的次數(shù)卻是大大減少。比較是在內(nèi)存中進(jìn)行的，相比于磁盤IO的速度，比較的耗時(shí)幾乎可以忽略。所以當(dāng)樹的高度足夠低的話，就可以極大的提高效率。相比之下，節(jié)點(diǎn)中的元素多點(diǎn)也沒關(guān)系，僅僅是多了幾次內(nèi)存交互而已，只要不超過磁盤頁的大小即可。
2、插入：
對(duì)高度為ｋ的m階B樹，新結(jié)點(diǎn)一般是插在葉子層。通過檢索可以確定關(guān)鍵碼應(yīng)插入的結(jié)點(diǎn)位置。然后分兩種情況討論：
1、 若該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)小于m-1，則直接插入即可。
2、 若該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)等于m-1，則將引起結(jié)點(diǎn)的分裂。以中間關(guān)鍵碼為界將結(jié)點(diǎn)一分為二，產(chǎn)生一個(gè)新結(jié)點(diǎn)，并把中間關(guān)鍵碼插入到父結(jié)點(diǎn)(ｋ-1層)中
重復(fù)上述工作，最壞情況一直分裂到根結(jié)點(diǎn)，建立一個(gè)新的根結(jié)點(diǎn)，整個(gè)B樹增加一層。
例1：在下面的B樹中插入key：4
第一步：檢索key插入的節(jié)點(diǎn)位置如上圖所示，在3,5之間；
第二步：判斷節(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)：
節(jié)點(diǎn)3，5已經(jīng)是兩元素節(jié)點(diǎn)，無法再增加。父親節(jié)點(diǎn) 2， 6 也是兩元素節(jié)點(diǎn)，也無法再增加。根節(jié)點(diǎn)9是單元素節(jié)點(diǎn)，可以升級(jí)為兩元素節(jié)點(diǎn)。；
第三步：結(jié)點(diǎn)分裂：
拆分節(jié)點(diǎn)3，5與節(jié)點(diǎn)2，6，讓根節(jié)點(diǎn)9升級(jí)為兩元素節(jié)點(diǎn)4，9。節(jié)點(diǎn)6獨(dú)立為根節(jié)點(diǎn)的第二個(gè)孩子。
最終結(jié)果如下圖：雖然插入比較麻煩，但是這也能確保Ｂ樹是一個(gè)自平衡的樹。
例2：我們以關(guān)鍵字序列{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}創(chuàng)建一棵5階B-樹，我們將詳細(xì)體會(huì)B-樹的插入過程。
（1）確定結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)范圍
由于題目要求建立5階B-樹，因此關(guān)鍵字的個(gè)數(shù)范圍為2～4
（2）根結(jié)點(diǎn)最多可以容納4個(gè)關(guān)鍵字，依次插入關(guān)鍵字1、2、6、7后的B-樹如下圖所示：
（3）當(dāng)插入關(guān)鍵字11的時(shí)候，發(fā)現(xiàn)此時(shí)結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)變?yōu)?，超出范圍，需要拆分，去關(guān)鍵字?jǐn)?shù)組中的中間位置，也就是k[3]=6，作為一個(gè)獨(dú)立的結(jié)點(diǎn)，即新的根結(jié)點(diǎn)，將關(guān)鍵字6左、右關(guān)鍵字分別做成兩個(gè)結(jié)點(diǎn)，作為新根結(jié)點(diǎn)的兩個(gè)分支，此時(shí)樹如下圖所示：
（4）新關(guān)鍵字總是插在葉子結(jié)點(diǎn)上，插入關(guān)鍵字4、8、13之后樹為：
（5）關(guān)鍵字10需要插入在關(guān)鍵字8和11之間，此時(shí)又會(huì)出現(xiàn)關(guān)鍵字個(gè)數(shù)超出范圍的情況，因此需要拆分。拆分時(shí)需要將關(guān)鍵字10納入根結(jié)點(diǎn)中，并將10左右的關(guān)鍵字做成兩個(gè)新的結(jié)點(diǎn)連在根結(jié)點(diǎn)上。插入關(guān)鍵字10并經(jīng)過拆分操作后的B-樹如下圖：
（6）插入關(guān)鍵字5、17、9、16之后的B-樹如圖所示：
（7）關(guān)鍵字20插入在關(guān)鍵字17以后，此時(shí)會(huì)造成結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)超出范圍，需要拆分，方法同上，樹為：
（8）按照上述步驟依次插入關(guān)鍵字3、12、14、18、19之后B-樹如下圖所示：
（9）插入最后一個(gè)關(guān)鍵字15，15應(yīng)該插入在14之后，此時(shí)會(huì)出現(xiàn)關(guān)鍵字個(gè)數(shù)超出范圍的情況，則需要進(jìn)行拆分，將13并入根結(jié)點(diǎn)，13并入根結(jié)點(diǎn)之后，又使得根結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)超出范圍，需要再次進(jìn)行拆分，將10作為新的根結(jié)點(diǎn)，并將10左、右關(guān)鍵字做成兩個(gè)新結(jié)點(diǎn)連接到新根結(jié)點(diǎn)的指針上，這種插入一個(gè)關(guān)鍵字之后出現(xiàn)多次拆分的情況稱為連鎖反應(yīng)，最終形成的B-樹如下圖所示：
3、刪除：
對(duì)于B-樹關(guān)鍵字的刪除，需要找到待刪除的關(guān)鍵字，在結(jié)點(diǎn)中刪除關(guān)鍵字的過程也有可能破壞B-樹的特性，如舊關(guān)鍵字的刪除可能使得結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)少于規(guī)定個(gè)數(shù)，這是可能需要向其兄弟結(jié)點(diǎn)借關(guān)鍵字或者和其孩子結(jié)點(diǎn)進(jìn)行關(guān)鍵字的交換，也可能需要進(jìn)行結(jié)點(diǎn)的合并，其中，和當(dāng)前結(jié)點(diǎn)的孩子進(jìn)行關(guān)鍵字交換的操作可以保證刪除操作總是發(fā)生在終端結(jié)點(diǎn)上。
例1：下面舉一個(gè)簡單的例子：刪除元素11.
第一步：判斷該元素是否在葉子結(jié)點(diǎn)上。
該元素在葉子節(jié)點(diǎn)上，可以直接刪去，但是刪除之后，中間節(jié)點(diǎn)12只有一個(gè)孩子，不符合B樹的定義：每個(gè)中間節(jié)點(diǎn)都包含k個(gè)孩子，（其中 ceil（m/2） <= k <= m）所以需要調(diào)整；
第二步：判斷其左右兄弟結(jié)點(diǎn)中有“多余”的關(guān)鍵字，即：原關(guān)鍵字個(gè)數(shù)n>=ceil(m/2) - 1；
顯然結(jié)點(diǎn)11的右兄弟節(jié)點(diǎn)中有多余的關(guān)鍵字。那么可將右兄弟結(jié)點(diǎn)中最小關(guān)鍵字上移至雙親結(jié)點(diǎn)。而將雙親結(jié)點(diǎn)中小于該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點(diǎn)中即可。
例2：我們用剛剛生成的B-樹作為例子，一次刪除8、16、15、4這4個(gè)關(guān)鍵字。
（1）刪除關(guān)鍵字8、16。關(guān)鍵字8在終端結(jié)點(diǎn)上，并且刪除后其所在結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)不會(huì)少于2，因此可以直接刪除。關(guān)鍵字16不在終端結(jié)點(diǎn)上，但是可以用17來覆蓋16，然后將原來的17刪除掉，這就是上面提到的和孩子結(jié)點(diǎn)進(jìn)行關(guān)鍵字交換的操作。這里不能用15和16進(jìn)行關(guān)鍵字交換，因?yàn)檫@樣會(huì)導(dǎo)致15所在結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)小于2。因此，刪除8和16之后B-樹如下圖所示：
（2）刪除關(guān)鍵字15，15雖然也在終端結(jié)點(diǎn)上，但是不能直接刪除，因?yàn)閯h除后當(dāng)前結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)小于2。這是需要向其兄弟結(jié)點(diǎn)借關(guān)鍵字，顯然應(yīng)該向其右兄弟來借關(guān)鍵字，因?yàn)樽笮值艿年P(guān)鍵字個(gè)數(shù)已經(jīng)是下限2.借關(guān)鍵字不能直接將18移到15所在的結(jié)點(diǎn)上，因?yàn)檫@樣會(huì)使得15所在的結(jié)點(diǎn)上出現(xiàn)比17大的關(guān)鍵字，所以正確的借法應(yīng)該是先用17覆蓋15，在用18覆蓋原來的17，最后刪除原來的18，刪除關(guān)鍵字15后的B-樹如下圖所示：
（3）刪除關(guān)鍵字4，4在終端結(jié)點(diǎn)上，但是此時(shí)4所在的結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)已經(jīng)到下限，需要借關(guān)鍵字，不過可以看到其左右兄弟結(jié)點(diǎn)已經(jīng)沒有多余的關(guān)鍵字可借。所以就需要進(jìn)行關(guān)鍵字的合并?？梢韵葘㈥P(guān)鍵字4刪除，然后將關(guān)鍵字5、6、7、9進(jìn)行合并作為一個(gè)結(jié)點(diǎn)鏈接在關(guān)鍵字3右邊的指針上，也可以將關(guān)鍵字1、2、3、5合并作為一個(gè)結(jié)點(diǎn)鏈接在關(guān)鍵字6左邊的指針上，如下圖所示：
顯然上述兩種情況下都不滿足B-樹的規(guī)定，即出現(xiàn)了非根的雙分支結(jié)點(diǎn)，需要繼續(xù)進(jìn)行合并，合并后的B-樹如下圖所示：
有時(shí)候刪除的結(jié)點(diǎn)不在終端結(jié)點(diǎn)上，我們首先需要將其轉(zhuǎn)化到終端結(jié)點(diǎn)上，然后再按上面的各種情況進(jìn)行刪除。在講述這種情況下的刪除方法之前，要引入一個(gè)相鄰關(guān)鍵字的概念，對(duì)于不在終端結(jié)點(diǎn)的關(guān)鍵字a，它的相鄰關(guān)鍵字為其左子樹中值最大的關(guān)鍵字或者其右子樹中值最小的關(guān)鍵字。找a的相鄰關(guān)鍵字的方法為：沿著a的左指針來到其子樹根結(jié)點(diǎn)，然后沿著根結(jié)點(diǎn)中最右端的關(guān)鍵字的右指針往下走，用同樣的方法一直走到葉結(jié)點(diǎn)上，葉結(jié)點(diǎn)上的最右端的關(guān)鍵字即為a的相鄰關(guān)鍵字（這里找的是a左邊的相鄰關(guān)鍵字，我們可以用同樣的思路找到a右邊的相鄰關(guān)鍵字）?？梢钥吹较聢D中a的相鄰關(guān)鍵字是d和e，要?jiǎng)h除關(guān)鍵字a，可以用d來取代a，然后按照上面的情況刪除葉子結(jié)點(diǎn)上的d即可。
【注意】
?、佟樹主要用于文件系統(tǒng)以及部分?jǐn)?shù)據(jù)庫索引，例如： MongoDB。而大部分關(guān)系數(shù)據(jù)庫則使用B+樹做索引，例如：mysql數(shù)據(jù)庫；
?、?、從查找效率考慮一般要求B樹的階數(shù)m >= 3;
?、?、B-樹上算法的執(zhí)行時(shí)間主要由讀、寫磁盤的次數(shù)來決定，故一次I/O操作應(yīng)讀寫盡可能多的信息。因此B-樹的結(jié)點(diǎn)規(guī)模一般以一個(gè)磁盤頁為單位。一個(gè)結(jié)點(diǎn)包含的關(guān)鍵字及其孩子個(gè)數(shù)取決于磁盤頁的大小。
五、B-樹的應(yīng)用
為了將大型數(shù)據(jù)庫文件存儲(chǔ)在硬盤上，以減少訪問硬盤次數(shù)為目的，在此提出了一種平衡多路查找樹——B-樹結(jié)構(gòu)。由其性能分析可知它的檢索效率是相當(dāng)高的 為了提高 B-樹性能’還有很多種B-樹的變型，力圖對(duì)B-樹進(jìn)行改進(jìn)，比如B+樹。
