一文了解 MySQL 索引機制

接觸 MySQL 數據庫的小夥伴一定避不開索引，索引的出現是爲了提高數據查詢的效率，就像書的目錄一樣。

某一個 SQL 查詢比較慢，你第一時間想到的就是 “給某個字段加個索引吧”，那麼索引是什麼？是如何工作的呢？一起靜下心來，耐心看完這篇文章吧，乾貨不囉嗦，相信你一定會有所收穫。

01

索引模型

模型也就是數據結構，常見的三種模型分別是哈希表、有序數組和搜索樹。

瞭解 MySQL 的朋友已經知道，現在 MySQL 默認使用的是 InnoDB 存儲引擎，使用的是 B + 樹索引數據結構。所以這個話題我們簡單介紹，不作過多篇幅解釋，只需瞭解爲什麼 InnoDB 選擇 B + 樹作爲索引的數據結構。

1.1 哈希表

key-value 鍵值對存儲結構，哈希思路非常 easy，給定 key，通過哈希函數命中 value。瞭解 HashMap 的都知道，哈希表不可避免的會發生同值衝突，所以需要通過鏈表跟在數組後面。

哈希表的特點是插入速度很快，只需要通過 hash 找到對應數組，發生衝突就在鏈表往後追加。但缺點也正是因爲無序，導致查詢速度很慢，幾乎全部掃描一遍。

1.2 有序數組

有序數組非常簡單，遞增順序保存。查詢時可以使用二分法，時間複雜度 O(log(N))，但是更新數據就很麻煩，往中間插入一個數據就必須挪動後面所有的記錄，成本很高。

1.3 B + 樹

B + 樹衍生於二叉搜索樹，沒錯，大學數據結構中的二叉搜索樹，課堂的熟悉感是不是都回來了～

二叉搜索樹的特點是：每個節點的左兒子小於父節點，右兒子大於父節點。所以查詢搜索的時間複雜度是 O(log(N))，爲了維持 O(log(N)) 查詢複雜度，需要保證這棵樹是平衡二叉樹，所以更新的時間複雜度也是 O(log(N))。

但是平衡二叉樹的缺點在於隨着數據的增加，整棵樹的層級越來越高，考慮葉子節點的數據總是在內存中，那麼樹層級越多意味着需要多次的磁盤尋址。一棵 100 萬數據量節點的平衡二叉樹，樹高 H=log2(N+1) - 1=log2(1000000+1)-1=20，一次查詢可能需要訪問 20 個數據節點，磁盤隨機讀一個數據塊大約 10ms，總計需要 20 個 10ms 時間找到一行數據，難以接受！

爲了減少儘量少的讀磁盤，二叉樹就演變爲了 N 叉樹，N 是多少，取決於數據塊的大小。如果 MySQL 數據表中你創建了一個整數類型的索引，這個 N 差不多是 1200，樹高是 4 時，整棵樹可以存儲 1200 的 3 次方，也就是 17 億數據，查找一個數據只需要訪問 3 次磁盤，很 nice~

02

索引維護 

每個索引在 InnoDB 中都對應一棵 B + 樹。

根據葉子節點的內容，索引類型分爲主鍵索引和非主鍵索引。主鍵索引又稱爲聚簇索引，葉子節點中存儲的是整行數據。

非主鍵索引的葉子節點中存儲的是主鍵的值。所以，如果你的 SQL 語句查詢時用到的索引不是主鍵，那麼就會有一次普通索引找到葉子節點中的主鍵 ID，再進行回表獲取數據。因此，我們在查詢時應儘量使用主鍵查詢。

B + 樹爲了維護索引有序性，是有代價的，如果新插入的數據在數據頁中有空位置且後面沒有數據，可以直接插入；如果在 500 和 700 中間插入 600，則需要挪動 700 及後面的數據，空出位置；更糟糕的是，如果數據頁已經滿了，則需要新申請一個新的數據頁，然後挪動數據，這就是頁分裂。有分裂就有合併，對應的就是刪除數據場景。性能很受影響！

從性能角度看，如果採用主鍵自增剛好符合索引有序的特點，每次插入數據都是追加，不會挪動數據也不會觸發頁分裂。

從存儲空間角度看，主鍵長度越小，索引的葉子節點就越小，佔用空間越小。如整型只要 4 個字節，長整型（bigint）就是 8 字節。這也是爲什麼不建議大家用隨機數作爲主鍵的原因。

03

索引利用

我們以一條 SQL 語句執行流程來看索引是怎麼提高查詢效率的。

selcect * from T where k between 1 and 3;

