MySQL實戰-4 | 深入淺出索引（上）（下）

什么是數據庫索引，索引又是如何工作的呢？

一句話簡單來說，索引的出現其實就是為了提高數據查詢的效率，就像書的目錄一樣。一本 500 頁的書，如果你想快速找到其中的某一個知識點，在不借助目錄的情況下，那我估計你可得找一會兒。同樣，對于數據庫的表而言，索引其實就是它的“目錄”。

索引的常見模型

索引的出現是為了提高查詢效率，但是實現索引的方式卻有很多種，所以這里也就引入了索引模型的概念。可以用于提高讀寫效率的數據結構很多，這里我先給你介紹三種常見、也比較簡單的數據結構：哈希表、有序數組和搜索樹。

哈希表是一種以鍵 - 值（key-value）存儲數據的結構，我們只要輸入待查找的鍵即 key，就可以找到其對應的值即 Value。哈希的思路很簡單，把值放在數組里，用一個哈希函數把 key 換算成一個確定的位置，然后把 value 放在數組的這個位置。

不可避免地，多個 key 值經過哈希函數的換算，會出現同一個值的情況。處理這種情況的一種方法是，拉出一個鏈表。

假設，你現在維護著一個身份證信息和姓名的表，需要根據身份證號查找對應的名字，這時對應的哈希索引的示意圖如下所示：

需要注意的是，圖中四個 ID_card_n 的值并不是遞增的，這樣做的好處是增加新的 User 時速度會很快，只需要往后追加。但缺點是，因為不是有序的，所以哈希索引做區間查詢的速度是很慢的。

所以，哈希表這種結構適用于只有等值查詢的場景，比如 Memcached 及其他一些 NoSQL 引擎。

而有序數組在等值查詢和范圍查詢場景中的性能就都非常優秀。還是上面這個根據身份證號查名字的例子，如果我們使用有序數組來實現的話，示意圖如下所示：

如果僅僅看查詢效率，有序數組就是最好的數據結構了。但是，在需要更新數據的時候就麻煩了，你往中間插入一個記錄就必須得挪動后面所有的記錄，成本太高。

所以，有序數組索引只適用于靜態存儲引擎，比如你要保存的是 2017 年某個城市的所有人口信息，這類不會再修改的數據。

二叉搜索樹也是課本里的經典數據結構了。還是上面根據身份證號查名字的例子，如果我們用二叉搜索樹來實現的話，示意圖如下所示：

二叉搜索樹的特點是：父節點左子樹所有結點的值小于父節點的值，右子樹所有結點的值大于父節點的值。

二叉樹是搜索效率最高的，但是實際上大多數的數據庫存儲卻并不使用二叉樹。其原因是，索引不止存在內存中，還要寫到磁盤上。

為了讓一個查詢盡量少地讀磁盤，就必須讓查詢過程訪問盡量少的數據塊。那么，我們就不應該使用二叉樹，而是要使用“N 叉”樹。這里，“N 叉”樹中的“N”取決于數據塊的大小。

N 叉樹由于在讀寫上的性能優點，以及適配磁盤的訪問模式，已經被廣泛應用在數據庫引擎中了。

在 MySQL 中，索引是在存儲引擎層實現的，所以并沒有統一的索引標準，即不同存儲引擎的索引的工作方式并不一樣。而即使多個存儲引擎支持同一種類型的索引，其底層的實現也可能不同。由于 InnoDB 存儲引擎在 MySQL 數據庫中使用最為廣泛，所以下面我就以 InnoDB 為例，和你分析一下其中的索引模型。

InnoDB 的索引模型

在 InnoDB 中，表都是根據主鍵順序以索引的形式存放的，這種存儲方式的表稱為索引組織表。又因為前面我們提到的，InnoDB 使用了 B+ 樹索引模型，所以數據都是存儲在 B+ 樹中的。

B+ 樹能夠很好地配合磁盤的讀寫特性，減少單次查詢的磁盤訪問次數。

每一個索引在 InnoDB 里面對應一棵 B+ 樹。

假設，我們有一個主鍵列為 ID 的表，表中有字段 k，并且在 k 上有索引。這個表的建表語句是：

mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分別為 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，兩棵樹的示例示意圖如下。

