在前面章節(jié)介紹了各類二叉樹，本章節(jié)介紹下另一系列的樹結(jié)構(gòu)：B樹（Balanced tree）。
B樹
B樹是1970年 R.Bayer 和 E.mccreight 提出的一種平衡的多叉樹筑煮，是一種搜索樹，又稱B-樹粤蝎。一棵m階的B樹符合如下條件：
- 1真仲、根結(jié)點至少有兩個子女（要么是空樹，要么肯定有2個節(jié)點以上才會分裂）初澎；
- 2秸应、每個非根節(jié)點至少包含有m/2棵個關(guān)鍵字（節(jié)點分裂后，單節(jié)點最少有m/2）碑宴，且最多有m-1個關(guān)鍵字（達到m個關(guān)鍵字需要分裂）软啼；
- 3、除根結(jié)點以外的所有結(jié)點（不包括葉子結(jié)點）的度數(shù)正好是關(guān)鍵字總數(shù)加1延柠；
- 4祸挪、所有的葉子結(jié)點都位于同一層。
B樹跟紅黑樹贞间、平衡二叉樹不同贿条，不需要左旋右旋的操作來保持樹的平衡，但每次數(shù)據(jù)的變更導致節(jié)點達到樹的階數(shù)時增热，需要從葉子節(jié)點開始往父節(jié)點延伸數(shù)據(jù)整以，并將當前節(jié)點平均分裂為兩部分。
關(guān)于B樹的構(gòu)建過程峻仇，可以自行查看這個網(wǎng)站的動態(tài)效果公黑，更能幫助我們理解B樹的構(gòu)建過程：
動態(tài)構(gòu)建B樹
從構(gòu)建過程我們知道，構(gòu)建B樹的值，可能是非葉子節(jié)點的關(guān)鍵字帆调，也能是葉子節(jié)點奠骄。搜索過程中，從根節(jié)點逐層往下判斷番刊，由于B樹的內(nèi)容是有序的，因此通過搜索樹的判斷方法影锈，逐層往下尋找芹务，直到找到搜索內(nèi)容。
下圖是一棵B樹示例：
B+樹
B+樹是從B樹的基礎(chǔ)上擴展出來的鸭廷，跟B樹不同的是枣抱，B+樹的值全部會出現(xiàn)在葉子節(jié)點，部門內(nèi)容也會在非葉子節(jié)點作為關(guān)鍵字存在辆床。B+樹的搜索跟B樹不同佳晶，即使關(guān)鍵字跟搜索內(nèi)容相同，也必須繼續(xù)往下搜索（關(guān)鍵字節(jié)點只有索引內(nèi)容讼载，不存索引內(nèi)容對應(yīng)的值）轿秧，達到最下層葉子節(jié)點。
B+樹的定義基本與B-樹相同咨堤，除了：
- 1菇篡、所有關(guān)鍵字都會在葉子結(jié)點出現(xiàn)；
- 2一喘、非葉子結(jié)點的子樹指針與關(guān)鍵字個數(shù)相同驱还；
- 3、所有的葉子結(jié)點都有一個鏈指針指向相鄰的葉子節(jié)點凸克；
B+樹的動態(tài)構(gòu)建效果可以參考這個頁面：
動態(tài)構(gòu)建B+樹
B+樹的如下兩個特點使得B+樹特別適合用在數(shù)據(jù)庫的數(shù)據(jù)存儲及索引上面：
- 1 议蟆、所有內(nèi)容都在葉子節(jié)點：關(guān)鍵字節(jié)點作為索引存在，而葉子節(jié)點順序存儲所有的元素值萎战。
- 2咐容、葉子之間順序且指針關(guān)聯(lián)：搜索不到的情況下便于找到下一個節(jié)點的位置，而不需要像B樹一樣從頭開始定位撞鹉，做全表掃描的時候非常方便疟丙。
而B樹比B+樹相比的優(yōu)點是，由于數(shù)據(jù)可能存在所有節(jié)點鸟雏，不需要每次都達到最深節(jié)點享郊，因此訪問更迅速。
B*樹
B樹是在B+樹基礎(chǔ)上的又一種變形孝鹊，相比B+樹炊琉，B樹多了如下兩個區(qū)別：
- 1、在關(guān)鍵字節(jié)點也包含了指向兄弟節(jié)點的指針。
-
2苔咪、當一個節(jié)點慢了锰悼，不會馬上考慮做數(shù)據(jù)對半拆分，而是優(yōu)先考慮把數(shù)據(jù)轉(zhuǎn)移到兄弟節(jié)點团赏，從而一定程度上降低了分配新節(jié)點的可能性箕般，提高了空間利用率。
B*樹
總結(jié)
最后舔清，我們對B樹丝里、B+樹、B*樹做一個總結(jié)体谒。
- 1杯聚、B樹是一種M階多路搜索樹，每個節(jié)點都會攜帶數(shù)據(jù)抒痒，節(jié)點數(shù)據(jù)滿的時候做拆分幌绍。
- 2、B+樹在B樹的基礎(chǔ)上增加了數(shù)據(jù)全在葉子節(jié)點故响，以及葉子節(jié)點之間有鏈表的特點傀广，使其非常適合用在數(shù)據(jù)庫的數(shù)據(jù)存儲上。
- 3被去、B*樹在B+樹基礎(chǔ)上增加了非葉子節(jié)點的鏈表以及拆分時候的優(yōu)化主儡，進一步提高了空間使用率。