假定主鍵索引和 k 索引樹分別是：

這條 SQL 查詢的執行流程：

1、在 k 索引樹上找到 k=1 的記錄，取得主鍵 ID=1

2、到主鍵索引樹上查到 ID=1 對應的 V1

3、在 k 索引樹繼續取下一個值 k=3，取得主鍵 ID=4

4、到主鍵索引樹上查到 ID=4 對應的 V4

5、在 k 索引樹上取下一個值 k=5，不滿足查詢條件，循環結束。

可以看到，這條 SQL 查詢了 k 索引樹 3 次，回表 2 次。這裏你一定會想，能不能優化索引，避免回表呢？

如果這條 SQL 改爲 selcect id from T where k between 1 and 3; 那麼就不需要回表了，這時 k 索引也稱爲覆蓋索引，也就是查詢的字段已經在 k 索引中，無需回表了。

你可能會立即反問，業務中怎麼可能剛剛好只查主鍵呢，那就需要根據實際情況考慮建立聯合索引。

3.1 最左前綴原則

每一種查詢都新加一個索引，無疑是對索引的浪費。

我們來看（name，age）這個聯合索引：

當你查詢姓名爲 “李五” 時，可以快速定位到 id3，然後向後遍歷得到所要的結果。

如果你查詢的姓名第一個字是 “李” 時，可以定位到 id2，然後向後遍歷得到所要的結果。

所以最左前綴，不僅是聯合索引的最左 N 個字段，也可以是字符串的最左 N 個字符。

這時你需要根據具體的業務場景，考慮聯合索引的順序問題，當有 (name,age) 這個聯合索引，就無需再單獨建立（name）索引了，但是如果查詢條件裏面只有 age，是無法使用 (name,age) 索引了。

3.2 索引下推

在 MySQL5.6 之後，引入了索引下推優化，可以在索引遍歷過程中，對索引中包含的字段先做判斷，直接過濾不滿足條件的記錄，減少回表次數。

SQL 語句：

select * from T where name like "李%" and age = 25;

無索引下推機制時，根據最左前綴匹配原則，找到 “李 %” 的 name 之後，就回表查詢主鍵索引，然後過濾 age 字段。索引下推機制下，在尋找“李 %”name 時，會直接判斷 age=25 符合條件的數據，然後回表查詢主鍵索引，減少了 2 次回表次數。

3.3 唯一索引

**唯一索引的屬性列不能出現重複的數據，但是允許數據爲 NULL，一張表允許創建多個唯一索引。**建立唯一索引的目的大部分時候都是爲了該屬性列的數據的唯一性，而不是爲了查詢效率。

知道了唯一索引的概念之後，你也許已經猜到唯一索引的性能可能比不上普通索引，一起來看背後的原因是什麼？

我們從查詢和更新 2 個角度來分析，唯一索引和普通索引的區別。

查詢過程

SQL 語句：

select id from T where k = 3;

普通索引：查找到滿足第一個 k=3 記錄後，向後繼續尋找，直到第一個不滿足 k=3 的記錄。

唯一索引：由於索引數據的唯一性，查找到第一個滿足 k=3 條件的記錄後，停止檢索。

對於內存操作來說，兩者的性能差別幾乎可以忽略。

更新過程

當更新一個數據頁時，如果數據頁在內存中就直接更新，否則 InnoDB 會將這些更新操作緩存在 change buffer 中，這樣就不需要從磁盤中讀入這個數據頁了。在下次查詢訪問這個數據頁時，會觸發 change buffer 的 merge 操作，持久化到磁盤中。除了訪問數據頁觸發 merge 時，系統有後臺線程也會定期 merge，在數據庫正常關閉時，也會執行 merge 操作。將更新操作先記錄在 change buffer，就是爲了減少讀磁盤，提升 SQL 語句執行速度。

唯一索引更新不能使用 change buffer，而普通索引可以使用。

此時，再執行一條更新語句時，第一種情況時更新的數據頁在內存中，這時：

唯一索引：找到需要插入的位置，判斷有沒有衝突，執行插入，結束；

普通索引：找到需要插入的位置，插入這個值，結束。

可以看出，數據頁在內存中的兩者操作幾乎沒有性能差別。

重點來了，如果更新的數據頁不在內存中，這時：

唯一索引：將數據頁讀入內存，判斷有沒有衝突，執行插入，結束；

普通索引：將更新記錄在 change buffer，結束。

將數據從磁盤讀入內存涉及隨機 IO 的訪問，是數據庫裏面成本最高的操作之一。change buffer 因爲減少了隨機磁盤訪問，所以對更新性能的提升是會很明顯的。

