看這篇就夠了！MySQL 索引知識點超全總結

作者：fanili，騰訊 WXG 后臺開發工程師

知其然知其所以然！本文介紹索引的數據結構、查找算法、常見的索引概念和索引失效場景。

什么是索引？

在關系數據庫中，索引是一種單獨的、物理的對數據庫表中一列或多列的值進行排序的一種存儲結構，它是某個表中一列或若干列值的集合和相應的指向表中物理標識這些值的數據頁的邏輯指針清單。索引的作用相當于圖書的目錄，可以根據目錄中的頁碼快速找到所需的內容。（百度百科）

索引的目的是提高查找效率，對數據表的值集合進行了排序，并按照一定數據結構進行了存儲。

本文將從一個案例開始，從索引的數據結構、分類、關鍵概念及如何使用索引提高查找效率等方面對索引知識進行總結。

從一個案例開始

現象

業務中有個既存的歷史 SQL 語句在運行時會導致 DB 服務器過載，進而導致相關服務阻塞無法及時完成。CPU 監控曲線如下：

從 DB 的 CPU 使用率曲線可以看到業務運行一直處于“亞健康”狀態（1），隨著業務的增長隨時都可能出現問題。這種問題（2）在 11 月 11 日凌晨出現，當時 DB CPU 一直處于 100%高負荷狀態，且存在大量的慢查詢語句。最終以殺死進程降低 DB 負載、減少業務進程（3）的方式恢復業務。

在 11 月 11 日下午，對該業務的 SQL 語句進行了優化，優化的效果如下。業務運行時的 CPU 使用率峰值有很大的降低（對比圖 2 的 1，2，3 可見）；慢查詢語句幾乎在監控曲線上也無法明顯觀察到（對比圖 3 的 1，2，3 可見）。

分析

表結構

CREATE TABLE T_Mch******Stat (`FStatDate` int unsigned NOT NULL DEFAULT 19700101 COMMENT '統計日期',
`FMerchantId` bigint unsigned NOT NULL DEFAULT 0 COMMENT '商戶ID',
`FVersion` int unsigned NOT NULL DEFAULT 0 COMMENT '數據版本號',
`FBatch` bigint unsigned NOT NULL DEFAULT 0 COMMENT '統計批次',
`FTradeAmount` bigint NOT NULL DEFAULT 0 COMMENT '交易金額'
PRIMARY KEY (`FStatDate`,`FMerchantId`,`FVersion`),
INDEX i_FStatDate_FVersion (`FStatDate`,`FVersion`))
DEFAULT CHARSET = utf8 ENGINE = InnoDB;

從建表語句可以知道該表有兩個索引：

主鍵索引，是一個組合索引，由字段 FStateDate、FMerchantId 和 FVersion 組成；
普通索引，是一個組合索引，由字段 FStateDate 和 FVersion 組成；

優化前的 SQL 語句（做了部分裁剪）A：

SELECT SQL_CALC_FOUND_ROWS FStatDate,
    FMerchantId,
    FVersion,
    FBatch,
    FTradeAmount,
    FTradeCount
FROM T_Mch******Stat_1020
WHERE FStatDate = 20201020
    AND FVersion = 0
    AND FMerchantId > 0
ORDER BY FMerchantId ASC LIMIT 0, 8000

對該 SQL 進行 explain 得到如下結果，Extra 字段的值為 using where，說明并沒有使用到索引。

優化后的 SQL 語句（做了部分裁剪）B：

SELECT SQL_CALC_FOUND_ROWS a1.FStatDate,
    a1.FMerchantId,
    a1.FVersion,
    FBatch,
    FTradeAmount,
    FTradeCount
FROM T_Mch******Stat_1020 a1, (
    SELECT FStatDate, FMerchantId, FVersion
    FROM T_Mch******Stat_1020
    WHERE FStatDate = 20201020
        AND FVersion = 0
        AND FMerchantId > 0
        ORDER BY FMerchantId ASC LIMIT 0, 8000 ) a2
where a1.FStatDate = a2.FStatDate
    and a1.FVersion = a2.FVersion
    and a1.FMerchantId = a2.FMerchantId;

優化關鍵步驟為：

新增一個子查詢，select 字段只有主鍵字段；

該 SQL 的 explain 結果如下，子查詢語句使用了索引，而最終在線上運行結果也證明了優化效果顯著。

疑問

優化后的 SQL 語句 B 比原來的 SQL 語句 A 復雜的多（子查詢，臨時表關聯等），怎么效率會提升，違反直覺？有三個疑問：

