在介紹B樹之前，先來看另一棵神奇的樹——二叉排序樹（Binary Sort Tree），首先它是一棵樹，“二叉”這個描述已經很明顯了，就是樹上的一根樹枝開兩個叉，於是遞歸下來就是二叉樹了（下圖所示），而這棵樹上的節點是已經排好序的，具體的排序規則如下：
- 若左子樹不空，則左子樹上所有節點的值均小於它的根節點的值
- 若右子樹不空，則右字數上所有節點的值均大於它的根節點的值
- 它的左、右子樹也分別為二叉排序數（遞歸定義）
從圖中可以看出，二叉排序樹組織數據時，用於查找是比較方便的，因為每次經過一次節點時，最多可以減少一半的可能，不過極端情況會出現所有節點都位於同一側，直觀上看就是一條直線，那麼這種查詢的效率就比較低了，因此需要對二叉樹左右子樹的高度進行平衡化處理，於是就有了平衡二叉樹（Balenced Binary Tree）
所謂“平衡”，說的是這棵樹的各個分支的高度是均勻的，它的左子樹和右子樹的高度之差絕對值小於1，這樣就不會出現一條支路特別長的情況。於是，在這樣的平衡樹中進行查找時，總共比較節點的次數不超過樹的高度，這就確保了查詢的效率（時間複雜度為O(logn)）
一、B樹的起源
B樹，最早是由德國計算機科學家Rudolf Bayer等人於1972年在論文 《Organization and Maintenance of Large Ordered Indexes》提出的，不過我去看了看原文，發現作者也沒有解釋為什麼就叫B-trees了，所以把B樹的B，簡單地解釋為Balanced或者Binary都不是特別嚴謹，也許作者就是取其名字Bayer的首字母命名的也說不定啊……
二、B樹長啥樣
還是直接看圖比較清楚，圖中所示，B樹事實上是一種平衡的多叉查找樹，也就是說最多可以開m個叉（m>=2），我們稱之為m階b樹，為了體現本博客的良心之處，不同於其他地方都能看到2階B樹，這裡特意畫了一棵5階B樹 。
總的來說，m階B樹滿足以下條件：
- 每個節點至多可以擁有m棵子樹
- 根節點，只有至少有2個節點（要麼極端情況，就是一棵樹就一個根節點，單細胞生物，即是根，也是葉，也是樹)
- 非根非葉的節點至少有的Ceil(m/2)個子樹(Ceil表示向上取整，圖中5階B樹，每個節點至少有3個子樹，也就是至少有3個叉)
- 非葉節點中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示該節點中保存的關鍵字個數，K為關鍵字且Ki
- 從根到葉子的每一條路徑都有相同的長度，也就是說，葉子節在相同的層，並且這些節點不帶信息，實際上這些節點就表示找不到指定的值，也就是指向這些節點的指針為空
B樹的查詢過程和二叉排序樹比較類似，從根節點依次比較每個結點，因為每個節點中的關鍵字和左右子樹都是有序的，所以只要比較節點中的關鍵字，或者沿著指針就能很快地找到指定的關鍵字，如果查找失敗，則會返回葉子節點，即空指針
例如查詢圖中字母表中的K
- 從根節點P開始，K的位置在P之前，進入左側指針
- 左子樹中，依次比較C、F、J、M，發現K在J和M之間
- 沿著J和M之間的指針，繼續訪問子樹，並依次進行比較，發現第一個關鍵字K即為指定查找的值
三、Plus版——B+樹
作為B樹的加強版，B+樹與B樹的差異在於：
- 有n棵子樹的節點含有n個關鍵字（也有認為是n-1個關鍵字）
- 所有的葉子節點包含了全部的關鍵字，及指向含這些關鍵字記錄的指針，且葉子節點本身根據關鍵字自小而大順序連接
- 非葉子節點可以看成索引部分，節點中僅含有其子樹（根節點）中的最大（或最小）關鍵字
B+樹的查找過程，與B樹類似，只不過查找時，如果在非葉子節點上的關鍵字等於給定值，並不終止，而是繼續沿著指針直到葉子節點位置。因此在B+樹，不管查找成功與否，每次查找都是走了一條從根到葉子節點的路徑
四、MySQL是如何使用B樹的
說明：事實上，在MySQL數據庫中，諸多存儲引擎使用的是B+樹，即便其名字看上去是BTREE。
4.1 innodb的索引機制
先以innodb存儲引擎為例，說明innodb引擎是如何利用B+樹建立索引的
首先創建一張表：zodiac，並插入一些數據
對於innodb來說，只有一個數據文件，這個數據文件本身就是用B+樹形式組織，B+樹每個節點的關鍵字就是表的主鍵，因此innode的數據文件本身就是主索引文件，如下圖所示，主索引中的葉子頁（leaf page）包含了數據記錄，但非葉子節點只包含了主鍵，術語“聚簇”表示數據行和相鄰的鍵值緊湊地存儲在一起，因此這種索引被稱為聚簇索引，或聚集索引。
這種索引方式，可以提高數據訪問的速度，因為索引和數據是保存在同一棵B樹之中，從聚簇索引中獲取數據通常比在非聚簇索引中要來得快。
所以可以說，innodb的數據文件是依靠主鍵組織起來的，這也就是為什麼innodb引擎下創建的表，必須指定主鍵的原因，如果沒有顯式指定主鍵，innodb引擎仍然會對該表隱式地定義一個主鍵作為聚簇索引。
同樣innodb的輔助索引，如下圖所示，假設這些字符是按照生肖的順序排列的（其實我也不知道具體怎麼實現，不要在意這些細節，就是舉個例子），其葉子節點中也包含了記錄的主鍵，因此innodb引擎在查詢輔助索引的時候會查詢兩次，首先通過輔助索引得到主鍵值，然後再查詢主索引，略微有點囉嗦
4.2 MyISAM的索引機制
MyISAM引擎同樣也使用B+樹組織索引，如下圖所示，假設我們的數據不是按照之前的順序插入的，而是按照圖中的是順序插入表，可以看到MyISAM引擎下，B+樹葉子節點中包含的是數據記錄的地址（可以簡單理解為“行號”），而MyISAM的輔助索引在結構上和主索引沒有本質的區別，同樣其葉子節點也包含了數據記錄的地址，稍微不同的是輔助索引的關鍵字是允許重複
五、簡單對比
- Innodb輔助索引的葉子節點存儲的不是地址，而是主鍵值，這樣的策略減少了當出現行移動或者數據頁分裂時輔助索引的維護工作，雖然使用主鍵值當作指針會讓輔助索引佔用更多空間，但好處是，Innodb在移動行時無需更新輔助索引中的主鍵值，而MyISAM需要調整其葉子節點中的地址
- innodb引擎下，數據記錄是保存在B+樹的葉子節點（大小相當於磁盤上的頁）上，當插入新的數據時，如果主鍵的值是有序的，它會把每一條記錄都存儲在上一條記錄的後面，但是如果主鍵使用的是無序的數值，例如UUID，這樣在插入數據時Innodb無法簡單地把新的數據插入到最後，而是需要為這條數據尋找合適的位置，這就額外增加了工作，這就是innodb引擎寫入性能要略差於MyISAM的原因之一
Innodb和MyISAM索引的抽象圖
