知識星球作者：iCell
連結：https://icell.io/how-mysql-index-works/
索引一直是資料庫中非常重要的概念，所以瞭解索引相關的知識是轉入後端開發中必不可少的一環。這篇文章是我從開始做後端開發之後至今學習關於索引知識的一個總結，從原先很多概念的模糊和不理解到現在大致有一個比較清楚的認知，儘量會把關於索引的一些點以及為什麼需要這麼做給解釋明白，包括使用 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 的關鍵優勢是中間節點不包含資料，因此 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 表，表結構如下：
| Column | Type | Usage | Index |
|---|---|---|---|
| id | bigint | Primary Key | primary_index |
| employee_id | varchar(10) | 員工編號 | employee_id_index |
| name | varchar(20) | 姓名 | name_age_gender_index |
| age | int | 年齡 | name_age_gender_index |
| gender | int | 性別 | 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，所以會使用一次訪問排序，流程如下：
-
初始化 buffer
-
根據最左匹配原則命中 name 為 ‘iCell’ 的值，根據輔助索引找出主鍵 id；
-
根據主鍵 id 取出整行的值，然後將 name, age 和 employee_id 這三個傳回列的的值存入到 buffer 中；
-
重覆以上 2 和 3 的步驟，直到不再滿足查詢條件為止；
-
對 buffer 中的資料根據 employee_id 進行排序；
-
將排序結果傳回；
那麼假設我現在的 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 主鍵的插入資料樣式，正符合了遞增插入的場景。每次插入一條新記錄，都是追加操作，都不涉及到挪動其他記錄，也不會觸發葉子節點的分裂。
結束
以上便是我對所學索引相關知識的一些總結，可能有些疏漏或者錯誤的地方。但是索引一直學過來感覺是一個涉及面非常廣的知識點，這篇文章也只能算是一個學習筆記，在之後的實踐過程中遇到什麼值得記錄的還會繼續進行補充。
