MySQL 索引原理及設計

作者：About iCell 
原文：https://icell.io/how-mysql-index-works/?utm_source=tuicool&utm_medium=referral

索引一直是數據庫中非常重要的概念，所以瞭解索引相關的知識是轉入後端開發中必不可少的一環。這篇文章是我從開始做後端開發之後至今學習關於索引知識的一個總結，從原先很多概念的模糊和不理解到現在大致有一個比較清楚的認知，儘量會把關於索引的一些點以及為什麼需要這麼做給解釋明白，包括使用 InnoDB 引擎的 MySQL 索引的相關概念，以及如何針對 InnoDB 進行索引的設計和使用，以及三星索引的概念，會從我所瞭解到的知識去解釋為什麼需要這樣，如果有錯誤的地方還請指出。

B+ Tree

在 InnoDB 中，索引使用的數據結構是 B+ Tree，這裡的 B 是 Balance 的意思。B 類樹的一個很鮮明的特點就是樹的層數比較少，而每層的節點都非常多，樹的每個葉子節點到根節點的距離都是相同的（這也是為什麼叫 Balance Tree 的原因）。

另外，樹的每一個節點都是一個數據頁，這樣每個節點只需要一次 IO 就可以全部讀取。這樣的結構保證了查詢數據時能儘量少地進行磁盤 IO，同時保證 IO 的穩定性。

B+ Tree 和 B Tree 不同，B+ Tree 中，只能將數據存儲在葉子結點中，內部節點將只包含指針，而 B Tree 可以將數據存儲在內部的葉節點中。

因此 B+ Tree 的關鍵優勢是中間節點不包含數據，因此

主索引和輔助索引

在 InnoDB 存儲引擎中，每一個索引都對應一棵 B+ Tree，InnoDB 的索引主要分為主索引和輔助索引：

1. 主索引：包含記錄的文件按照某個 key 制定的順序排序，這個 key 就是主索引，也就是主鍵，也被稱為聚簇索引。因為無法同時把數據行存放在兩個不同的地方，所以一個表只能有一個聚集索引。在 InnoDB 中，主索引的葉子節點存的是整行數據，這也意味著 InnoDB 中的表一定要有一個主索引；
2. 輔助索引：某個 key 指定的順序與文件記錄的物理順序不同，這個
   key 就是輔助索引。InnoDB 中的輔助索引在葉子節點中並不存儲實際的數據，只會包含主索引的值 。這就意味著如果使用輔助索引進行數據的查找，只能查到主索引，然後根據這個主索引再次掃描以下主索引的樹，進行一次回表操作；

上面講到，InnoDB 的表中要求必須有一個主鍵，那麼可能有人會將身份證號這種唯一性的標識作為主索引，這樣就大錯特錯了。剛剛說到主鍵也被稱為聚簇索引，它是要按照順序進行排序的，要求有聚簇性。如果將身份證號作為主鍵，不能保證每次插入的數據都是按照身份證號的順序進行排列的，這就使得每次主鍵的插入都變得完全隨機，可能導致每次插入一條數據都會引起頁分裂的問題（這個話題在後面會講到）。

所以在表結構定義的時候，應該使用一個具有聚集性的 key 作為主鍵，如果真的沒有的話，可以使用一個 AUTO INCREMENT 代理鍵作為主索引，這樣可以保證數據行是順序寫入的。如果你真的完全沒有定義主鍵，InnoDB 會選擇一個唯一的非空索引代替，但是如果沒有這樣的索引，InnoDB 會隱式定義一個主鍵來作為聚集索引。

正因為 InnoDB 索引的這種結構，產生了一些限制：

1. 如果不是按照索引的最左列開始查找，則無法使用索引；
2. 不能跳過聯合索引中的某些列；
3. 如果查詢中有某個列的範圍查詢，則其右邊所有列都無法使用索引優化查找；

以上幾點也基本上代表常聽到的“最左前綴”，我們通過幾個例子來解釋一下這個問題，可能有的情況舉的例子不太恰當，但希望能說明白想說出的問題。假設我們有一個 employees 表，表結構如下：

ColumnTypeUsageIndexidbigintPrimary Keyprimary_indexemployee_idvarchar(10)員工編號employee_id_indexnamevarchar(20)姓名name_age_gender_indexageint年齡name_age_gender_indexgenderint性別name_age_gender_index

這個表中我們有 (name, age, gender) 這個聯合索引，這個索引的結構大概如下圖所示：

在上面的葉子節點下，假設有多個名為 BX 和 iCell 的員工，他們的年齡都不太一樣，是先按照 name 排序，再按照 age 進行排序。

查詢 1:

SELECT * FROM employees 
WHERE name='BX' AND age=19 AND gender=0;

