什么是索引？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ù)據(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+樹。再聊B+樹之前，我們先聊聊二叉樹和B樹。

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

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

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