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