一個m階的B-樹具有如下幾個特征：
- 根節(jié)點至少有兩個子女
- 每個中間節(jié)點都包含k-1個元素和k個孩子，其中m/2<=k<=m
- 每個葉子節(jié)點都包含k-1個元素，其中m/2<=k<=m
- 所有的葉子結(jié)點都位于同一層
- 每個節(jié)點中的元素從小到大排序，節(jié)點當中k-1個元素正好是K個漢子包含的元素的值域劃分。
例：3階的B-樹
3.png
B-樹查詢的過程，假如我們要查詢的數(shù)值是5
第一次磁盤IO:
4.png
在內(nèi)存中定位（和9比較）：
5.png
第二次磁盤IO
6.png
在內(nèi)存中定位（和2、6比較）：
7.png
第3次磁盤IO：
8.png
在內(nèi)存中定位（和3、5比較）
9.png
通過整個流程我們可以看出，B-樹在查詢中的比較次數(shù)其實不比二叉查找樹少，尤其當單一節(jié)點中的元素數(shù)量很多時?？墒窍啾却疟PIO的速度，內(nèi)存中比較耗時幾乎可以忽略。所以只要樹的高度足夠低，IO次數(shù)足夠少，就可以提升查找性能。相比之下節(jié)點內(nèi)部元素多一些也沒有關(guān)系，僅僅是多了幾次內(nèi)存交互，只要不超過磁盤頁的大小即可。這就是B-樹的優(yōu)勢之一。
插入節(jié)點
B-樹插入新節(jié)點的過程比較復雜，而且分成很多種情況。例如插入值4
自頂向下查找4的節(jié)點位置，發(fā)現(xiàn)4應當插入到節(jié)點元素3，5之間
10.png
節(jié)點3，5已經(jīng)是兩元素節(jié)點，無法再增加。父親節(jié)點2，6也是兩元素節(jié)點，也無法再增加。根節(jié)點9是單元素節(jié)點，可以升級為兩元素節(jié)點。于是拆分節(jié)點3，5與節(jié)點2，6，讓根節(jié)點9升級為兩元素節(jié)點4，9。節(jié)點6獨立為根節(jié)點的第二個孩子。
1.png
B-樹能夠始終維持多路平衡，這也是B-樹的一大優(yōu)勢：自平衡。
刪除節(jié)點
比如刪除元素11
2.png
刪除11后，節(jié)點12只有一個孩子，不符合B樹規(guī)范。因此找出11，12，15三個節(jié)點的中位數(shù)13，取代節(jié)點12，而節(jié)點12自身下移成為第一個孩子（這個過程稱為左旋）
3.png
4.png
B-樹主要應用于文件系統(tǒng)以及部分數(shù)據(jù)庫索引，比如著名的非關(guān)系型數(shù)據(jù)庫MongoDB.
而大部分關(guān)系型數(shù)據(jù)庫，比如Mysql,則使用B+樹作為索引。
