大家好少梁，我是“Stephen·謝”矫付，之前有講到樹（Tree）的概念凯沪，還演示了二叉查找樹和紅黑樹這兩種經典樹的相關內容买优，其中引入了一個“自平衡”的概念妨马，這個自平衡特性對樹結構而言相當?shù)闹匾鞘刮覀兊臉浣Y構變得實用方便的重要手段烘跺。由此，開始下面B樹（B-Tree即Balance Tree）的講解脂崔。
首先補充一點，標題中的"B-樹"就是“B樹”砌左，它們都是B-Tree的翻譯脖咐，里面不是減號-铺敌，是連接符-屁擅。因為有人把B-Tree讀成"B-樹"偿凭，讓人誤以為“B樹”和"B-樹"是兩種樹派歌，實際上兩者都是同一種樹弯囊。還有，大家在讀的時候千萬不要讀成“B減樹”匾嘱，讀成“B樹”就行了，不然就外行了稽物。
下面開始今天正文，我們依然從數(shù)據(jù)庫的檢索開始贝或，我們知道數(shù)據(jù)庫的索引是使用樹結構來實現(xiàn)的吼过，是因為樹的查詢效率高咪奖，而且還可以保持有序的狀態(tài)盗忱。上篇中講到的二叉查找樹效率就很高，但是為什么沒有使用二叉查找樹來實現(xiàn)索引呢趟佃？其實從算法邏輯上講，二叉查找樹的查找次數(shù)和比較次數(shù)都是最小的昧捷，但是我們必須還要考慮一個現(xiàn)實問題：磁盤的IO（磁盤讀寫）。
數(shù)據(jù)庫的索引是存儲在磁盤上的靡挥，當數(shù)據(jù)量非常大的時候序矩，索引的大小可能有幾個G甚至更多跋破，當我們利用索引查詢的時候顯然不可能將整個索引全部加載到內存簸淀，正常的操作都是逐一加載每一個磁盤頁，這里的磁盤頁就對應著索引樹的節(jié)點租幕。
我們如果利用二叉查找樹做索引結構，查找情形是什么樣子的呢拧簸？假設樹的高度是4，要查找的值是10。
磁盤IO的次是4次珠叔，即樹的高度，最壞的情況就是磁盤IO的次數(shù)等于索引樹的高度祷安。既然如此姥芥，為了減少磁盤IO的次數(shù)汇鞭，我們就需要把原來的“瘦高”樹結構變得“矮胖”凉唐，這就是本文所要說的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é)點當中k-1個元素正好是k個孩子包含的元素的值域劃分勺拣。
我們以一個3階B樹為例來看一下B樹的結構鱼填，樹中的具體元素和上面的二叉查找樹是一樣的药有。
我們來看（2，6）節(jié)點愤惰，該節(jié)點有兩個元素2和6苇经，又有三個孩子1，（3扇单，5），8奠旺。其中1小于元素2，（3响疚，5）在元素2鄙信，6之間忿晕，8大于元素6装诡，符合上面的幾條規(guī)則。
接下來我們來看一下B樹的查詢過程，看看會帶來什么效果宏侍，假如我們要查詢的數(shù)值是5
從上面我們看出，其實B樹在查詢中的比較次數(shù)并不比二叉查找樹少绷耍，尤其當單一節(jié)點中的元素數(shù)量很多時吐限」邮迹可是相對磁盤IO的速度诸典，在內存中比較耗時幾乎可以忽略，所以只要樹的高度足夠低狐粱，磁盤IO次數(shù)足夠少，就可以提高查詢性能胆数。就算單個節(jié)點內元素多一點也沒關系肌蜻，僅僅是多了幾次內存中的交互必尼，可以忽略用時蒋搜。其實說白了B樹的優(yōu)勢和高效就是因為B樹將一部分的IO負擔到內存中來了，用內存的高效和強大提升了查詢性能豆挽。
下面我們來看一下B樹的插入和刪除
B樹插入新節(jié)點的過程比較復雜育谬，分好多種情況，此處舉一個最典型的例子帮哈，還使用上面的B樹膛檀，假如我們要插入的值是4，自頂向下查找4的位置宿刮，發(fā)下4應當插入到節(jié)點元素3，5之間私蕾，
可是節(jié)點3，5已經是兩節(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樹主要應用于文件系統(tǒng)（FS）以及部分數(shù)據(jù)庫索引，比如著名的非關系型數(shù)據(jù)庫MongoDB寄猩。但是絕大多數(shù)關系型數(shù)據(jù)庫，比如MySQL骑疆，都使用B+樹作索引，所以下篇將會介紹B+樹的相關內容封断。