SQL 語句 A 的查詢條件字段都在主鍵中，主鍵索引用到了沒？
SQL 語句 B 的子查詢為什么能夠用到索引？
前后兩條語句執行流程的差異是什么？

索引的數據結構

在 MySQL 中，索引是在存儲引擎層實現的，而不同的存儲引擎根據其業務場景特點會有不同的實現方式。這里會先介紹我們常見的有序數組、Hash 和搜索樹，最后看下 Innodb 的引擎支持的 B+樹。

有序數組

數組是在任何一本數據結構和算法的書籍都會介紹到的一種重要的數據結構。有序數組如其字面意思，以 Key 的遞增順序保存數據在數組中。非常適合等值查詢和范圍查詢。

ID：1ID：2......ID:N

在 ID 值沒有重復的情況下，上述數組按照 ID 的遞增順序進行保存。這個時候如果需要查詢特定 ID 值的 name，用二分法就可以快速得到，時間復雜度是 O(logn)。

// 二分查找遞歸實現方式
int binary_search(const int arr[], int start, int end, int key)
{
    if (start > end)
        return -1;

    int mid = start + (end - start) / 2;
    if (arr[mid] > key)
        return binary_search(arr, start, mid - 1, key);
    else if (arr[mid] < key)
        return binary_search(arr, mid + 1, end, key);
    else
        return mid;
}

有序數組的優點很明顯，同樣其缺點也很明顯。其只適合靜態數據，如遇到有數據新增插入，則就會需要數據移動（新申請空間、拷貝數據和釋放空間等動作），這將非常消耗資源。

Hash

哈希表是一種以鍵-值（K-V）存儲數據的結構，我們只需要輸入鍵 K，就可以找到對應的值 V。哈希的思路是用特定的哈希函數將 K 換算到數組中的位置，然后將值 V 放到數組的這個位置。如果遇到不同的 K 計算出相同的位置，則在這個位置拉出一個鏈表依次存放。哈希表適用于等值查詢的場景，對應范圍查詢則無能為力。

二叉搜索樹

二叉搜索樹，也稱為二叉查找樹、有序二叉樹或排序二叉樹，是指一顆空樹或者具有以下性質的二叉樹：

若任意節點的左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；
若任意節點的右子樹不空，則右子樹上所有節點的值均大于或等于它的根節點的值；
任意節點的左、右子樹也分別為二叉查找樹；

二叉搜索樹相比于其它數據結構的優勢在于查找、插入的時間復雜度較低，為 O(logn)。為了維持 O(logn)的查詢復雜度，需要保持這棵樹是平衡二叉樹。

二叉搜索樹的查找算法：

若 b 是空樹，則搜索失敗，否則：
若 x 等于 b 的根節點的值，則查找成功；否則：
若 x 小于 b 的根節點的值，則搜索左子樹；否則：
查找右子樹。

相對于有序數組和 Hash，二叉搜索樹在查找和插入兩端的表現都非常不錯。后續基于此不斷的優化，發展出 N 叉樹等。

B+樹

Innodb 存儲引擎支持 B+樹索引、全文索引和哈希索引。其中 Innodb 存儲引擎支持的哈希索引是自適應的，Innodb 存儲引擎會根據表的使用情況自動為表生成哈希索引，不能人為干預。B+樹索引是關系型數據庫中最常見的一種索引，也將是本文的主角。

數據結構

在前文簡單介紹了有序數組和二叉搜索樹，對二分查找法和二叉樹有了基本了解。B+樹的定義相對復雜，在理解索引工作機制上無須深入、只需理解數據組織形式和查找算法即可。我們可以簡單的認為 B+樹是一種 N 叉樹和有序數組的結合體。

例如：

B+樹的 3 個優點:

層級更低，IO 次數更少
每次都需要查詢到葉子節點，查詢性能穩定
葉子節點形成有序鏈表，范圍查詢方便

操作算法

查找

由根節點自頂向下遍歷樹，根據分離值在要查找的一邊的指針；在節點內使用二分查找來確定位置。

插入

Leaf Page（葉子）滿Index Page（索引）滿操作

刪除

葉子節點小于填充因子中間節點小于填充因子操作

注：插入和刪除兩個表格內容來自《MySQL 技術內幕-InnoDB 存儲引擎》

