什么是索引？MySQL索引的底層數(shù)據(jù)結(jié)構(gòu)

索引(index)是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)(有序)。在數(shù)據(jù)之外，數(shù)據(jù)庫(kù)系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)(B+樹(shù))，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用(指向)數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級(jí)查找算法，這種數(shù)據(jù)結(jié)構(gòu)就是索引。

MySQL默認(rèn)使用的索引底層數(shù)據(jù)結(jié)構(gòu)是B+樹(shù)。再聊B+樹(shù)之前，我們先聊聊二叉樹(shù)和B樹(shù)。

B-Tree，B樹(shù)是一種多叉路衡查找樹(shù)，相對(duì)于二叉樹(shù)，B樹(shù)每個(gè)節(jié)點(diǎn)可以有多個(gè)分支，即多叉。以一顆最大度數(shù)(max-degree)為5(5階)的b-tree為例，那這個(gè)B樹(shù)每個(gè)節(jié)點(diǎn)最多存儲(chǔ)4個(gè)key。MySQL的默認(rèn)的存儲(chǔ)引擎InnoDB采用的B+樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)索引，選擇B+樹(shù)的主要的原因是：第一階數(shù)更多，路徑更短，第二個(gè)磁盤(pán)讀寫(xiě)代價(jià)B+樹(shù)更低，非葉子節(jié)點(diǎn)只存儲(chǔ)指針，葉子階段存儲(chǔ)數(shù)據(jù)，第三是B+樹(shù)便于掃庫(kù)和區(qū)間查詢，葉子節(jié)點(diǎn)是一個(gè)雙向鏈表。

B+Tree是在BTree基礎(chǔ)上的一種優(yōu)化，使其更適合實(shí)現(xiàn)外存儲(chǔ)索引結(jié)構(gòu)，InnoDB存儲(chǔ)引擎就是用B+Tree實(shí)現(xiàn)其索引結(jié)構(gòu)。

B樹(shù)與B+樹(shù)的區(qū)別:①：磁盤(pán)讀寫(xiě)代價(jià)B+樹(shù)更低;②：查詢效率B+樹(shù)更加穩(wěn)定;③：B+樹(shù)便于掃庫(kù)和區(qū)間查詢

第一：在B樹(shù)中，非葉子節(jié)點(diǎn)和葉子節(jié)點(diǎn)都會(huì)存放數(shù)據(jù)，而B(niǎo)+樹(shù)的所有的數(shù)據(jù)都會(huì)出現(xiàn)在葉子節(jié)點(diǎn)，在查詢的時(shí)候，B+樹(shù)查找效率更加穩(wěn)定。

第二：在進(jìn)行范圍查詢的時(shí)候，B+樹(shù)效率更高，因?yàn)锽+樹(shù)都在葉子節(jié)點(diǎn)存儲(chǔ)，并且葉子節(jié)點(diǎn)是一個(gè)雙向鏈表。