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

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

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

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

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

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

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

第二：在進行范圍查詢的時候，B+樹效率更高，因為B+樹都在葉子節(jié)點存儲，并且葉子節(jié)點是一個雙向鏈表。