技術文章 » 我所理解的MySQL之二：索引

我所理解的MySQL之二：索引

2020-10-21 18:00:49

欄目今天介紹相關索引知識。

MySQL 系列的第二篇，主要討論 MySQL 中關於索引的一些問題，包括索引種類、資料模型、索引執行流程、最左字首原則、索引失效情況以及索引下推等內容。

最早知道索引應該是在大二的資料庫原理這門課中，當一個查詢語句非常慢時，可以通過為某些欄位新增索引來提高查詢效率。

還有一個非常經典的例子：我們可以把資料庫想象成字典，把索引想象成目錄，當我們藉助字典的目錄來查詢一個字的時候，就能體現出索引的作用了。

1. 索引種類

在 MySQL 中，從索引的邏輯或者說欄位特性來區分，索引大致分為以下幾個種類：普通索引、唯一索引、主鍵索引、聯合索引和字首索引。

  • 普通索引：最基礎的索引，沒有任何限制。
  • 唯一索引：索引列的值必須唯一。
  • 主鍵索引：特殊的唯一索引，作為主鍵它的值不能為空。
  • 聯合索引：聯合索引就是索引列為多個欄位的普通索引，需要考慮最左字首原則。
  • 字首索引：對字元型別的前幾個字元或二進位制型別的前幾個位元組建立索引。

還有另外一種從物理儲存上來區分的索引分類：聚簇索引和非聚簇索引。

  • 聚簇索引：索引順序與資料儲存順序一致，其葉子節點儲存的是資料行。
  • 非聚簇索引：非聚簇索引的葉子節點儲存的是聚簇索引的值，同時它是基於聚簇索引建立的。

簡單來說，所謂的聚簇索引就是索引 key 與資料行在一起，而非聚簇索引的索引 key 對應的值是聚簇索引的值。

2. 索引的資料結構

常見的用於實現索引的資料結構有雜湊表、有序陣列和搜尋樹。

2.1 雜湊索引

雜湊表是一個以 key-value 形式來儲存資料的容器，和 HashMap 一樣，雜湊索引也會將 key 通過特定的雜湊函數計算得到索引值，然後在陣列的相應位置存放 key 對應的 value，如果有兩個 key 通過雜湊函數計算得到的索引值相同（發生雜湊衝突），那麼陣列的這個位置就會變成一個連結串列，存放所有雜湊值相同的 value。

所以在一般情況下，雜湊表進行等值查詢的時間複雜度可以達到 O(1)，但是在發生雜湊衝突的情況下，還需要額外遍歷連結串列中的所有值，才能夠找到符合條件的資料。

另外，考慮到經過雜湊函數計算得到的索引是不規律的——雜湊表希望所有的 key 能夠得到充分雜湊，這樣才能讓 key 均勻分佈，不浪費空間——即雜湊表的 key 是非順序的，所以使用雜湊表來進行區間查詢時很慢的，排序也是同樣的道理。

所以，雜湊表僅適用於等值查詢。

2.2 有序陣列

有序陣列顧名思義是一個按照 key 的順序進行排列的陣列，它進行等值查詢的時間複雜度使用二分查詢可以達到O(logN)，這與雜湊表相比遜色不少。

但是通過有序陣列進行範圍查詢的效率較高：首先通過二分查詢找到最小值（或最大值），然後反向遍歷，直到另一個邊界。

至於排序，有序陣列本來就是有序的，天然已經排好序了，當然排序欄位不是索引欄位就另說了。

但是有序陣列有一個缺點，由於陣列元素是連續且有序的，如果此時插入新的資料行，為了維持有序陣列的有序性，需要將比此元素 key 大的元素都往後移動一個單位，給他騰出一個地方插入。而這種維護索引的方式的代價是很大的。

所以，有序陣列適合儲存衣服初始化過後就不再更新的資料。

2.3 搜尋樹

瞭解過資料結構的人應該會知道，搜尋樹是一個查詢時間複雜度為O(logN)，更新的時間複雜度也是O(logN)的資料結構。所以搜尋樹相較於雜湊表和有序陣列來說兼顧查詢與更新兩方面。也正是由於這個原因，在 MySQL 中最常用的資料模型就是搜尋樹。

