什么是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?
為了減少磁盤讀取次數(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+樹索引可分為聚簇索引和非聚簇索引?
主索引就是聚簇索引(也稱聚集索引,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ù)所有的索引。