從圖中不難看出，根據葉子節點的內容，索引類型分為主鍵索引和非主鍵索引。

主鍵索引的葉子節點存的是整行數據。在 InnoDB 里，主鍵索引也被稱為聚簇索引（clustered index）。
非主鍵索引的葉子節點內容是主鍵的值。在 InnoDB 里，非主鍵索引也被稱為二級索引（secondary index）。

根據上面的索引結構說明，我們來討論一個問題：基于主鍵索引和普通索引的查詢有什么區別？

如果語句是 select * from T where ID=500，即主鍵查詢方式，則只需要搜索 ID 這棵 B+ 樹；
如果語句是 select * from T where k=5，即普通索引查詢方式，則需要先搜索 k 索引樹，得到 ID 的值為 500，再到 ID 索引樹搜索一次。這個過程稱為回表。

也就是說，基于非主鍵索引的查詢需要多掃描一棵索引樹。因此，我們在應用中應該盡量使用主鍵查詢。

索引維護

B+ 樹為了維護索引有序性，在插入新值的時候需要做必要的維護。

以上面這個圖為例，如果插入新的行 ID 值為 700，則只需要在 R5 的記錄后面插入一個新記錄。如果新插入的 ID 值為 400，就相對麻煩了，需要邏輯上挪動后面的數據，空出位置。

而更糟的情況是，如果 R5 所在的數據頁已經滿了，根據 B+ 樹的算法，這時候需要申請一個新的數據頁，然后挪動部分數據過去。這個過程稱為頁分裂。在這種情況下，性能自然會受影響。

除了性能外，頁分裂操作還影響數據頁的利用率。原本放在一個頁的數據，現在分到兩個頁中，整體空間利用率降低大約 50%。

當然有分裂就有合并。當相鄰兩個頁由于刪除了數據，利用率很低之后，會將數據頁做合并。合并的過程，可以認為是分裂過程的逆過程。

基于上面的索引維護過程說明，進行一個案例討論：

你可能在一些建表規范里面見到過類似的描述，要求建表語句里一定要有自增主鍵。哪些場景下應該使用自增主鍵，而哪些場景下不應該？

自增主鍵是指自增列上定義的主鍵，在建表語句中一般是這么定義的： NOT NULL PRIMARY KEY AUTO_INCREMENT。

插入新記錄的時候可以不指定 ID 的值，系統會獲取當前 ID 最大值加 1 作為下一條記錄的 ID 值。

也就是說，自增主鍵的插入數據模式，正符合了我們前面提到的遞增插入的場景。每次插入一條新記錄，都是追加操作，都不涉及到挪動其他記錄，也不會觸發葉子節點的分裂。

而有業務邏輯的字段做主鍵，則往往不容易保證有序插入，這樣寫數據成本相對較高。

除了考慮性能外，我們還可以從存儲空間的角度來看。假設你的表中確實有一個唯一字段，比如字符串類型的身份證號，那應該用身份證號做主鍵，還是用自增字段做主鍵呢？

由于每個非主鍵索引的葉子節點上都是主鍵的值。如果用身份證號做主鍵，那么每個二級索引的葉子節點占用約 20 個字節，而如果用整型做主鍵，則只要 4 個字節，如果是長整型（bigint）則是 8 個字節。

顯然，主鍵長度越小，普通索引的葉子節點就越小，普通索引占用的空間也就越小。

所以，從性能和存儲空間方面考量，自增主鍵往往是更合理的選擇。

有沒有什么場景適合用業務字段直接做主鍵的呢？還是有的。比如，有些業務的場景需求是這樣的：

只有一個索引；
該索引必須是唯一索引。

你一定看出來了，這就是典型的 KV 場景。由于沒有其他索引，所以也就不用考慮其他索引的葉子節點大小的問題。這時候我們就要優先考慮上一段提到的“盡量使用主鍵查詢”原則，直接將這個索引設置為主鍵，可以避免每次查詢需要搜索兩棵樹。

在下面這個表 T 中，如果我執行 select * from T where k between 3 and 5，需要執行幾次樹的搜索操作，會掃描多少行？

下面是這個表的初始化語句。

mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0, 
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

現在，我們一起來看看這條 SQL 查詢語句的執行流程：

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