上述這種查詢，根據 (name, age, gender) 這個索引樹來查找，找到 id 為 2 的索引數據符合條件，然後通過相鄰的節點鏈接繼續查找，發現下一個數據不符合條件，最終命中索引的就是 id 為 2 的這一條數據，因為是要查找行的所有數據，所以再根據 id 為 2 去主鍵索引樹中繼續回表查找，得到結果數據。

查詢 2:

SELECT * FROM employees WHERE name='iCell';

根據 (name, age, gender) 這個索引樹來查找，找到 id 為 3 的索引數據符合條件，然後通過相鄰的節點鏈接繼續查找，發現下一個數據也符合條件，繼續根據節點鏈接查找，直到發現數據已經不符合條件了，於是命中索引的就是 id 為 3，4，5 的幾條數據，然後繼續根據這幾個 id 值進行回表操作，得到結果數據。

查詢 3:

SELECT * FROM employees WHERE age=17;

根據“最左前綴”原則，並不存在 age 為前綴的索引，所以這個查詢無法使用 (name, age, gender) 這個索引樹進行數據查找，得去主索引中進行全表掃描，這無非是非常慢的。所以如果想讓這個查詢命中索引，得單獨為 age 添加索引或者添加 age 為前綴的聯合索引。或者，這類情況還有一種方法，就是給跳過的索引列使用 IN 的查詢方式讓其發生“最左前綴”匹配，但是在這裡 name 這個字段不適合用 IN 這種查詢方法。

查詢 4:

SELECT * FROM employees 
WHERE name like 'B%' AND age=17;
SELECT * FROM employees 
WHERE name='iCell' AND age > 18 AND gender=1;

由於 B+ Tree 的限制，當查詢中出現有某個列的範圍查詢，則這個範圍查詢後面的列都無法使用索引。上面的查詢中，like B%和 age > 18都是範圍查詢，所以後面的查詢不能通過索引樹來直接查找。

對於此種情況，MySQL 5.6 版本增加了 Index Condition Pushdown 技術，如果查詢中 where 語句可以使用索引中已有的字段（比如這裡就是 name，age， gender），在遍歷索引時對這些字段先做判斷直接過濾掉不滿足條件的值，減少引擎層訪問表的次數和 MySQL Server 層訪問存儲引擎的次數。但是這種技術跟“最左前綴”並無衝突，只是做了數據過濾的優化。

查詢 5:

SELECT * FROM employees WHERE employee_id=11;

注意看之前的數據表定義，employee_id 是 varchar 類型，但這個查詢語句中將其與數字類型做比較，這時候會觸發 MySQL 的隱式類型轉換，將字符串轉換成數字進行比較，也就是說上述的語句相當於：

SELECT * FROM employees 
WHERE CAST(employee_id AS int)=11;

也就是說，在這個查詢中對索引字段做了函數操作，而這樣的話會破壞索引值的有序性，於是不會命中索引，轉而進行全表掃描。

查詢 6:

SELECT age, gender FROM employees WHERE name='iCell';

這種情況類似於查詢 2 中所舉的例子，但是這個查詢的結果要求只返回 age 和 gender，而 age 和 gender 的值是包含在索引中的，這樣就可以直接返回而不用再進行回表查詢了。如果一個索引包含所有需要查詢的字段的值，則為覆蓋索引，使用覆蓋索引不需要進行回表操作，能增加數據查詢效率

ORDER BY 如何使用索引

要說 ORDER BY 如何利用索引進行排序，得先弄清楚 ORDER BY 本身是如何進行排序的。在 MySQL 中，會給每個線程分配一塊內存空間 buffer 用於排序，還有一個參數叫做 max_length_for_sort_data，這個參數作用是用來規定排序返回行的字段長度，默認值是 1024，最小值為 4，如果排序返回行的字段長度沒有超過這個參數的值，就會使用一次訪問排序，否則使用二次訪問排序。

現在我們還是通過上面這張 employees 表來說明問題，有以下語句：

SELECT name, age, employee_id FROM employees 
WHERE name='iCell' ORDER BY employee_id;

現在我要查的排序的返回字段只包括 name, age 和 employee_id，在默認情況下肯定不會超過 1024，所以會使用一次訪問排序，流程如下：

1. 初始化 buffer
2. 根據最左匹配原則命中 name 為 'iCell' 的值，根據輔助索引找出主鍵 id；
3. 根據主鍵 id 取出整行的值，然後將 name, age 和 employee_id 這三個返回列的的值存入到
   buffer 中；
4. 重複以上 2 和 3 的步驟，直到不再滿足查詢條件為止；
5. 對 buffer 中的數據根據 employee_id 進行排序；
6. 將排序結果返回；

那麼假設我現在的 max_length_for_sort_data 的值很小，要查詢的返回子段長度超過了這個值，那就會使用二次訪問排序，流程如下：