填充因子（innodb_fill_factor）：索引構建期間填充的每個 B-tree 頁面上的空間百分比，其余空間保留給未來索引增長。從插入和刪除操作中可以看到填充因子的值會影響到數據頁的 split 和 merge 的頻率。將值設置小些，可以減少 split 和 merge 的頻率，但是索引相對會占用更多的磁盤空間；反之，則會增加 split 和 merge 的頻率，但是可以減少占用磁盤空間。Innodb 對于聚集索引默認會預留 1/16 的空間保證后續的插入和升級索引。

Innodb B+樹索引

前文介紹了索引的基本數據結構，現在開始我們從 Innodb 的角度了解如何使用 B+樹構建索引，索引如何工作和如何使用索引提升查找效率。

聚集索引和非聚集索引

數據庫中的 B+樹索引可以分為聚集索引和非聚集索引。聚集索引和非聚集索引的不同點在于葉子節點是否是完整行數據。

Innodb 存儲引擎表是索引組織表，即表中的數據按照主鍵順序存放。聚集索引就是按照每張表的主鍵構造一棵 B+樹，葉子節點存放的是表的完整行記錄。非聚集索引的葉子節點不包含行記錄的全部數據。Innodb 存儲引擎的非聚集索引的葉子節點的內容為主鍵索引值。

若數據表沒有主鍵聚集索引是怎么建立的？在沒有主鍵時 Innodb 會給數據表的每條記錄生成一個 6 個字節長度的 RowId 字段，會以此建立聚集索引。

Select 語句查找記錄的過程

下面例子將展示索引數據的組織形式及 Select 語句查詢數據的過程。

建表語句：

create table T (
    ID int primary key,
    k int NOT NULL DEFAULT 0,
    s varchar(16) NOT NULL DEFAULT '',
    index k(k)
) engine=InnoDB DEFAULT CHARSET=utf8;

insert into T values(100, 1, 'aa'),(200, 2, 'bb'),(300, 3, 'cc'),(500, 5, 'ee'),(600,6,'ff'),(700,7,'gg');

索引結構示意

左邊是以主鍵 ID 建立起的聚集索引，其葉子節點存儲了完整的表記錄信息；右邊是以普通字段 K 建立的普通索引，其葉子節點的值是主鍵 ID。

Select 語句執行過程

select * from T where k between 3 and 5;

執行流程如下：

在 K 索引樹上找到 k=3 的記錄，取得 ID=300；
再到 ID 索引樹上查找 ID=300 對應的 R3；
在 k 索引樹取下一個值 k=5，取得 ID=500；
再回到 ID 索引樹查到 ID=500 對應的 R4；
在 k 索引樹取下一個值 k=6，不滿足條件，循環結束。

上述查找記錄的過程中引入了一個重要的概念：回表，即回到主鍵索引樹搜索的過程。避免回表操作是提升 SQL 查詢效率的常規思路及重要方法。那么如何避免回表？

注：該例子來自《MySQL 實戰 45 講》

覆蓋索引

MySQL 5.7,建表語句：

