大家好，歡迎收看猿話！
BTree意思是多路平衡查找樹，它是一種數據結構。MySQL的InnoDB和MyISAM存儲引擎，都是使用它來存儲索引。BTree可細分為B-Tree和B+Tree，B+Tree是B-Tree的升級版。MySQL的InnoDB和MyISAM存儲引擎使用的是B+Tree。
B-Tree
為了描述B-Tree，首先定義一條記錄為一個二元組[key, data] ，key為記錄的鍵值，對應表中的主鍵值，data為一行記錄中除主鍵外的數據。對于不同的記錄，key值互不相同。如下圖中的紫色部分就是key，橙色部分就是一行數據，綠色部分就是指針。
一棵m階的B-Tree有如下特性：
- 每個節點最多有m個子節點。 如上圖所示是一個3階的樹，那最多有3個子節點。
- 除了根節點和葉子節點外，其它每個節點至少有ceil(m/2)個子節點。如上圖所示是一個3階的樹，那每個節點至少有2個子節點。
- 所有葉子節點都在同一層，且不包含其它關鍵字信息
- 每個非終端節點包含n個關鍵字信息（P0,P1,…Pn, k1,…kn） ，關鍵字的個數n滿足：ceil(m/2)-1 <= n <= m-1
- ki(i=1,…n)為關鍵字，且關鍵字升序排序。
- Pi(i=1,…n)為指向子樹根節點的指針。P(i-1)指向的子樹的所有節點關鍵字均小于ki，但都大于k(i-1)
- 指針存儲的是子節點所在磁盤塊的地址
假設以根節點為例，關鍵字為17和35，P1指針指向的子樹的數據范圍為小于17，P2指針指向的子樹的數據范圍為17~35，P3指針指向的子樹的數據范圍為大于35。
當我們要查找關鍵字29時：
- 根據根節點找到磁盤塊1，讀入內存。【磁盤I/O操作第1次】
- 比較關鍵字29在區間（17,35），找到磁盤塊1的指針P2。
- 根據P2指針找到磁盤塊3，讀入內存。【磁盤I/O操作第2次】
- 比較關鍵字29在區間（26,30），找到磁盤塊3的指針P2。
- 根據P2指針找到磁盤塊8，讀入內存。【磁盤I/O操作第3次】
- 在磁盤塊8中的關鍵字列表中找到關鍵字29。
分析上面過程，發現需要3次磁盤I/O操作，和3次內存查找操作。由于內存中的關鍵字是一個有序表結構，可以利用二分法查找提高效率。而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素。B-Tree相對于AVLTree縮減了節點個數，使每次磁盤I/O取到內存的數據都發揮了作用，從而提高了查詢效率。
B+Tree
從上一節中的B-Tree結構圖中可以看到，每個節點中不僅包含數據的key值，還有data值。而每一個頁的存儲空間是有限的，一般為16K（也可以調整），如果data數據較大時將會導致每個節點（即一個頁）能存儲的key的數量很小。當存儲的數據量很大時同樣會導致B-Tree的深度較大，增大查詢時的磁盤I/O次數，進而影響查詢效率。
為解決這個問題，在B-Tree基礎上就產生了一種新的數據結構B+Tree。
一棵m階的B+Tree的特性和m階的B-Tree基本相同，除了以下幾點：
- 非葉子節點上只存儲key值信息，而不存儲data信息
- 非葉子節點的子樹指針與關鍵字個數相同
- 非葉子節點的子樹指針 P[i] ， 指向關鍵字值屬于 [K[i], K[i+1]) 的子樹（ B- 樹是開區間）
- 所有關鍵字都會出現在葉子節點的鏈表中（稠密索引），且鏈表中的關鍵字恰好是有序的。如上圖所示的升序。
雖然，MySQL的InnoDB和MyISAM存儲引擎使用的都是B+Tree結構，但是它們也有不同之處：
- InnoDB的B+Tree索引分為聚簇索引和非聚簇索引，而MyISAM的B+Tree索引都是非聚簇索引。
- InnoDB的主鍵索引為聚簇索引，輔助索引為非聚簇索引。主鍵索引的葉子節點保存了完整的記錄，輔助索引的葉子節點并不包含行記錄的全部數據，它除了包含鍵值外，還包含了相應行數據的聚簇索引鍵。
- MyISAM的非聚簇索引結構都是一樣的，它的葉子節點保存的都是磁盤地址，真正的數據存儲在另外的地方。
