別再說不懂索引了

作者：小林coding 2022-05-27 21:56:55

所謂的存儲引擎，說白了就是如何存儲數(shù)據(jù)、如何為存儲的數(shù)據(jù)建立索引和如何更新、查詢數(shù)據(jù)等技術(shù)的實現(xiàn)方法。MySQL 存儲引擎有 MyISAM 、InnoDB、Memory，其中 InnoDB 是在 MySQL 5.5 之后成為默認的存儲引擎。

大家好，我是小林。

面試中，MySQL 索引相關(guān)的問題基本都是一系列問題，都是先從索引的基本原理，再到索引的使用場景，比如：

索引底層使用了什么數(shù)據(jù)結(jié)構(gòu)和算法?

為什么 MySQL InnoDB 選擇 B+tree 作為索引的數(shù)據(jù)結(jié)構(gòu)?
什么時候適用索引?
什么時候不需要創(chuàng)建索引?
什么情況下索引會失效?
有什么優(yōu)化索引的方法?
.....

今天就帶大家，夯實 MySQL 索引的知識點。

什么是索引?

當你想查閱書中某個知識的內(nèi)容，你會選擇一頁一頁的找呢?還是在書的目錄去找呢?

傻瓜都知道時間是寶貴的，當然是選擇在書的目錄去找，找到后再翻到對應(yīng)的頁。書中的目錄，就是充當索引的角色，方便我們快速查找書中的內(nèi)容，所以索引是以空間換時間的設(shè)計思想。

那換到數(shù)據(jù)庫中，索引的定義就是幫助存儲引擎快速獲取數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)，形象的說就是索引是數(shù)據(jù)的目錄。

下圖是 MySQL 的結(jié)構(gòu)圖，索引和數(shù)據(jù)就是位于存儲引擎中：

索引的分類

你知道索引有哪些嗎?大家肯定都能霹靂啪啦地說出聚簇索引、主鍵索引、二級索引、普通索引、唯一索引、hash索引、B+樹索引等等。

然后再問你，你能將這些索引分一下類嗎?可能大家就有點模糊了。其實，要對這些索引進行分類，要清楚這些索引的使用和實現(xiàn)方式，然后再針對有相同特點的索引歸為一類。

我們可以按照四個角度來分類索引。

按「數(shù)據(jù)結(jié)構(gòu)」分類：B+tree索引、Hash索引、Full-text索引。
按「物理存儲」分類：聚簇索引(主鍵索引)、二級索引(輔助索引)。
按「字段特性」分類：主鍵索引、唯一索引、普通索引、前綴索引。
按「字段個數(shù)」分類：單列索引、聯(lián)合索引。

接下來，按照這些角度來說說各類索引的特點。

按數(shù)據(jù)結(jié)構(gòu)分類

從數(shù)據(jù)結(jié)構(gòu)的角度來看，MySQL 常見索引有 B+Tree 索引、HASH 索引、Full-Text 索引。

每一種存儲引擎支持的索引類型不一定相同，我在表中總結(jié)了 MySQL 常見的存儲引擎 InnoDB、MyISAM 和 Memory 分別支持的索引類型。

InnoDB 是在 MySQL 5.5 之后成為默認的 MySQL 存儲引擎，B+Tree 索引類型也是 MySQL 存儲引擎采用最多的索引類型。

在創(chuàng)建表時，InnoDB 存儲引擎會根據(jù)不同的場景選擇不同的列作為索引：

如果有主鍵，默認會使用主鍵作為聚簇索引的索引鍵(key);
如果沒有主鍵，就選擇第一個不包含 NULL 值的唯一列作為聚簇索引的索引鍵(key);
在上面兩個都沒有的情況下，InnoDB 將自動生成一個隱式自增 id 列作為聚簇索引的索引鍵(key);

其它索引都屬于輔助索引(Secondary Index)，也被稱為二級索引或非聚簇索引。創(chuàng)建的主鍵索引和二級索引默認使用的是 B+Tree 索引。

為了讓大家理解 B+Tree 索引的存儲和查詢的過程，接下來我通過一個簡單例子，說明一下 B+Tree 索引在存儲數(shù)據(jù)中的具體實現(xiàn)。

先創(chuàng)建一張商品表，id 為主鍵，如下：