而考慮到索引是存放在磁碟中的，如果搜尋樹是一棵二元樹，那麼它的子節點只能有左右兩個，在資料比價多的情況下，這棵二元樹的樹高可能會非常高，當 MySQL 進行查詢的時候，可能由於樹高導致磁碟I/O次數過多，查詢效率變慢。

2.4 全文索引

除此之外，還有一種全文索引，它通過建立倒排索引，解決了判斷欄位是否包含的問題。

倒排索引是用來儲存在全文搜尋下某個單詞在一個檔案或者一組檔案中的儲存位置的對映，通過倒排索引可以根據單詞快速獲取包含這個單詞的檔案列表。

當通過關鍵詞進行檢索的時候，全文索引就會派上用場。

3. InnoDB 中的 BTree 索引

3.1 B+樹

這是一棵比較簡單的B+樹。

B+樹示例

圖片來源: Data Structure Visualizations

從上面這張範例圖也可以看到，這棵B+樹最下面的葉子節點儲存了所有的元素，並且是按順序儲存的，而非葉子節點僅儲存索引列的值。

3.2 圖解 BTree 索引

在 InnoDB 中，基於 BTree 的索引模型的最為常用的，下面以一個實際的例子來圖解 InnoDB 中 BTree 索引的結構。

CREATE TABLE `user`  (  `id` int(11) NOT NULL,  `name` varchar(36) DEFAULT NULL,  `age` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,  INDEX `nameIndex`(`name`) USING BTREE
) ENGINE = InnoDB;-- 插入資料insert into user1(id,name,age) values (1,'one',21),(2,'two',22),(3,'three',23),(4,'four',24),(5,'five',25);複製程式碼

在這張表中只有兩個欄位：主鍵 id 和 name 欄位，同時建立了一個以 name 欄位為索引列的 BTree 索引。

以主鍵 id 欄位的為索引的索引，又叫主鍵索引，它的索引樹結構是：索引樹的非葉子階段存放的都是主鍵 id 的值，葉子節點存放的值是該主鍵 id 對應的整個資料行，如下圖所示：

id主鍵索引樹

也正因為主鍵索引的葉子節點儲存的是該主鍵 id 對應的整個資料行，主鍵索引又被稱為聚簇索引。

而以 name 欄位為列的索引樹，非葉子節點存放的同樣是索引列的值，而其葉子階段存放的值是主鍵 id 的值，如下圖所示。

name欄位索引樹

3.3 索引的執行流程

首先來看下面這句 SQL，查詢 user 表中 id=1 的資料行。

select * from user where id=1;複製程式碼

這句 SQL 的執行流程很簡單，儲存引擎會走主鍵 id 的索引樹，當找到 id=1 時，就會把索引樹上 id=1 的資料行返回（由於主鍵值是唯一的，所以找到命中目標就會停止搜尋，直接返回結果集）。

3.3.1 回表

接下來再看使用普通索引進行查詢的情況，它的情況與主鍵索引略有不同。

select * from user where name='one';複製程式碼

上面這句 SQL 查詢語句的流程是這樣的：首先儲存引擎會搜尋普通索引 name 列的索引樹，當命中 name 等於 one 的記錄後，儲存引擎需要經過一個非常重要的步驟：回表。

由於普通索引的索引樹子節點存放的是主鍵值，當查詢語句需要查詢除主鍵 id 及索引列之外的其他欄位時，需要根據主鍵 id 的值再回到主鍵索引樹中進行查詢，得到主鍵 id 對應的整個資料行，然後從中獲取使用者端需要的欄位後，才將這一行加入結果集。

隨後儲存引擎會繼續搜尋索引樹，直到遇到第一個不滿足 name='one' 的記錄才會停止搜尋，最後將所有命中的記錄返回使用者端。

我們把根據從普通索引查詢到的主鍵 id 值，再在主鍵索引中查詢整個資料行的過程稱之為回表。