CREATE TABLE `employees` (
  `emp_no` int(11) NOT NULL,
  `birth_date` date NOT NULL,
  `first_name` varchar(14) NOT NULL,
  `last_name` varchar(16) NOT NULL,
  `gender` enum('M','F') NOT NULL,
  `hire_date` date NOT NULL,
  PRIMARY KEY (`emp_no`),
  KEY `i_first_name` (`first_name`),
  KEY `i_hire_date` (`hire_date`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

SQL 語句 A

explain select * from employees where hire_date > '1990-01-14';

explain 結果：

SQL 語句 B

explain select emp_no from employees where hire_date > '1990-01-14';

explain 結果：

分析

從前后兩次 explain 的結果可以看到 SQL 語句 A 的 extra 為 using where，SQL 語句 B 的 extra 為 using where;using index。這說明 A 沒有使用索引，而 B 使用了索引。

索引 K 中包含了查詢語句所需要的字段 ID 的值，無需再次回到主鍵索引樹查找，也就是“覆蓋”了我們的查詢需求，我們稱之為覆蓋索引。覆蓋索引可以減少樹的搜索次數，顯著提升查詢性能。

最左匹配

SQL 語句 A

explain select * from employees where hire_date > '1990-01-14' and first_name like '%Hi%';

SQL 語句 B

explain select * from employees where hire_date > '1990-01-14' and first_name like 'Hi%';

分析

在上述測試的 SQL 語句 A 使用了極端方式: first_name like '%Hi%'，前后都增加模糊匹配使得 SQL 語句無法使用到索引；當去掉最左邊的‘%’后，SQL 語句 B 就使用了索引。最左匹配可以是字符串索引的最左 N 個字符，也可以是聯合索引的最左 M 的字段。合理規劃、使用最左匹配可以減少索引，從而節約磁盤空間。

索引下推

何為索引下推？我們先從下面這組對比測試開始，將在 MySQL5.5 版本和 MySQL5.7 版本中執行同一條 SQL 語句：

select * from employees where hire_date > '1990-01-14' and first_name like 'Hi%';

在 MySQL 5.5 執行 explain，extra 字段的值顯示沒有使用索引

執行查詢花費時間為 0.12s

在 MySQL 5.7 執行 explain，extra 字段的值顯示使用了索引下推

執行查詢花費時間為 0.02s

索引下推

explain 結果中的 extra 字段值包含 using index condition，則說明使用了索引下推。索引下推功能是從 5.6 版本開始支持的。在 5.6 版本之前，i_first_name 索引是沒有使用上的，需要每次去主鍵索引表取完整的記錄值進行比較。從 5.6 版本開始，由于索引 i_first_name 的存在，可以直接取索引的 first_name 值進行過濾，這樣不符合"first_name like 'Hi%'"條件的記錄就不再需要回表操作。

MRR 優化

MySQL 5.6 版本開始支持 Multi-Range Read(MRR)優化，MRR 優化的目的是為減少磁盤的隨機訪問，并且將隨機訪問轉化為較為順序的數據訪問，對于 IO-bound 類型的 SQL 查詢語句可帶來性能極大提升。我們先看下對比測試，以下測試語句在同一個 MySQL 實例下執行，執行前均進行 mysql 服務重啟，以保證緩存此沒被預熱。

關閉 MRR

SET @@optimizer_switch='mrr=off';
select * from employees where hire_date > '1990-01-14' and first_name like 'Hi%';

執行耗時為 0.90s

開啟 MRR

SET @@optimizer_switch='mrr=on,mrr_cost_based=off';
 select * from employees where hire_date > '1990-01-14' and first_name like 'Hi%';

分析

從測試結果可以發現在 mrr 從關閉到開啟，耗時從 0.90s 減少到 0.03s，查詢速率達到 30 倍的提升。

常見的索引失效場景

在 MySQL 表中建立了索引，SQL 查詢語句就會一定使用到索引么？不一定，存在著索引失效的場景。我們給 employees 表增一個組合索引，后續例子均基于此表進行分析、測試。

alter table employees add index i_b_f_l(birth_date, first_name, last_name)
alter table employees add index i_h(hire_date);

失效場景

范圍查詢（>,<,<>）

explain select * from employees where hire_date > '1989-06-02';

查詢條件類型不一致

alter table employees add index i_first_name (first_name);
explain select * from employees where first_name = 1;

查詢條件使用了函數

explain select * from employees where CHAR_LENGTH(hire_date) = 10;

模糊查詢

explain select * from employees where hire_date  like  '%1995';

不使用組合索引的首個字段當條件

explain select * from employees where last_name = 'Kalloufi' and first_name = 'Saniya';

為什么會失效？

順序讀比離散讀性能要好
范圍查詢一定會導致索引失效么？并不會！稍微更改下查詢條件看下 explain 的對比結果，可以看到新語句用到索引下推，說明索引并未失效。為什么？在不使用覆蓋索引的情況下，優化器只有在數據量小的時候才會選擇使用非聚集索引。受制于傳統的機械磁盤特性，通過聚集索引順序讀數據行的性能會比通過非聚集索引離散讀數據行要好。所以，優化器在即使有非聚集索引、但是訪問數據量可能達到送記錄數的 20%時會選擇聚集索引。當然也可以用 Force index 強制使用索引。

explain select * from employees where hire_date > '1999-06-02';

無法使用 B+索引快速查找
B+樹索引支持快速查詢的基本要素是因為其索引鍵值是有序存儲的，從左到右由小到大，這樣就可以在每個層級的節點中快速查并進入下一層級，最終在葉子節點找到對應的值。使用函數會使得 MySQL 無法使用索引進行快速查詢，因為對索引字段做函數操作會破壞索引值的有序性，所以優化器選擇不使用索引。而查詢條件類型不一致其實也是同樣的情況，因為其使用了隱式類型轉換*。

模糊匹配和不使用組合索引的首字段作為查詢條件均是無法快速定位索引位置從而導致無法使用索引。模糊匹配當查詢條件是 lwhere A ike 'a%'，a 是 A 的最左前綴時是可能用上索引的（最左匹配），是否用上最終還是依賴優化器對查詢數據量的評估。

回到初始的案例

讓我們回到文章初的案例，嘗試回答下當時提出的 3 個問題。

-- A語句
SELECT FStatDate, FMerchantId, FVersion, FBatch, FTradeAmount, FTradeCount FROM T_Mch******Stat_1020 WHERE FStatDate = 20201020     AND FVersion = 0     AND FMerchantId > 0 ORDER BY FMerchantId ASC LIMIT 0, 8000;

-- B語句
SELECT SQL_CALC_FOUND_ROWS a1.FStatDate,
    a1.FMerchantId,
    a1.FVersion,
    FBatch,
    FTradeAmount,
    FTradeCount
FROM T_Mch******Stat_1020 a1, (
    SELECT FStatDate, FMerchantId, FVersion
    FROM T_Mch******Stat_1020
    WHERE FStatDate = 20201020
        AND FVersion = 0
        AND FMerchantId > 0
        ORDER BY FMerchantId ASC LIMIT 0, 8000 ) a2
where a1.FStatDate = a2.FStatDate
    and a1.FVersion = a2.FVersion
    and a1.FMerchantId = a2.FMerchantId;

SQL 語句 A 的查詢條件字段都在主鍵中，主鍵索引用到了沒？

主鍵索引其實是有被使用的：索引的范圍查詢，只是其需要逐條讀取和解析所有記錄才導致慢查詢。

SQL 語句 B 的子查詢為什么能夠用到索引？

前文中我們介紹了聚集索引，其索引鍵值就是主鍵。
兩條 SQL 語句的不同之處在于 B 語句的子查詢語句的 Select 字段都包含在主鍵字段中，而 A 語句還有其它字段（例如 FBatch 和 FTradeAmount 等）。這種情況下只憑主鍵索引的鍵值就能滿足 B 語句的字段要求；A 語句則需要逐條取整行記錄進行解析。

前后兩條語句執行流程的差異是什么？

SQL 語句 A 的執行過程：

逐條掃描索引表并比較查詢條件
遇到符合查詢條件的則讀取整行數據返回
回到 a 步驟，直至完成所有索引記錄的比較
對返回的所有符合條件的記錄（完整的記錄）進行排序
選取前 8000 條數據返回

SQL 語句 B 的執行過程：

逐條掃描索引表并比較查詢條件
遇到符合查詢條件的則從索引鍵中取相關字段值返回
回到 a 步驟，直至完成所有索引記錄的比較
對返回的所有符合條件的記錄（每條記錄只有 3 個主鍵）進行排序
選取前 8000 條數據返回形成臨時表
關聯臨時表與主表，使用主鍵相等比較查詢 8000 條數據

對比兩個 SQL 語句的執行過程，可以發現差異點集中在步驟 2 和步驟 4。在步驟 2 中 SQL 語句 A 需要隨機讀取整行數據并解析非常耗資源；步驟 4 涉及 MySQL 的排序算法，這里也會對執行效率有影響，排序效果上看 SQL 語句 B 比 SQL 語句 A 好。

名詞解釋

主鍵索引

顧名思義該類索引由表的主鍵組成，從左到右由小到大排序。一個 Innodb 存儲表只有一張主鍵索引表（聚集索引）。

普通索引

最為平常的一種索引，沒有特別限制。

唯一索引

該索引的字段不能有相同值，但允許有空值。

組合索引

由多列字段組合而成的索引，往往是為了提升查詢效率而設置。

總結

在文章開始時介紹了常見的幾種索引數據結構，適合靜態數據的有序數組、適合 KV 結構的哈希索引及兼顧查詢及插入性能的搜索二叉樹；然后介紹了 Innodb 的常見索引實現方式 B+樹及 Select 語句使用 B+樹索引查找記錄的執行過程，在這個部分我們了解了幾個關鍵的概念，回表、覆蓋索引、最左匹配、索引下推和 MMR；之后還總結了索引的失效場景及背后的原因。最后，我們回到最初的案例，分析出優化前后 SQL 語句在使用索引的差異，進而導致執行效率的差異。

本文介紹了索引的一些粗淺知識，希望能夠對讀者有些許幫助。作為階段性學習的一個總結，文章對 MySQL 索引的相關知識基本上是淺嘗輒止，日后還需多多使用和深入學習。

何以解憂？唯有學習。