CREATE TABLE `product`  (
  `id` int(11) NOT NULL,
  `product_no` varchar(20)  DEFAULT NULL,
  `name` varchar(255) DEFAULT NULL,
  `price` decimal(10, 2) DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE
) CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;

商品表里，有這些行數(shù)據(jù)：

這些行數(shù)據(jù)，存儲在 B+Tree 索引時是長什么樣子的?

B+Tree 是一種多叉樹，葉子節(jié)點才存放數(shù)據(jù)，非葉子節(jié)點只存放索引，而且每個節(jié)點里的數(shù)據(jù)是按主鍵順序存放的。每一層父節(jié)點的索引值都會出現(xiàn)在下層子節(jié)點的索引值中，因此在葉子節(jié)點中，包括了所有的索引值信息，并且每一個葉子節(jié)點都指向下一個葉子節(jié)點，形成一個鏈表。

如圖所示：

主鍵索引 B+Tree

通過主鍵查詢商品數(shù)據(jù)的過程

比如，我們執(zhí)行了下面這條查詢語句，這條語句使用了主鍵索引查詢 id 號為 5 的商品。查詢過程是這樣的，B+Tree 會自頂向下逐層進行查找：

將 5 與根節(jié)點的索引數(shù)據(jù) (1，10，20) 比較，5 在 1 和 10 之間，所以根據(jù) B+Tree的搜索邏輯，找到第二層的索引數(shù)據(jù) (1，4，7);
在第二層的索引數(shù)據(jù) (1，4，7)中進行查找，因為 5 在 4 和 7 之間，所以找到第三層的索引數(shù)據(jù)(4，5，6);
在葉子節(jié)點的索引數(shù)據(jù)(4，5，6)中進行查找，然后我們找到了索引值為 5 的行數(shù)據(jù)。

數(shù)據(jù)庫的索引和數(shù)據(jù)都是存儲在硬盤的，我們可以把讀取一個節(jié)點當作一次磁盤 I/O 操作。那么上面的整個查詢過程一共經(jīng)歷了 3 個節(jié)點，也就是進行了 3 次 I/O 操作。

B+Tree 存儲千萬級的數(shù)據(jù)只需要 3-4 層高度就可以滿足，這意味著從千萬級的表查詢目標數(shù)據(jù)最多需要 3-4 次磁盤 I/O，所以B+Tree 相比于 B 樹和二叉樹來說，最大的優(yōu)勢在于查詢效率很高，因為即使在數(shù)據(jù)量很大的情況，查詢一個數(shù)據(jù)的磁盤 I/O 依然維持在 3-4次。

通過二級索引查詢商品數(shù)據(jù)的過程

主鍵索引的 B+Tree 和二級索引的 B+Tree 區(qū)別如下：

主鍵索引的 B+Tree 的葉子節(jié)點存放的是實際數(shù)據(jù)，所有完整的用戶記錄都存放在主鍵索引的 B+Tree 的葉子節(jié)點里;
二級索引的 B+Tree 的葉子節(jié)點存放的是主鍵值，而不是實際數(shù)據(jù)。

我這里將前面的商品表中的 product_no (商品編碼)字段設(shè)置為二級索引，那么二級索引的 B+Tree 如下圖，其中非葉子的 key 值是 product_no(圖中橙色部分)，葉子節(jié)點存儲的數(shù)據(jù)是主鍵值(圖中綠色部分)。

二級索引 B+Tree

如果我用 product_no 二級索引查詢商品，如下查詢語句：

select * from product where product_no = '0002';

會先檢二級索引中的 B+Tree 的索引值(商品編碼，product_no)，找到對應(yīng)的葉子節(jié)點，然后獲取主鍵值，然后再通過主鍵索引中的 B+Tree 樹查詢到對應(yīng)的葉子節(jié)點，然后獲取整行數(shù)據(jù)。這個過程叫「回表」，也就是說要查兩個 B+Tree 才能查到數(shù)據(jù)。如下圖：

回表

不過，當查詢的數(shù)據(jù)是能在二級索引的 B+Tree 的葉子節(jié)點里查詢到，這時就不用再查主鍵索引查，比如下面這條查詢語句：

select id from product where product_no = '0002';