當資料量十分龐大時，回表是一個十分耗時的過程，所以我們應該儘量避免回表發生，這就引出了下一個問題：使用覆蓋索引避免回表。

3.3.2 覆蓋索引

不知道你有沒有注意到，在上一個回表的問題中有這樣一句描述：「當查詢語句需要查詢除主鍵 id 及索引列之外的其他欄位時...」，在這種場景下需要通過回表來獲取其他的查詢欄位。也就是說，如果查詢語句需要查詢的欄位僅有主鍵 id 和索引列的欄位時，是不是就不需要回表了？

下面來分析一波這個過程，首先建立一個聯合索引。

alter table user add index name_age ('name','age');複製程式碼

那麼這棵索引樹的結構圖應該是下面這樣：

name_age聯合索引樹

聯合索引索引樹的子節點順序是按照宣告索引時的欄位來排序的，類似於 order by name, age ，而它索引對應的值與普通索引一樣是主鍵值。

select name,age from user where name='one';複製程式碼

上面這條 SQL 是查詢所有 name='one' 記錄的 name 和 age 欄位，理想的執行計劃應該是搜尋剛剛建立的聯合索引。

與普通索引一樣，儲存引擎會搜尋聯合索引，由於聯合索引的順序是先按照 name 再按照 age 進行排序的，所以當找到第一個 name 不是 one 的索引時，才會停止搜尋。

而由於 SQL 語句查詢的只是 name 和 age 欄位，恰好儲存引擎命中查詢條件時得到的資料正是 name, age 和 id 欄位，已經包含了使用者端需要的欄位了，所以就不需要再回表了。

我們把只需要在一棵索引樹上就可以得到查詢語句所需要的所有欄位的索引成為覆蓋索引，覆蓋索引無須進行回表操作，速度會更快一些，所以我們在進行 SQL 優化時可以考慮使用覆蓋索引來優化。

4. 最左字首原則

上面所舉的例子都是使用索引的情況，事實上在專案中複雜的查詢語句中，也可能存在不使用索引的情況。首先我們要知道，MySQL 在執行 SQL 語句的時候一張表只會選擇一棵索引樹進行搜尋，所以一般在建立索引時需要儘可能覆蓋所有的查詢條件，建立聯合索引。

而對於聯合索引，MySQL 會遵循最左字首原則：查詢條件與聯合索引的最左列或最左連續多列一致，那麼就可以使用該索引。

為了詳細說明最左字首原則，同時說明最左字首原則的一些特殊情況。

5. 索引失效場景

即便我們根據最左字首的原則建立了聯合索引，還是會有一些特殊的場景會導致索引失效，下面舉例說明。

假設有一張 table 表，它有一個聯合索引，索引列為 a,b,c 這三個欄位，這三個欄位的長度均為10。

CREATE TABLE `demo`  (  `a` varchar(1) DEFAULT NULL,  `b` varchar(1) DEFAULT NULL,  `c` varchar(1) DEFAULT NULL,  INDEX `abc_index`(`a`, `b`, `c`) USING BTREE
) ENGINE = InnoDB;複製程式碼

5.1 全欄位匹配

第一種情況是查詢條件與索引欄位全部一致，並且用的是等值查詢，如：

select * from demo where a='1' and b='1' and c='1';select * from demo where c='1' and a='1' and b='1';複製程式碼

輸出上述兩條 SQL 的執行計劃來看它們使用索引的情況。

mysql> explain select * from demo where a='1' and b='1' and c='1';
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref               | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+|  1 | SIMPLE      | demo  | NULL       | ref  | abc_index     | abc_index | 18      | const,const,const |    1 |   100.00 | Using index |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+1 row in set, 1 warning (0.00 sec)

mysql> explain select * from demo where c='1' and a='1' and b='1';
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref               | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+|  1 | SIMPLE      | demo  | NULL       | ref  | abc_index     | abc_index | 18      | const,const,const |    1 |   100.00 | Using index |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+1 row in set, 1 warning (0.00 sec)複製程式碼