舉個例子，大家感受更深，如果你的業務庫有大量插入數據的操作，內存命中率下降明顯，系統就會經常處於阻塞狀態，更新語句都堵住了。有可能就是因爲普通索引改爲了唯一索引。

那麼怎麼判斷是不適合用唯一索引呢？

對於寫多讀少的業務來說，寫完之後立即讀的概率比較小，此時 change buffer 效果很好，推薦使用普通索引。

對於一個業務寫完之後立即就要訪問，將更新操作記錄在 change buffer 之後，由於馬上訪問這個數據頁，會立即出觸發 merge 操作，增加隨機訪問 IO 次數，此時，change buffer 反而起到了反作用，增加了維護代價，可以使用唯一索引。

04

索引實踐

4.1 order by 語句

給定一個 SQL 語句：

select city,name,age from T where city = "杭州" order by name limit 1000;

此時你已經很清楚，爲了避免全表掃描，需要在 city 字段上加索引，我們用 explain 命令看一下這條 SQL 執行情況：

Extra 中的 “Using filesort” 表示就是需要排序，MySQL 會分配一塊內存用於排序，稱爲 sort_buffer。這條 SQL 的執行流程是：

1、初始化 sort_buffer，放入 name、city、age 三個字段

2、從索引 city 找到第一個滿足 city="杭州" 的主鍵 ID

3、從主鍵索引中取出行數據，選取 select 條件中的 city、name、age 三個字段，放入 sort_buffer 中

4、從索引 city 中取下一個記錄的主鍵 id

5、重複 3、4 直到不滿足 city 的查詢條件

6、對 sort_buffer 中的數據按照 name 進行快速排序

7、按照排序結果取前 1000 行返回給用戶

通過一張圖來看流程：

但是 sort_buffer 不是無限大的，如果排序數據量太大，內存就會放不下，就會用到磁盤臨時文件進行排序。

合併多個臨時文件一般使用歸併排序算法。MySQL 的設計思想是：如果內存夠用，儘量多利用內存，減少磁盤訪問。

4.2 索引選擇

其實對於 4.1 中的 SQL 語句是可以優化的，不知道你猜到了沒有，SQL 中過濾條件是 city 和 name，我們可以創建一個 (city，name) 的聯合索引，這樣能夠保證從 city 索引中取出來的數據，天然就是按照 name 遞增排序的，此時的流程變爲了：

是不是效果好多了，而且查詢過程不需要臨時表，也不需要排序，我們用 explain 來驗證下：

可以看到，Extra 中沒有 Using filesort 了，也就是不需要排序了。而且 (city,name) 聯合索引本身有序，掃描行數由之前的 4000 行減少到 1000 行。

你是不是覺得到此爲止了？還可以再優化下哦，如果創建一個 (city,name,age) 的聯合索引，那麼這個聯合索引對於這個 SQL 來說就成了覆蓋索引，流程簡化成了這樣：

來看一下 explain 效果：

可以看到，Extra 中多了 “Using index”，表示使用了覆蓋索引，性能上快了很多。

以上是索引選擇的一個例子，在大家日常業務開發中會有很多遇到索引的情況，一般可考慮：

• **被頻繁查詢的字段：**我們創建索引的字段應該是查詢操作非常頻繁的字段。

• **被作爲條件查詢的字段：**被作爲 WHERE 條件查詢的字段，應該被考慮建立索引。

• **頻繁需要排序的字段：**索引已經排序，這樣查詢可以利用索引的排序，加快排序查詢時間。

• **被經常頻繁用於連接的字段：**經常用於連接的字段可能是一些外鍵列，對於外鍵列並不一定要建立外鍵，只是說該列涉及到表與表的關係。對於頻繁被連接查詢的字段，可以考慮建立索引，提高多表連接查詢的效率。

• 如果一個字段不被經常查詢，反而被經常修改，那麼就更不應該在這種字段上建立索引了。

• 儘可能地考慮建立聯合索引而不是單列索引。每個索引都需要維護一棵 B + 樹，索引佔用的空間也是很多的，且修改索引時，耗費的時間也是較多的。如果是聯合索引，多個字段在一個索引上，那麼將會節約很大磁盤空間，且修改數據的操作效率也會提升。

4.3 索引失效

索引失效也是慢查詢的主要原因之一，常見的導致索引失效的情況有下面這些：

• 使用 SELECT * 進行查詢，優化器可能會認爲全表掃描比索引更高效。

• 創建了聯合索引，但查詢條件未遵守最左匹配原則;