這種在二級索引的 B+Tree 就能查詢到結(jié)果的過程就叫作「覆蓋索引」，也就是只需要查一個 B+Tree 就能找到數(shù)據(jù)。

為什么 MySQL InnoDB 選擇 B+tree 作為索引的數(shù)據(jù)結(jié)構(gòu)?

前面已經(jīng)講了 B+Tree 的索引原理，現(xiàn)在就來回答一下 B+Tree 相比于 B 樹、二叉樹或 Hash 索引結(jié)構(gòu)的優(yōu)勢在哪兒?

1.B+Tree vs B Tree

B+Tree 只在葉子節(jié)點存儲數(shù)據(jù)，而 B 樹的非葉子節(jié)點也要存儲數(shù)據(jù)，所以 B+Tree 的單個節(jié)點的數(shù)據(jù)量更小，在相同的磁盤 I/O 次數(shù)下，就能查詢更多的節(jié)點。

另外，B+Tree 葉子節(jié)點采用的是雙鏈表連接，適合 MySQL 中常見的基于范圍的順序查找，而 B 樹無法做到這一點。

2.B+Tree vs 二叉樹

對于有 N 個葉子節(jié)點的 B+Tree，其搜索復(fù)雜度為O(logdN)，其中 d 表示節(jié)點允許的最大子節(jié)點個數(shù)為 d 個。

在實際的應(yīng)用當中， d 值是大于100的，這樣就保證了，即使數(shù)據(jù)達到千萬級別時，B+Tree 的高度依然維持在 3~4 層左右，也就是說一次數(shù)據(jù)查詢操作只需要做 3~4 次的磁盤 I/O 操作就能查詢到目標數(shù)據(jù)。

而二叉樹的每個父節(jié)點的兒子節(jié)點個數(shù)只能是 2 個，意味著其搜索復(fù)雜度為 O(logN)，這已經(jīng)比 B+Tree 高出不少，因此二叉樹檢索到目標數(shù)據(jù)所經(jīng)歷的磁盤 I/O 次數(shù)要更多。

3.B+Tree vs Hash

Hash 在做等值查詢的時候效率賊快，搜索復(fù)雜度為 O(1)。

但是 Hash 表不適合做范圍查詢，它更適合做等值的查詢，這也是 B+Tree 索引要比 Hash 表索引有著更廣泛的適用場景的原因。

按物理存儲分類

從物理存儲的角度來看，索引分為聚簇索引(主鍵索引)、二級索引(輔助索引)。

這兩個區(qū)別在前面也提到了：

主鍵索引的 B+Tree 的葉子節(jié)點存放的是實際數(shù)據(jù)，所有完整的用戶記錄都存放在主鍵索引的 B+Tree 的葉子節(jié)點里;
二級索引的 B+Tree 的葉子節(jié)點存放的是主鍵值，而不是實際數(shù)據(jù)。

所以，在查詢時使用了二級索引，如果查詢的數(shù)據(jù)能在二級索引里查詢的到，那么就不需要回表，這個過程就是覆蓋索引。如果查詢的數(shù)據(jù)不在二級索引里，就會先檢索二級索引，找到對應(yīng)的葉子節(jié)點，獲取到主鍵值后，然后再檢索主鍵索引，就能查詢到數(shù)據(jù)了，這個過程就是回表。

按字段特性分類

從字段特性的角度來看，索引分為主鍵索引、唯一索引、普通索引、前綴索引。

主鍵索引

主鍵索引就是建立在主鍵字段上的索引，通常在創(chuàng)建表的時候一起創(chuàng)建，一張表最多只有一個主鍵索引，索引列的值不允許有空值。

在創(chuàng)建表時，創(chuàng)建主鍵索引的方式如下：

CREATE TABLE table_name  (
  ....
  PRIMARY KEY (index_column_1) USING BTREE
);

唯一索引

唯一索引建立在 UNIQUE 字段上的索引，一張表可以有多個唯一索引，索引列的值必須唯一，但是允許有空值。

在創(chuàng)建表時，創(chuàng)建唯一索引的方式如下：

CREATE TABLE table_name  (
  ....
  UNIQUE KEY(index_column_1,index_column_2,...) 
);