第一條 SQL 很顯然能夠用到聯合索引。

從執行計劃中可以看到，第二條 SQL 與第一條 SQL 使用的索引以及索引長度是一致的，都是使用 abc_index 索引，索引長度為 18 個位元組。

按理說查詢條件與索引的順序不一致，應該不會用到索引，但是由於 MySQL 有優化器存在，它會把第二條 SQL 優化成第一條 SQL 的樣子，所以第二條 SQL 也使用到了聯合索引 abc_index。

綜上所述，全欄位匹配且為等值查詢的情況下，查詢條件的順序不一致也能使用到聯合索引。

5.2 部分欄位匹配

第二種情況是查詢條件與索引欄位部分保持一致，這裡就需要遵循最左字首的原則，如：

select * from demo where a='1' and b='1';select * from demo where a='1' and c='1';複製程式碼

上述的兩條查詢語句分別對應三個索引欄位只用到兩個欄位的情況，它們的執行計劃是：

mysql> explain select * from demo where a='1' and b='1';
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------+------+----------+-------------+| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref         | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------+------+----------+-------------+|  1 | SIMPLE      | demo  | NULL       | ref  | abc_index     | abc_index | 12      | const,const |    1 |   100.00 | Using index |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------+------+----------+-------------+1 row in set, 1 warning (0.00 sec)

mysql> explain select * from demo where a='1' and c='1';
+----+-------------+-------+------------+------+---------------+-----------+---------+-------+------+----------+--------------------------+| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref   | rows | filtered | Extra                    |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------+------+----------+--------------------------+|  1 | SIMPLE      | demo  | NULL       | ref  | abc_index     | abc_index | 6       | const |    1 |   100.00 | Using where; Using index |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------+------+----------+--------------------------+1 row in set, 1 warning (0.00 sec)複製程式碼

從它們的執行計劃可以看到，這兩條查詢語句都使用到了 abc_index 索引，不同的是，它們使用到索引的長度分別是：12、6 位元組。

在這裡需要額外提一下索引長度的計算方式，對於本例中宣告為 varchar(1) 型別的 a 欄位，它的索引長度= 1 * (3) + 1 + 2 = 6。

  • 第一個數位 1 是該欄位宣告時的長度。
  • 第二個數位 3 是該欄位字元型別的長度：utf8=3, gbk=2, latin1=1。
  • 第三個數位 1 是該欄位的預設型別，若預設允許 NULL，第三個數位是 1，因為 NULL 需要一個位元組的額外空間；若預設不允許 NULL，這裡應該是0。
  • 第四個數位 2 是 varchar 型別的變長欄位需要附加的位元組。

所以這兩條查詢語句使用索引的情況是：

  1. 使用聯合索引，索引長度為 12 位元組，使用到的索引欄位是 a,b 欄位；
  2. 使用聯合索引，索引長度為 6 位元組，使用到的索引欄位是 a 欄位；

由此可見：最左字首原則要求，查詢條件必須是從索引最左列開始的連續幾列。

5.3 範圍查詢

第三種情況是查詢條件用的是範圍查詢（<,>,!=,<=,>=,between,like）時，如：

select * from demo where a='1' and b!='1' and c='1';複製程式碼

這兩條查詢語句的執行計劃是：

mysql> EXPLAIN select * from demo where a='1' and b!='1' and c='1';
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+| id | select_type | table | partitions | type  | possible_keys | key       | key_len | ref  | rows | filtered | Extra                    |
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+|  1 | SIMPLE      | demo  | NULL       | range | abc_index     | abc_index | 12      | NULL |    2 |    10.00 | Using where; Using index |
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+1 row in set, 1 warning (0.00 sec)複製程式碼

從執行計劃可以看到，第一條 SQL 使用了聯合索引，且索引長度為 12 位元組，即用到了 a,b 兩個欄位；第二條 SQL 也使用了聯合索引，索引長度為 6 位元組，僅使用了聯合索引中的 a 欄位。

