在前面章節(jié)介紹了各類二叉樹，本章節(jié)介紹下另一系列的樹結(jié)構(gòu)：B樹（Balanced tree）。

B樹

B樹是1970年 R.Bayer 和 E.mccreight 提出的一種平衡的多叉樹，是一種搜索樹，又稱B-樹。一棵m階的B樹符合如下條件：

• 1、根結(jié)點(diǎn)至少有兩個(gè)子女（要么是空樹，要么肯定有2個(gè)節(jié)點(diǎn)以上才會(huì)分裂）；
• 2、每個(gè)非根節(jié)點(diǎn)至少包含有m/2棵個(gè)關(guān)鍵字（節(jié)點(diǎn)分裂后，單節(jié)點(diǎn)最少有m/2），且最多有m-1個(gè)關(guān)鍵字（達(dá)到m個(gè)關(guān)鍵字需要分裂）；
• 3、除根結(jié)點(diǎn)以外的所有結(jié)點(diǎn)（不包括葉子結(jié)點(diǎn)）的度數(shù)正好是關(guān)鍵字總數(shù)加1；
• 4、所有的葉子結(jié)點(diǎn)都位于同一層。

B樹跟紅黑樹、平衡二叉樹不同，不需要左旋右旋的操作來保持樹的平衡，但每次數(shù)據(jù)的變更導(dǎo)致節(jié)點(diǎn)達(dá)到樹的階數(shù)時(shí)，需要從葉子節(jié)點(diǎn)開始往父節(jié)點(diǎn)延伸數(shù)據(jù)，并將當(dāng)前節(jié)點(diǎn)平均分裂為兩部分。
關(guān)于B樹的構(gòu)建過程，可以自行查看這個(gè)網(wǎng)站的動(dòng)態(tài)效果，更能幫助我們理解B樹的構(gòu)建過程：
動(dòng)態(tài)構(gòu)建B樹
從構(gòu)建過程我們知道，構(gòu)建B樹的值，可能是非葉子節(jié)點(diǎn)的關(guān)鍵字，也能是葉子節(jié)點(diǎn)。搜索過程中，從根節(jié)點(diǎn)逐層往下判斷，由于B樹的內(nèi)容是有序的，因此通過搜索樹的判斷方法，逐層往下尋找，直到找到搜索內(nèi)容。

下圖是一棵B樹示例：

B樹

B+樹

B+樹是從B樹的基礎(chǔ)上擴(kuò)展出來的，跟B樹不同的是，B+樹的值全部會(huì)出現(xiàn)在葉子節(jié)點(diǎn)，部門內(nèi)容也會(huì)在非葉子節(jié)點(diǎn)作為關(guān)鍵字存在。B+樹的搜索跟B樹不同，即使關(guān)鍵字跟搜索內(nèi)容相同，也必須繼續(xù)往下搜索（關(guān)鍵字節(jié)點(diǎn)只有索引內(nèi)容，不存索引內(nèi)容對(duì)應(yīng)的值），達(dá)到最下層葉子節(jié)點(diǎn)。
B+樹的定義基本與B-樹相同，除了：

• 1、所有關(guān)鍵字都會(huì)在葉子結(jié)點(diǎn)出現(xiàn)；
• 2、非葉子結(jié)點(diǎn)的子樹指針與關(guān)鍵字個(gè)數(shù)相同；
• 3、所有的葉子結(jié)點(diǎn)都有一個(gè)鏈指針指向相鄰的葉子節(jié)點(diǎn)；
  B+樹的動(dòng)態(tài)構(gòu)建效果可以參考這個(gè)頁面：
  動(dòng)態(tài)構(gòu)建B+樹

B+樹

B+樹的如下兩個(gè)特點(diǎn)使得B+樹特別適合用在數(shù)據(jù)庫的數(shù)據(jù)存儲(chǔ)及索引上面：

• 1 、所有內(nèi)容都在葉子節(jié)點(diǎn)：關(guān)鍵字節(jié)點(diǎn)作為索引存在，而葉子節(jié)點(diǎn)順序存儲(chǔ)所有的元素值。
• 2、葉子之間順序且指針關(guān)聯(lián)：搜索不到的情況下便于找到下一個(gè)節(jié)點(diǎn)的位置，而不需要像B樹一樣從頭開始定位，做全表掃描的時(shí)候非常方便。
  而B樹比B+樹相比的優(yōu)點(diǎn)是，由于數(shù)據(jù)可能存在所有節(jié)點(diǎn)，不需要每次都達(dá)到最深節(jié)點(diǎn)，因此訪問更迅速。

B*樹

B樹是在B+樹基礎(chǔ)上的又一種變形，相比B+樹，B樹多了如下兩個(gè)區(qū)別：

• 1、在關(guān)鍵字節(jié)點(diǎn)也包含了指向兄弟節(jié)點(diǎn)的指針。

• 2、當(dāng)一個(gè)節(jié)點(diǎn)慢了，不會(huì)馬上考慮做數(shù)據(jù)對(duì)半拆分，而是優(yōu)先考慮把數(shù)據(jù)轉(zhuǎn)移到兄弟節(jié)點(diǎn)，從而一定程度上降低了分配新節(jié)點(diǎn)的可能性，提高了空間利用率。

  
  
  B*樹

總結(jié)

最后，我們對(duì)B樹、B+樹、B*樹做一個(gè)總結(jié)。

• 1、B樹是一種M階多路搜索樹，每個(gè)節(jié)點(diǎn)都會(huì)攜帶數(shù)據(jù)，節(jié)點(diǎn)數(shù)據(jù)滿的時(shí)候做拆分。
• 2、B+樹在B樹的基礎(chǔ)上增加了數(shù)據(jù)全在葉子節(jié)點(diǎn)，以及葉子節(jié)點(diǎn)之間有鏈表的特點(diǎn)，使其非常適合用在數(shù)據(jù)庫的數(shù)據(jù)存儲(chǔ)上。
• 3、B*樹在B+樹基礎(chǔ)上增加了非葉子節(jié)點(diǎn)的鏈表以及拆分時(shí)候的優(yōu)化，進(jìn)一步提高了空間使用率。