建表后，如果要創(chuàng)建唯一索引，可以使用這面這條命令：

CREATE UNIQUE INDEX index_name
ON table_name(index_column_1,index_column_2,...);

普通索引

普通索引就是建立在普通字段上的索引，既不要求字段為主鍵，也不要求字段為 UNIQUE。

在創(chuàng)建表時，創(chuàng)建普通索引的方式如下：

CREATE TABLE table_name  (
  ....
  INDEX(index_column_1,index_column_2,...) 
);

建表后，如果要創(chuàng)建普通索引，可以使用這面這條命令：


CREATE INDEX index_name
ON table_name(index_column_1,index_column_2,...);

前綴索引

前綴索引是指對字符類型字段的前幾個字符建立的索引，而不是在整個字段上建立的索引，前綴索引可以建立在字段類型為 char、 varchar、binary、varbinary 的列上。

使用前綴索引的目的是為了減少索引占用的存儲空間，提升查詢效率。

在創(chuàng)建表時，創(chuàng)建前綴索引的方式如下：

CREATE TABLE table_name(
    column_list,
    INDEX(column_name(length))
);

建表后，如果要創(chuàng)建前綴索引，可以使用這面這條命令：

CREATE INDEX index_name
ON table_name(column_name(length));

按字段個數(shù)分類

從字段個數(shù)的角度來看，索引分為單列索引、聯(lián)合索引(復(fù)合索引)。

建立在單列上的索引稱為單列索引，比如主鍵索引;
建立在多列上的索引稱為聯(lián)合索引;

聯(lián)合索引

通過將多個字段組合成一個索引，該索引就被稱為聯(lián)合索引。比如將商品表中的 product_no 和 name 字段組合成聯(lián)合索引 (product_no, name)，創(chuàng)建聯(lián)合索引的方式如下：

CREATE INDEX index_product_no_name ON product(product_no, name);

聯(lián)合索引 (product_no, name) 的 B+Tree 示意圖如下：

聯(lián)合索引

可以看到，聯(lián)合索引的非葉子節(jié)點保持了兩個字段的值作為 B+Tree 的 key 值。當在聯(lián)合索引查詢數(shù)據(jù)時，先按 product_no 字段比較，在 product_no 相同的情況下按 name 字段比較。

也就是說，聯(lián)合索引查詢的 B+Tree 是先按 product_no 進行排序，然后再 product_no 相同的情況再按 name 字段排序。因此，使用聯(lián)合索引時，存在最左匹配原則，也就是按照最左優(yōu)先的方式進行索引的匹配。

比如，如果創(chuàng)建了一個 (a, b, c) 聯(lián)合索引，如果查詢條件是以下這幾種，就可以匹配上聯(lián)合索引：

where a=1;
where a=1 and b=2 and c=3;
where a=1 and b=2;

需要注意的是，因為有查詢優(yōu)化器，所以 a 字段在 where 子句的順序并不重要。

但是，如果查詢條件是以下這幾種，因為不符合最左匹配原則，所以就無法匹配上聯(lián)合索引，聯(lián)合索引就會失效:

where b=2;
where c=3;
where b=2 and c=3;

另外，建立聯(lián)合索引時的字段順序，對索引效率也有很大影響。越靠前的字段被用于索引過濾的概率越高，實際開發(fā)工作中建立聯(lián)合索引時，要把區(qū)分度大的字段排在前面，這樣區(qū)分度大的字段越有可能被更多的 SQL 使用到。

區(qū)分度就是某個字段 column 不同值的個數(shù)「除以」表的總行數(shù)，計算公式如下：

區(qū)分度計算公式

比如，性別的區(qū)分度就很小，不適合建立索引或不適合排在聯(lián)合索引列的靠前的位置，而 UUID 這類字段就比較適合做索引或排在聯(lián)合索引列的靠前的位置。

這里出一個題目考查大家，針對針對下面這條 SQL，你怎么通過索引來提高查詢效率呢?

select * from product where status = 1 order by create_time asc

有的同學(xué)會認為，單獨給 status 建立一個索引就可以了。

但是更好的方式給 status 和 create_time 列建立一個聯(lián)合索引，因為這樣可以避免 MySQL 數(shù)據(jù)庫發(fā)生文件排序。

