大家好，我是“Stephen·謝”，之前有講到樹（Tree）的概念，還演示了二叉查找樹和紅黑樹這兩種經(jīng)典樹的相關(guān)內(nèi)容，其中引入了一個“自平衡”的概念，這個自平衡特性對樹結(jié)構(gòu)而言相當(dāng)?shù)闹匾?，它是使我們的樹結(jié)構(gòu)變得實用方便的重要手段。由此，開始下面B樹（B-Tree即Balance Tree）的講解。
首先補充一點，標(biāo)題中的"B-樹"就是“B樹”，它們都是B-Tree的翻譯，里面不是減號-，是連接符-。因為有人把B-Tree讀成"B-樹"，讓人誤以為“B樹”和"B-樹"是兩種樹，實際上兩者都是同一種樹。還有，大家在讀的時候千萬不要讀成“B減樹”，讀成“B樹”就行了，不然就外行了。
下面開始今天正文，我們依然從數(shù)據(jù)庫的檢索開始，我們知道數(shù)據(jù)庫的索引是使用樹結(jié)構(gòu)來實現(xiàn)的，是因為樹的查詢效率高，而且還可以保持有序的狀態(tài)。上篇中講到的二叉查找樹效率就很高，但是為什么沒有使用二叉查找樹來實現(xiàn)索引呢？其實從算法邏輯上講，二叉查找樹的查找次數(shù)和比較次數(shù)都是最小的，但是我們必須還要考慮一個現(xiàn)實問題：磁盤的IO（磁盤讀寫）。
數(shù)據(jù)庫的索引是存儲在磁盤上的，當(dāng)數(shù)據(jù)量非常大的時候，索引的大小可能有幾個G甚至更多，當(dāng)我們利用索引查詢的時候顯然不可能將整個索引全部加載到內(nèi)存，正常的操作都是逐一加載每一個磁盤頁，這里的磁盤頁就對應(yīng)著索引樹的節(jié)點。
我們?nèi)绻枚娌檎覙渥鏊饕Y(jié)構(gòu)，查找情形是什么樣子的呢？假設(shè)樹的高度是4，要查找的值是10。
磁盤IO的次是4次，即樹的高度，最壞的情況就是磁盤IO的次數(shù)等于索引樹的高度。既然如此，為了減少磁盤IO的次數(shù)，我們就需要把原來的“瘦高”樹結(jié)構(gòu)變得“矮胖”，這就是本文所要說的B-樹的特征之一。
B-樹（以下都稱作B樹）是一種多路平衡查找樹，它的每個節(jié)點最多包含k個孩子，其中，k被稱為B數(shù)的階，k的大小取決于磁盤頁的大小。
一個m階的B樹具備如下幾個特征：
1、根節(jié)點至少有兩個子女；
2、每個中間節(jié)點都包含k-1個元素和k個孩子，其中m/2<=k<=m；
3、每個葉子節(jié)點都包含k-1個元素，其中m/2<=k<=m；
4、所有的葉子節(jié)點都位于同一層；
5、每個節(jié)點中的元素從小到大排列，節(jié)點當(dāng)中k-1個元素正好是k個孩子包含的元素的值域劃分。
我們以一個3階B樹為例來看一下B樹的結(jié)構(gòu)，樹中的具體元素和上面的二叉查找樹是一樣的。
我們來看（2，6）節(jié)點，該節(jié)點有兩個元素2和6，又有三個孩子1，（3，5），8。其中1小于元素2，（3，5）在元素2，6之間，8大于元素6，符合上面的幾條規(guī)則。
接下來我們來看一下B樹的查詢過程，看看會帶來什么效果，假如我們要查詢的數(shù)值是5
從上面我們看出，其實B樹在查詢中的比較次數(shù)并不比二叉查找樹少，尤其當(dāng)單一節(jié)點中的元素數(shù)量很多時?？墒窍鄬Υ疟PIO的速度，在內(nèi)存中比較耗時幾乎可以忽略，所以只要樹的高度足夠低，磁盤IO次數(shù)足夠少，就可以提高查詢性能。就算單個節(jié)點內(nèi)元素多一點也沒關(guān)系，僅僅是多了幾次內(nèi)存中的交互，可以忽略用時。其實說白了B樹的優(yōu)勢和高效就是因為B樹將一部分的IO負(fù)擔(dān)到內(nèi)存中來了，用內(nèi)存的高效和強大提升了查詢性能。
下面我們來看一下B樹的插入和刪除
B樹插入新節(jié)點的過程比較復(fù)雜，分好多種情況，此處舉一個最典型的例子，還使用上面的B樹，假如我們要插入的值是4，自頂向下查找4的位置，發(fā)下4應(yīng)當(dāng)插入到節(jié)點元素3，5之間，
可是節(jié)點3，5已經(jīng)是兩節(jié)點元素，無法再增加，父節(jié)點2，6也是兩節(jié)點元素，無法再增加。倒是根節(jié)點9是單元素節(jié)點，可以升級為兩元素節(jié)點，于是拆分節(jié)點2，6和節(jié)點3，5，讓根節(jié)點9升級為兩元素節(jié)點4，9，節(jié)點6獨立為根節(jié)點的第二個孩子。
由此看出，插入一個節(jié)點，會讓B樹的那么多節(jié)點發(fā)生連鎖改變。也正是如此，保證了B樹始終維持多路平衡，這就是B樹的一大優(yōu)勢，也是B樹英語Balance-Tree中Balance的體現(xiàn)。
下面再看看B樹的刪除機制，以上面插入4后的B樹為例，刪除元素11，首先自頂向下找出11的位置
刪除11后，節(jié)點12只有一個孩子，不符合B樹規(guī)范，因此找出12，13，15三個節(jié)點的中位數(shù)13，取代節(jié)點12，而節(jié)點12自身下移成為第一個孩子。（此過程稱為“左旋”）
以上便是B樹的查詢，新增和刪除的機制，B樹主要應(yīng)用于文件系統(tǒng)（FS）以及部分?jǐn)?shù)據(jù)庫索引，比如著名的非關(guān)系型數(shù)據(jù)庫MongoDB。但是絕大多數(shù)關(guān)系型數(shù)據(jù)庫，比如MySQL，都使用B+樹作索引，所以下篇將會介紹B+樹的相關(guān)內(nèi)容。