在這個過程中，回到主鍵索引樹搜索的過程，我們稱為回表。可以看到，這個查詢過程讀了 k 索引樹的 3 條記錄（步驟 1、3 和 5），回表了兩次（步驟 2 和 4）。

在這個例子中，由于查詢結果所需要的數據只在主鍵索引上有，所以不得不回表。那么，有沒有可能經過索引優化，避免回表過程呢？

覆蓋索引

如果執行的語句是 select ID from T where k between 3 and 5，這時只需要查 ID 的值，而 ID 的值已經在 k 索引樹上了，因此可以直接提供查詢結果，不需要回表。也就是說，在這個查詢里面，索引 k 已經“覆蓋了”我們的查詢需求，我們稱為覆蓋索引。

由于覆蓋索引可以減少樹的搜索次數，顯著提升查詢性能，所以使用覆蓋索引是一個常用的性能優化手段。

基于上面覆蓋索引的說明，我們來討論一個問題：在一個市民信息表上，是否有必要將身份證號和名字建立聯合索引？

假設這個市民表的定義是這樣的：

CREATE TABLE `tuser` (`id` int(11) NOT NULL,`id_card` varchar(32) DEFAULT NULL,`name` varchar(32) DEFAULT NULL,`age` int(11) DEFAULT NULL,`ismale` tinyint(1) DEFAULT NULL,PRIMARY KEY (`id`),KEY `id_card` (`id_card`),KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB

我們知道，身份證號是市民的唯一標識。也就是說，如果有根據身份證號查詢市民信息的需求，我們只要在身份證號字段上建立索引就夠了。而再建立一個（身份證號、姓名）的聯合索引，是不是浪費空間？

如果現在有一個高頻請求，要根據市民的身份證號查詢他的姓名，這個聯合索引就有意義了。它可以在這個高頻請求上用到覆蓋索引，不再需要回表查整行記錄，減少語句的執行時間。

當然，索引字段的維護總是有代價的。因此，在建立冗余索引來支持覆蓋索引時就需要權衡考慮了。

最左前綴原則

單獨為一個不頻繁的請求創建一個（身份證號，地址）的索引又感覺有點浪費。應該怎么做呢？

B+ 樹這種索引結構，可以利用索引的“最左前綴”，來定位記錄。

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

在建立聯合索引的時候，如何安排索引內的字段順序？

評估標準是，索引的復用能力。因為可以支持最左前綴，所以當已經有了 (a,b) 這個聯合索引后，一般就不需要單獨在 a 上建立索引了。因此，第一原則是，如果通過調整順序，可以少維護一個索引，那么這個順序往往就是需要優先考慮采用的。

所以現在你知道了，這段開頭的問題里，我們要為高頻請求創建 (身份證號，姓名）這個聯合索引，并用這個索引支持“根據身份證號查詢地址”的需求。

那么，如果既有聯合查詢，又有基于 a、b 各自的查詢呢？查詢條件里面只有 b 的語句，是無法使用 (a,b) 這個聯合索引的，這時候你不得不維護另外一個索引，也就是說你需要同時維護 (a,b)、(b) 這兩個索引。

這時候，我們要考慮的原則就是空間了。比如上面這個市民表的情況，name 字段是比 age 字段大的，那我就建議你創建一個（name,age) 的聯合索引和一個 (age) 的單字段索引。

索引下推

上一段我們說到滿足最左前綴原則的時候，最左前綴可以用于在索引中定位記錄。那些不符合最左前綴的部分，會怎么樣呢？

mysql> select * from tuser where name like '張%' and age=10 and ismale=1;

你已經知道了前綴索引規則，所以這個語句在搜索索引樹的時候，只能用 “張”，找到第一個滿足條件的記錄 ID3。當然，這還不錯，總比全表掃描要好。

在 MySQL 5.6 之前，只能從 ID3 開始一個個回表。到主鍵索引上找出數據行，再對比字段值。

MySQL 5.6 引入的索引下推優化（index condition pushdown)，可以在索引遍歷過程中，對索引中包含的字段先做判斷，直接過濾掉不滿足條件的記錄，減少回表次數。

總結：

在滿足語句需求的情況下，盡量少地訪問資源是數據庫設計的重要原則之一。我們在使用數據庫的時候，尤其是在設計表結構時，也要以減少資源消耗作為目標。