因為在查詢時，如果只用到 status 的索引，但是這條語句還要對 create_time 排序，這時就要用文件排序 filesort，也就是在 SQL 執(zhí)行計劃中，Extra 列會出現(xiàn) Using filesort。

所以，要利用索引的有序性，在 status 和 create_time 列建立聯(lián)合索引，這樣根據(jù) status 篩選后的數(shù)據(jù)就是按照 create_time 排好序的，避免在文件排序，提高了查詢效率。

什么時候需要 / 不需要創(chuàng)建索引?

索引最大的好處是提高查詢速度，但是索引也是有缺點的，比如：

需要占用物理空間，數(shù)量越大，占用空間越大;
創(chuàng)建索引和維護索引要耗費時間，這種時間隨著數(shù)據(jù)量的增加而增大;
會降低表的增刪改的效率，因為每次增刪改索引，都需要進行動態(tài)維護。

所以，索引不是萬能鑰匙，它也是根據(jù)場景來使用的。

什么時候適用索引?

字段有唯一性限制的，比如商品編碼;
經(jīng)常用于 WHERE 查詢條件的字段;
經(jīng)常用于 GROUP BY 和 ORDER BY 的字段;

什么時候不需要創(chuàng)建索引?

WHERE 條件，GROUP BY，ORDER BY 里用不到的字段，索引的價值是快速定位，如果起不到定位的字段通常是不需要創(chuàng)建索引的。
字段中存在大量重復(fù)數(shù)據(jù)，不需要創(chuàng)建索引，比如性別字段，只有男女。
表數(shù)據(jù)太少的時候，不需要創(chuàng)建索引;
經(jīng)常更新的字段不用創(chuàng)建索引，比如電商項目的用戶余額，因為索引字段頻繁修改，那就意味著需要頻繁的重建索引;

有什么優(yōu)化索引的方法?

這里說一下幾種常見優(yōu)化索引的方法：

前綴索引優(yōu)化;
覆蓋索引優(yōu)化;
主鍵索引最好是自增的;
防止索引失效;

前綴索引優(yōu)化

前綴索引顧名思義就是使用某個字段中字符串的前幾個字符建立索引，那我們?yōu)槭裁葱枰褂们熬Y來建立索引呢?

使用前綴索引是為了減小索引字段大小，可以增加一個索引頁中存儲的索引值，有效提高索引的查詢速度。在一些大字符串的字段作為索引時，使用前綴索引可以幫助我們減小索引項的大小。

不過，前綴索引有一定的局限性，例如：

order by 就無法使用前綴索引;
無法把前綴索引用作覆蓋索引;

覆蓋索引優(yōu)化

覆蓋索引是指 SQL 中 query 的所有字段，在索引 B+Tree 的葉子節(jié)點上都能找得到的那些索引，從二級索引中查詢得到記錄，而不需要通過聚簇索引查詢獲得，可以避免回表的操作。

假設(shè)我們只需要查詢商品的名稱、價格，有什么方式可以避免回表呢?

我們可以建立一個聯(lián)合索引，即「商品ID、名稱、價格」作為一個聯(lián)合索引。如果索引中存在這些數(shù)據(jù)，查詢將不會再次檢索主鍵索引，從而避免回表。

所以，使用覆蓋索引的好處就是，不需要查詢出包含整行記錄的所有信息，也就減少了大量的 I/O 操作。

主鍵索引最好是自增的

我們在建表的時候，都會默認將主鍵索引設(shè)置為自增的，具體為什么要這樣做呢?又什么好處?

InnoDB 創(chuàng)建主鍵索引默認為聚簇索引，數(shù)據(jù)被存放在了 B+Tree 的葉子節(jié)點上。也就是說，同一個葉子節(jié)點內(nèi)的各個數(shù)據(jù)是按主鍵順序存放的，因此，每當有一條新的數(shù)據(jù)插入時，數(shù)據(jù)庫會根據(jù)主鍵將其插入到對應(yīng)的葉子節(jié)點中。

如果我們使用自增主鍵，那么每次插入的新數(shù)據(jù)就會按順序添加到當前索引節(jié)點的位置，不需要移動已有的數(shù)據(jù)，當頁面寫滿，就會自動開辟一個新頁面。因為不需要重新移動數(shù)據(jù)，因此這種插入數(shù)據(jù)的方法效率非常高。

