什么是B+Tree?

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

　　為什么是B+Tree?

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

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

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

　　B+樹(shù)索引可分為聚簇索引和非聚簇索引?

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

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

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

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