• 在索引列上進行計算、函數、類型轉換等操作;

• 以 % 開頭的 LIKE 查詢比如 like '%abc';

• 查詢條件中使用 or，且 or 的前後條件中有一個列沒有索引，涉及的索引都不會被使用到;

這裏可以展開說明函數和類型轉換爲什麼會導致索引失效。

案例一：函數操作

SQL 語句：

select count(*) from T where month(modified) = 6

這條 SQL 想要檢索 modified 修改時間在 6 月份的數據量有多少。

即使 modified 字段上有索引，你仍會發現 SQL 語句執行了很久。因爲 MySQL 規定：對字段做了函數計算，就不能使用索引。爲什麼條件是 where modified='2024-06-18’的時候可以用上索引，而改成 where month(modified)=6 的時候就不行了？

其實也很簡單，modified 索引樹的每個節點存儲的是 “2024-06-18” 這樣的數據，month(modified)之後的結果是 7，無法在索引樹中進行檢索。最終 MySQL 選擇了全表掃描。

案例二：類型轉換

給定 SQL 語句：

select * from T where age = 20;

設定 age 這個字段上有索引，創建表語句中 age 是 varchar(10)，通過 explain 可以發現，這條 SQL 走了全表掃描，因爲輸入的 age 參數是整數，需要做類型轉換。

對於 MySQL 優化器來說，這條 SQL 等同於：

select * from T where CAST(a ge AS signed int) = 20;

這樣就又回到了對索引字段做函數操作，優化器會放棄走樹搜索功能。

案例三：編碼轉換

如果你需要做兩張表的聯表查詢，但是一張表的編碼是 utf8，另一張表的編碼格式是 utf8mb4，那麼在通過 join 字段連接時用不上關聯字段的索引。utf8 中的一個英文字符佔用一個字節的存儲空間，一箇中文佔用三個字節的存儲空間，不支持 4 個字節的存儲，而 utf8mb4 支持 4 個字節的存儲，可以更好的支持 emoji 表情。

所以在連表查詢時，MySQL 會先將 utf8 字符串轉換爲 utf8mb4 字符集，再做比較。SQL 語句變成了：

select * from T1 where CONVERT(T1.age USING utf8mb4)=T2.age.value;

這樣又回到了對索引字段做函數操作，走不到索引。

05

QA

B 樹與 B + 樹的區別

數據結構上：B 樹所有節點都可包含記錄，而 B + 樹只有葉子節點存儲數據，非葉子節點只用於索引，不存儲實際數據。

更新操作上：B + 樹執行更新需要維護索引的變化以保持有序。

查詢性能上：B 樹通過二分查找，而且是跨層查找，理論上，需要命中的數據離根節點越近性能越高（最好的性能是 O(1)），否則需要多次磁盤訪問，性能較低。B + 樹是數據存儲在葉子節點，通過鏈表定位數據的時間複雜度是 O(log(N))。

使用場景上：B 樹適合隨機訪問的場景，比如文件系統索引；B + 樹適合範圍查詢和順序查詢，比如數據庫索引。

explain 語句

explain 語句也稱爲獲取 MySQL 執行計劃信息，展示一條 SQL 的執行方案。

explain 語句執行結構一共有 12 列，每一列什麼含義和如何分析，百度很多，這裏不展開解釋了。大家也不需要刻意記每個字段什麼含義，需要 explain 時百度下，次數多了自然也就熟悉了。

爲什麼要限制每張表上的索引數量？

索引可以提高查詢效率，是不是一張表上索引越多越好呢，其實不然。索引可以提高效率也可以降低效率，因爲 MySQL 優化器在選擇如何優化 SQL 查詢時，會對每一個索引進行評估，以生成一個最好的執行計劃，如果同時有很多索引都可以使用，就會增加 MySQL 優化器生成執行計劃的時間，同樣會降低查詢性能。所以一般建議單表索引不超過 5 個，根據實際頻繁查詢的字段設置索引。

索引失效的進一步擴展

我們已經知道 MySQL 遇到函數轉換會使索引失效，那麼假定主鍵 id 是 int 類型，如果執行下面 SQL 語句，會導致全表掃描嗎？

select * from T where id = "65535";

你可以去數據庫嘗試下這條 SQL，然後通過 explain 驗證下。其實結論很簡單，這裏進行的是查詢條件的 value 值函數轉換（將 varchar 轉換爲 int），並不是在索引字段 id 上，自然是命中索引的。

【本文作者 - 京東零售京麥研發 - 李澤陽】

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/rF3zP99Bqw7PzVXfqfzF0w