如果我們使用非自增主鍵，由于每次插入主鍵的索引值都是隨機的，因此每次插入新的數(shù)據(jù)時，就可能會插入到現(xiàn)有數(shù)據(jù)頁中間的某個位置，這將不得不移動其它數(shù)據(jù)來滿足新數(shù)據(jù)的插入，甚至需要從一個頁面復(fù)制數(shù)據(jù)到另外一個頁面，我們通常將這種情況稱為頁分裂。頁分裂還有可能會造成大量的內(nèi)存碎片，導(dǎo)致索引結(jié)構(gòu)不緊湊，從而影響查詢效率。

舉個例子，假設(shè)某個數(shù)據(jù)頁中的數(shù)據(jù)是1、3、5、9，且數(shù)據(jù)頁滿了，現(xiàn)在準備插入一個數(shù)據(jù)7，則需要把數(shù)據(jù)頁分割為兩個數(shù)據(jù)頁：

innodb頁分裂

出現(xiàn)頁分裂時，需要將一個頁的記錄移動到另外一個頁，性能會受到影響，同時頁空間的利用率下降，造成存儲空間的浪費。

而如果記錄是順序插入的，例如插入數(shù)據(jù)11，則只需開辟新的數(shù)據(jù)頁，也就不會發(fā)生頁分裂：

開辟新數(shù)據(jù)頁

因此，在使用 InnoDB 存儲引擎時，如果沒有特別的業(yè)務(wù)需求，建議使用自增字段作為主鍵。

防止索引失效

用上了索引并不意味著查詢的時候會使用到索引，所以我們心里要清楚有哪些情況會導(dǎo)致索引失效，從而避免寫出索引失效的查詢語句，否則這樣的查詢效率是很低的。

我之前寫過索引失效的文章，想詳細了解的可以去看這篇文章：誰還沒碰過索引失效呢?

這里簡單說一下，發(fā)生索引失效的情況：

當我們使用左或者左右模糊匹配的時候，也就是 like %xx 或者 like %xx%這兩種方式都會造成索引失效;
當我們在查詢條件中對索引列做了計算、函數(shù)、類型轉(zhuǎn)換操作，這些情況下索引失效是因為查詢過程需要掃描整個索引并回表，代價高于直接全表掃描，所以優(yōu)化最終選擇走全表掃描。
聯(lián)合索引要能正確使用需要遵循最左匹配原則，也就是按照最左優(yōu)先的方式進行索引的匹配，否則就會導(dǎo)致索引失效。
在 WHERE 子句中，如果在 OR 前的條件列是索引列，而在 OR 后的條件列不是索引列，那么索引會失效。
為了更好的利用索引，索引列要設(shè)置為 NOT NULL 約束。

我上面說的是常見的索引失效場景，實際過程中，可能會出現(xiàn)其他的索引失效場景，這時我們就需要查看執(zhí)行計劃，通過執(zhí)行計劃顯示的數(shù)據(jù)判斷查詢語句是否使用了索引。

如下圖，就是一個沒有使用索引，并且是一個全表掃描的查詢語句。

對于執(zhí)行計劃，參數(shù)有：

possible_keys 字段表示可能用到的索引;
key 字段表示實際用的索引，如果這一項為 NULL，說明沒有使用索引;
key_len 表示索引的長度;
rows 表示掃描的數(shù)據(jù)行數(shù)。
type 表示數(shù)據(jù)掃描類型，我們需要重點看這個。

type 字段就是描述了找到所需數(shù)據(jù)時使用的掃描方式是什么，常見掃描類型的執(zhí)行效率從低到高的順序為：

ALL(全表掃描);
index(全索引掃描);
range(索引范圍掃描);
ref(非唯一索引掃描);
eq_ref(唯一索引掃描);
const(結(jié)果只有一條的主鍵或唯一索引掃描)。

考慮到查詢效率問題，全表掃描和全索引掃描要盡量避免。

總結(jié)

這次主要介紹了索引的原理、分類和使用。我把重點總結(jié)在了下面這個表格

責任編輯：武曉燕來源：小林coding

索引存儲 MySQL 存儲引擎