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