什么是B+Tree?

　　B+ Tree 是基于 B Tree 和葉子節(jié)點順序訪問指針進行實現(xiàn)，它具有 B Tree 的平衡性，并且通過順序訪問指針來提高區(qū)間查詢的性能。在 B+ Tree 中，一個節(jié)點中的 key 從左到右非遞減排列，如果某個指針的左右相鄰 key 分別是 keyi 和 keyi+1，且不為 null，則該指針指向節(jié)點的所有 key 大于等于 keyi 且小于等于 keyi+1。

　　為什么是B+Tree?

　　為了減少磁盤讀取次數(shù)，決定了樹的高度不能高，所以必須是先B-Tree;

　　以頁為單位讀取使得一次 I/O 就能完全載入一個節(jié)點，且相鄰的節(jié)點也能夠被預(yù)先載入;所以數(shù)據(jù)放在葉子節(jié)點，本質(zhì)上是一個Page頁;

　　為了支持范圍查詢以及關(guān)聯(lián)關(guān)系， 頁中數(shù)據(jù)需要有序，且頁的尾部節(jié)點指向下個頁的頭部;

　　B+樹索引可分為聚簇索引和非聚簇索引?

　　主索引就是聚簇索引(也稱聚集索引，clustered index)輔助索引(有時也稱非聚簇索引或二級索引，secondary index，non-clustered index)。

　　如上圖，主鍵索引的葉子節(jié)點保存的是真正的數(shù)據(jù)。而輔助索引葉子節(jié)點的數(shù)據(jù)區(qū)保存的是主鍵索引關(guān)鍵字的值。

　　假如要查詢name = C 的數(shù)據(jù)，其搜索過程如下：a) 先在輔助索引中通過C查詢最后找到主鍵id = 9; b) 在主鍵索引中搜索id為9的數(shù)據(jù)，最終在主鍵索引的葉子節(jié)點中獲取到真正的數(shù)據(jù)。所以通過輔助索引進行檢索，需要檢索兩次索引。

　　之所以這樣設(shè)計，一個原因就是：如果和MyISAM一樣在主鍵索引和輔助索引的葉子節(jié)點中都存放數(shù)據(jù)行指針，一旦數(shù)據(jù)發(fā)生遷移，則需要去重新組織維護所有的索引。