談談 MySQL 索引 是如何提高 查詢效率 的？

碼農老K

工具主管,科技領域創作者

前言

我們都知道當查詢數據庫變慢時，需要建索引去優化。但是只知道索引能優化顯然是不夠的，我們更應該知道索引的原理，因為不是加了索引就一定會提升性能。那麼接下來就一起探索MYSQL索引的原理吧

什麼是索引

索引其實是一種能高效幫助MYSQL獲取數據的數據結構，通常保存在磁盤文件中，好比一本書的目錄，能加快數據庫的查詢速度。除此之外，索引是有序的，所以也能提高數據的排序效率。

通常MYSQL的索引包括聚簇索引，覆蓋索引，複合索引，唯一索引，普通索引，通常底層是B+樹的數據結構。

總結一下，索引的優勢在於：

提高查詢效率。降低數據排序的成本。

缺點在於：

索引會占用磁盤空間。索引會降低更新表的效率。因為在更新數據時，要額外維護索引文件。

索引的類型

聚簇索引

索引列的值必須是唯一的，並且不能為空，一個表只能有一個聚簇索引。

唯一索引

索引列的值是唯一的，值可以為空。

普通索引

沒有什麼限制，允許在定義索引的列中插入重複值和空值。

複合索引

也叫組合索引，用戶可以在多個列上組合建立索引，遵循“最左匹配原則”，在條件允許的情況下使用複合索引可以替代多個單列索引的使用。

索引的數據結構

我們都知道索引的底層數據結構采用的是B+樹，但是在講B+樹之前，要先知道B樹，因為B+樹是在B樹上面進行改進優化的。

首先講一下B樹的特點：

B樹的每個節點都存儲了多個元素，每個內節點都有多個分支。節點中元素包含鍵值和數據，節點中的鍵值從小到大排序。父節點的數據不會出現在子節點中。所有的葉子節點都在同一層，葉節點具有相同的深度。

image

在上面的B樹中，假如我們要找值等於18的數據，查找路徑就是磁盤塊1->磁盤塊3->磁盤塊8。

過程如下：

第一次磁盤IO：首先加載磁盤塊1到內存中，在內存中遍歷比較，因為17<18<50，所以走中間P2，定位到磁盤塊3。

第二次磁盤IO：加載磁盤塊3到內存，依然是遍歷比較，18<25，所以走左邊P1，定位到磁盤塊8。

第三次磁盤IO：加載磁盤塊8到內存，在內存中遍歷，18=18，找到18，取出data。

如圖所示：

image

如果data存儲的是行數據，直接返回，如果存的是磁盤地址則根據磁盤地址到磁盤中取出數據。可以看出B樹的查詢效率是很高的。

B樹存在著什麼問題，需要改進優化呢？

第一個問題：B樹在範圍查詢時，性能並不理想。假如要查詢13到30之間的數據，查詢到13後又要回到根節點再去查詢後面的數據，就會產生多次的查詢遍歷。

第二個問題：因為非葉子節點和葉子節點都會存儲數據，所以占用的空間大，一個頁可存儲的數據量就會變少，樹的高度就會變高，磁盤的IO次數就會變多。

基於以上兩個問題，就出現了B樹的升級版，B+樹。
B+樹與B樹最大的區別在於兩點：

B+樹只有葉子節點存儲數據，非葉子節點只存儲鍵值。而B樹的非葉子節點和葉子節點都會存儲數據。B+樹的最底層的葉子節點會形成一個雙向有序鏈表，而B樹不會。

如圖所示：

image

B+樹的等值查詢過程是怎麼樣的？

如果在B+樹中進行等值查詢，比如查詢等於13的數據。

查詢路徑為：磁盤塊1->磁盤塊2->磁盤塊6。

第一次IO：加載磁盤塊1，在內存中遍歷比較，13<17，走左邊，找到磁盤塊2。第二次IO：加載磁盤塊2，在內存中遍歷比較，10<13<15，走中間，找到磁盤塊6。第三次IO：加載磁盤塊6，依次遍歷，找到13=13，取出data。

所以B+樹在等值查詢的效率是很高的。

B+樹的範圍查詢過程又是怎麼樣呢？

比如我們要進行範圍查詢，查詢大於5並且小於15的數據。

查詢路徑為：磁盤塊1->磁盤塊2->磁盤塊5->磁盤塊6

第一次IO：加載磁盤塊1，比較得出5<17，然後走左邊，找到磁盤塊2。第二次IO：加載磁盤塊2，比較5<10，然後還是走左邊，找到磁盤塊5第三次IO：加載磁盤塊5，然後找大於5的數據。第四次IO：由於最底層是有序的雙向鏈表，所以繼續往右遍歷即可，直到不符合小於15的數據為止。

過程如圖所示：

image

所以在範圍查詢的時候，是不需要像B樹一樣，再回到根節點，這就是底層采用雙向鏈表的好處。

所以B+樹的優勢在於，能保證等值查詢和範圍查詢的快速查找。

InnoDB索引

我們常用的MySQL存儲引擎一般是InnoDB，所以接下來講講幾種不同的索引的底層數據結構，以及查找過程。

聚簇索引

前面講過，每個InnoDB表有且僅有一個聚簇索引。除此之外，聚簇索引在表的創建有以下幾點規則：

在表中，如果定義了主鍵，InnoDB會將主鍵索引作為聚簇索引。如果沒有定義主鍵，則會選擇第一個不為NULL的唯一索引列作為聚簇索引。如果以上兩個都沒有。InnoDB 會使用一個6 字節長整型的隱式字段 ROWID字段構建聚簇索引。該ROWID字段會在插入新行時自動遞增。

除了聚簇索引之外的索引都稱為非聚簇索引，區別在於，聚簇索引的葉子節點存儲的數據是整行數據，而非聚簇索引存儲的是該行的主鍵值。

比如有一張user表，如圖所示：

image

底層的數據結構就像這樣：

image.png

當我們用主鍵值去查詢的時候，查詢效率是很快的，因為可以直接返回數據。

image.png

普通索引

也就是用得最多的一種索引，比如我要為user表的age列創建索引，SQL語句可以這樣寫：

CREATE INDEX INDEX_USER_AGE ON `user`(age);

普通索引屬於非聚簇索引，所以葉子節點存儲的是主鍵值，底層的數據結構大概長這個樣子：

image

比如要查詢age=33的數據，那麼首先查到磁盤塊7的age=33的數據，獲取到主鍵值，主鍵值為4。

接著再通過主鍵值等於4，查詢到該行的數據。所以總得來說，底層會進行兩次查詢。

這種先通過查詢主鍵值，再通過主鍵值查詢到數據的過程就叫做回表查詢。

覆蓋索引

既然上面提到了回表查詢，那麼自然而然會想到，有沒有什麼辦法能避免回表查詢呢？答案肯定是有的，那就是使用覆蓋索引。

覆蓋索引不是一種索引的類型，而是一種使用索引的方式。假設你需要查詢的列是建立了索引，查詢的結果在索引列上就能獲取，那就可以用覆蓋索引。

比如上面的例子，我們通過age=33查詢，我需要查詢的結果就只要age這一列，那就可以用到覆蓋索引，如圖所示：

image.png

使用到覆蓋索引的話，就能避免回表查詢，所以在寫SQL語句時盡量不要寫SELECT *。

總結

這篇文章主要講的是索引的類型，索引的數據結構，以及InnoDB表中常用的幾種索引。當然，除了上述講的這些之外，還有很多關於索引的知識，比如索引失效的場景，索引創建的原則等等，由於篇幅過長，留著以後再講。