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