綜上所述，在全欄位匹配且為範圍查詢的情況下，也能使用聯合索引，但只能使用到聯合索引中第一個出現範圍查詢條件的欄位。

需要注意的是：

  • like 必須要求是左模糊匹配才能用到索引，因為字元型別欄位的索引樹也是有序的。
  • between 並不一定是範圍查詢，它相當於使用 in 多值精確匹配，所以 between 並不會因為是範圍查詢就讓聯合索引後面的索引列失效。

5.4 查詢條件為函數或表示式

第四種情況是查詢條件中帶有函數或特殊表示式的，比如：

select * from demo where id + 1 = 2;select * from demo where concat(a, '1') = '11';複製程式碼

可能由於資料的原因（空表），我輸出的執行計劃是使用了聯合索引的，但是事實上，在查詢條件中，等式不等式左側的欄位包含表示式或函數時，該欄位是不會用到索引的。

至於原因，是因為使用函數或表示式的情況下，索引欄位本身的值已不具備有序性。

5.5 其他索引失效的場景

  • 查詢影響行數大於全表的25%
  • 查詢條件使用 <>(!=), not in, is not null
  • in 查詢條件中值資料型別不一致，MySQL 會將所有值轉化為與索引列一致的資料型別，從而無法使用索引

6. 索引下推

上文中已經羅列了聯合索引的實際結構、最左字首原則以及索引失效的場景，這裡再說一下索引下推這個重要的優化規則。

select * from demo where a > '1' and b='1';

mysql> explain select * from demo where a > '1' and b='1';
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+| id | select_type | table | partitions | type  | possible_keys | key       | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+|  1 | SIMPLE      | demo  | NULL       | range | abc_index     | abc_index | 6       | NULL |    1 |    10.00 | Using index condition |
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+1 row in set, 1 warning (0.00 sec)複製程式碼

上面這條查詢語句，從它的執行計劃也可以看出，它使用的索引長度為 6 個位元組，只用到了第一個欄位。

所以 MySQL 在查詢過程中，只會對第一個欄位 a 進行 a > '1' 的條件判斷，當滿足條件後，儲存引擎並不會進行 b=1 的判斷， 而是通過回表拿到整個資料行之後再進行判斷。

這好像很蠢，就算索引只用到了第一個欄位，但明明索引樹中就有 b 欄位的資料，為什麼不直接進行判斷呢？

聽上去好像是個 bug，其實在未使用索引下推之前整個查詢邏輯是：由儲存引擎檢索索引樹，就算索引樹中存在 b 欄位的值，但由於這條查詢語句的執行計劃使用了聯合索引但沒有用到 b 欄位，所以也無法進行 b 欄位的條件判斷，當儲存引擎拿到滿足條件（a>'1'）的資料後，再由 MySQL 伺服器進行條件判斷。

在 MySQL5.6 版本中對這樣的情況進行優化，引入索引下推技術：在搜尋索引樹的過程中，就算沒能用到聯合索引的其他欄位，也能優先對查詢條件中包含且索引也包含的欄位進行判斷，減少回表次數，提高查詢效率。

在使用索引下推優化之後，b 欄位作為聯合索引列，又存在於查詢條件中，同時又沒有在搜尋索引樹時被使用到，MySQL 伺服器會把查詢條件中關於 b 欄位的部分也傳給儲存引擎，儲存引擎會在搜尋索引樹命中資料之後再進行 b 欄位查詢條件的判斷，滿足的才會加入結果集。

Ps: 執行計劃中 Extra 欄位的值包含 Using index condition 就代表使用到了索引下推。

7. 溫故知新

  1. 索引分類？聚簇索引結構？非聚簇索引結構？
  2. 常用的實現索引的資料模型？
  3. B+樹索引的執行流程？
  4. 什麼是回表？如何優化？
  5. 什麼是覆蓋索引？
  6. 什麼是最左字首原則？
  7. 索引在哪些情況下可能會失效？
  8. 什麼是索引下推？

更多相關免費學習推薦：(視訊)

以上就是我所理解的MySQL之二：索引的詳細內容，更多請關注TW511.COM其它相關文章！