??數(shù)據(jù)庫索引為什么要用樹結(jié)構(gòu)來做存儲? (InnoDB引擎使用的是B+樹)
1.樹的查詢效率高.
2.可以保持有序
??二叉查找樹跟B數(shù)的時間復(fù)雜度都是O(logn),為什么使用的是B樹,而不是二叉查找樹?
??磁盤I/O消耗比較小.（一顆完全二叉樹的高度大約是logN，而一個完全M叉樹的高度大約是log?N）
??數(shù)據(jù)庫索引是存儲在磁盤上的,索引的大小可能有幾個G甚至更多.當(dāng)我們利用索引查詢的時候,不可能將整個索引全部加載到內(nèi)存中,只能逐一加載每一個磁盤頁,這里的磁盤頁對應(yīng)著索引樹的節(jié)點.
??如果我們利用二叉查找樹作為索引結(jié)構(gòu),當(dāng)樹的高度是4,查找的值是10,流程如下:
??????????????????二叉查找樹的結(jié)構(gòu)：
???????????????????????第1次磁盤I/O：
???????????????????????第2次磁盤I/O：
???????????????????????第3次磁盤I/O：
???????????????????????第4次磁盤I/O：
??而B樹是一種多路平衡查找數(shù),它的每一個節(jié)點最多包含k個孩子,k被稱為B樹的階.k的大小取決于磁盤頁的大小.
??一個m階的B樹具有如下幾個特征:
- 1.根節(jié)點至少有兩個子女.
- 2.每個中間節(jié)點包含k-1個元素和k個孩子,其中m/2<=k<=m.
- 3.每一個葉子節(jié)點都包含k-1個元素,其中m/2<=k<=m.
- 4.所有的葉子節(jié)點都位于同一層.
- 5.每個節(jié)點中的元素從小到大排序,節(jié)點當(dāng)中k-1個元素正好是k個孩子包含的元素的值域劃分.
一個3階的B-樹:
??如果我們利用B-樹作為索引結(jié)構(gòu),查詢的數(shù)值是5,流程如下:
????????????????????????第1次磁盤I/O：
???????????????????????在內(nèi)存中定位（和9比較)：
?????????????????????????第2次磁盤I/O：
???????????????????????在內(nèi)存中定位（和2洼怔，6比較）：
??????????????????????????第3次磁盤I/O：
???????????????????????在內(nèi)存中定位（和3症革，5比較）：
??通過整個流程我們可以看出,B-樹在查詢中的比較次數(shù)其實不必二叉查找樹少,尤其當(dāng)單一節(jié)點的元素數(shù)量很多時,可是相比磁盤I/O的速度,內(nèi)存中的比較耗時幾乎可以忽略.所以只要樹的高度足夠低,I/O次數(shù)足夠少,就可以提升查找性能.
B+樹
??一個m階的B+樹具有如下幾個特征:
1.有k個子樹的中間節(jié)點包含有k個元素(B樹中k-1個元素),每個元素不保存數(shù)據(jù),只用來索引,所有數(shù)據(jù)都保存在葉子節(jié)點.
2.所有的葉子結(jié)點中包含了全部元素的信息,及指向含這些元素記錄的指針,且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接.
3.所有的中間節(jié)點元素都同時存在于子節(jié)點,在子節(jié)點元素中是最大(或最小)元素.
??B+樹結(jié)構(gòu)例子:
??B+樹的好處主要體現(xiàn)在查詢性能上.
??在單元素查詢的時候,B+樹會自頂向下逐層查找節(jié)點,最終找到匹配的葉子節(jié)點.比如我們要查找的是元素3
??????????????????????????第一次磁盤I/O：
??????????????????????????第二次磁盤I/O：
??????????????????????????第三次磁盤I/O：
B+樹對比B-樹的優(yōu)勢:
1.B+樹的中間節(jié)點沒有衛(wèi)星數(shù)據(jù)(衛(wèi)星數(shù)據(jù),指的是索引元素所執(zhí)行的數(shù)據(jù)記錄,比如數(shù)據(jù)庫中的某一行),所以同樣大小的磁盤頁可以容納更多的節(jié)點元素
?這意味著,數(shù)據(jù)量相同的情況下,B+樹的結(jié)構(gòu)比B-樹更加"矮胖",因此查詢時I/O次數(shù)也更少.2.其次,B+樹的查詢必須最終查找到葉子節(jié)點,而B-樹只要找到匹配元素即可,無論匹配元素處于中間節(jié)點還是葉子節(jié)點.
?因此,B-樹的查找性能并不文檔(最好情況是只查根節(jié)點,最壞情況是查到葉子節(jié)點).而B+樹的每一次查找都是穩(wěn)定的(查詢性能穩(wěn)定)- B+樹范圍查詢的效率比B-樹高(范圍查詢簡便)
B-樹的范圍查找過程
????????????????????自頂向下，查找到范圍的下限（3）：
??????????????????????中序遍歷到元素6：
??????????????????????中序遍歷到元素9:
????????????????????中序遍歷到元素11扼雏，遍歷結(jié)束：
B+樹的范圍查找過程
????????????????????自頂向下携狭，查找到范圍的下限（3）：
????????????????????通過鏈表指針害晦，遍歷到元素6, 8
??????????????????通過鏈表指針，遍歷到元素9, 11壹瘟，遍歷結(jié)束：