• 初始化 buffer
• 根據最左匹配原則命中 name 為 'iCell' 的值，根據輔助索引找出主鍵 id；
• 根據主鍵 id 取出整行的值，然後將排序行 employee_id 以及 primary key 的值存入到 buffer 中；
• 重複以上 2 和 3 的步驟，直到不再滿足查詢條件為止；
• 對 buffer 中的數據根據 employee_id 進行排序；
• 根據排序結果中的 primary key，就會回表操作，並將最終結果返回；

以上兩種排序，無非是 MySQL 認為內存夠不夠用，夠用的話就多利用內存而避免過多的回表操作從而增加磁盤訪問。那如果排序申請的內存空間不過用了怎麼辦？參數 sort_buffer_size 就是控制排序內存空間大小的，如果內存不夠用，就會使用磁盤臨時文件做外部歸併排序。

知道了以上排序操作，再結合之前覆蓋索引以及 B+ Tree 索引的邏輯，是不能就有辦法去優化 ORDER BY 的流程了。首先，不管是一次訪問排序還是二次訪問排序，都要在 buffer 對數據做排序操作，而 B+ Tree 本身的葉子結點就是有序排列的，所以只要能做到排序行也能按照最左匹配原則匹配到索引，就可以避免內存排序的步驟了。另外，上述的排序步驟中還需要進行回表操作，那麼只要查詢的語句能命中覆蓋索引，是不是就能夠避免回表操作了。進一步，如何可以使用同一個索引既滿足排序又用於查找行那就相當不錯了。

三星索引

在《高性能 MySQL》書中提到了一本書叫《Relational Database index design and the optimizers》，書中有一個概念是“三星索引”，它是這樣定義的：

1. 滿足第一顆星：取出 WHERE 語句後的相關的列，將這些列作為索引最開始的列，這樣可以利用索引來儘可能的過濾不必要的數據，減少數據處理的規模；
2. 滿足第二顆星：將 ORDER BY 列加入到索引中，不改變這些列的順序，不考慮第一顆星已經出現的列，利用索引進行排序；
3. 滿足第三顆星：將查詢語句中剩餘的列加到索引中去，達到覆蓋索引的效果。

但是三星索引往往是理想中的情況，現實狀況下往往會同時有範圍查詢和排序的需求出現，這樣就很難同時滿足第一顆星和第二顆星，比如下列語句：

SELECT name, age FROM employees 
WHERE age BETWEEN 15 AND 30 
AND gender=1 ORDER BY name;

根據以上 SQL 建立索引，會出現兩種情況：

第一種情況的索引為 (age, gender, name)：

1. 滿足第一顆星：將 age 和 gender 放入索引中，這樣滿足 WHERE 後有一個索引列和一個過濾列；
2. 無法滿足第二顆星：age 是範圍查詢，此時的 gender 並不是有序的；
3. 滿足第三顆星：將查詢列 name 放入索引中；

第二種情況的索引為 (gender, name, age):

1. 不滿足第一顆星：只能匹配到 gender 索引列；
2. 滿足第二顆星：gender 相等的前提下，name 是有序排列的；
3. 滿足第三顆星：將查詢列 age 放入索引中；

關於三星索引的概念這裡只是簡單地舉例子說明，之後會對 “Relational Database index design and the optimizers

頁分裂

前面說到，InnoDB 中數據是存儲在數據頁中的，而數據是按照索引的順序插入到數據頁中的，所以數據是緊湊排序的，但如果隨機對數據進行插入，就有可能導致數據頁分裂的問題。

假設一個數據頁只能存儲 3 條數據，且已經有 3 條數據（100， 200， 300）了，這時候想插入一條 150 的數據，就會再申請一個新的數據頁，100，150 兩條數據存放在原來的數據頁中，200 和 300 存放在新的數據頁中，這樣可能會存在數據頁利用率不高的問題。

不僅僅是插入數據會導致上述問題，刪除數據也會。這裡要注意，如果刪除掉了一個數據頁中的某條數據，這條數據所留下的位置並不會縮小而是等待複用，如果是一整個頁的數據被刪除了，那這個頁也是出於被複用狀態。如果相鄰的兩個數據頁的利用率很小，系統會把這兩個頁的數據合到其中一個頁上，另一個頁就處於可被複用的狀態。所以通過 delete 刪除數據並不會回收表空間。

為了解決頻繁刪除數據導致的沒有回收表空間的問題，可以通過重建表來解決，比如以下命令：

alter table table_name engin=InnoDB;

這個命令的流程基本上是：

1. 新建一個臨時表，結果同原表相同；
2. 按照主鍵 id 遞增的順序將數據從原表讀出插入到新表中；
3. 用新的表替換舊錶，刪除舊錶；

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

結束

以上便是我對所學索引相關知識的一些總結，可能有些疏漏或者錯誤的地方。但是索引一直學過來感覺是一個涉及面非常廣的知識點，這篇文章也只能算是一個學習筆記，在之後的實踐過程中遇到什麼值得記錄的還會繼續進行補充。

閱讀更多 電氣工控自動化 的文章

關鍵字: 數據結構 一環 數據庫