一、索引的常見模型
1. 哈希表
是鍵值對（key-value）存儲結構，隻要根據 key 就可以找到 value。
可以了解為一個數組，對 key 進行哈希計算，換算成一個确定的位置，把 value 放入此位置。
因為存儲hash沖突的情況，多個value可能在同一個位置上，使用連結清單，後來的就追加到連結清單中。
例如存儲身份證号和名字的資訊：
這種結構隻适用于等值查詢場景，如果要找某個區間的使用者就需要全部掃描一遍了。
2. 有序數組
按照身份證号遞增的順序儲存。
有序數組非常适合等值查詢和範圍查詢。
例如查找 [ID_X, ID_Y] 内的，先用二分法找到 ID_X，然後向右周遊，直到找到大于 ID_Y 的就結束了。
有序數組的優勢是查詢效率高，缺點是更新麻煩，插入一個記錄就需要挪動後面所有的記錄，效率低。
有序數組索引隻适用于靜态存儲引擎，不會修改的資料情況。
3. 搜尋樹
先看最經典的二叉樹：
二叉樹中，左兒子 < 父節點，父節點 < 右兒子。
例如查找 ID_2，路徑就是：
UserA -> UserC -> UserF -> User2
二叉樹搜尋效率最高，但實際資料庫卻不适用二叉樹，因為索引是需要寫到磁盤上的，例如一棵100萬節點的二叉樹，高度是20，一次查詢需要通路20個資料塊，從磁盤随機讀一個資料塊需要10ms左右的尋址時間，那麼這個查詢就需要200ms，很慢了。
是以需要使用N叉樹，每個節點可以有多個兒子，兒子間從左到右遞增，這樣可以讓查詢過程通路盡量少的資料塊兒。
二、InnoDB 索引
1. 為什麼使用 B+ tree 索引模型？
例如插入資料：1,a,b,c,d,e。
二叉樹的結構：
紅黑樹的結構：
B+ tree 的結構：
二叉樹上面說過，效率太低，高度完全不可控，紅黑樹優化了不少，但高度仍然不可控，B+ tree 的高度恒定，而且隻在葉子節點中存儲資料，葉子節點間也是順序連結的，做範圍查找時非常高效。
2. 為什麼建議使用自增主鍵？
涉及到1個概念：頁分裂。
插入時，如果新值比現有值都大，那麼隻需要在後面插入即可，否則需要挪動現有資料。
如果插入目标位置的資料頁滿了，就要申請新的資料頁，并挪動資料。
是以自增ID能夠連續申請頁空間，提升空間的操作效率和使用率。
三、MySQL 索引的3個重要概念
例如有一個表：
有2個索引，ID 和 k。
InnoDB 主鍵索引的葉子節點存儲的是行資料，非主鍵索引的葉子節點存儲的是主鍵。
查詢 k 在 [3,5] 區間内的所有行資料：
select * from T where k betweet 3 and 5 在 k 索引樹上找到符合條件的，得到 ID 值，回到 ID 索引樹取得行資料。
回到主鍵索引搜尋的過程稱為回表。
1. 覆寫索引
上面的查詢如果改為：
select ID from T where k betweet 3 and 5 隻查詢ID這個字段，那麼隻搜尋 k 樹索引即可，不需要回表了。
索引 k 已經覆寫了我們的查詢需求，這種情況稱為覆寫索引。
覆寫索引可以顯著提升查詢性能，是以做優化時可以考慮是否适合使用此方式。
例如使用者表，有身份證号、姓名字段，身份證号是唯一的，建了一個索引。
如果業務中有根據身份證号搜尋姓名的高頻需求，就可以建立一個（身份證号+姓名）的聯合索引，實作覆寫索引，即使增加了索引的維護成本也是值得的。
2. 最左字首原則
索引項是按照字段順序排序的。
查詢“張三”時，會快速定位到 ID_4，然後向後周遊需要的結果。
查詢“張%”也可以用這個索引，定位到 ID_3，向後找，直到不滿足條件為止。
是以，隻要滿足最左字首就可以用到索引。
涉及到一個問題：如何安排索引内的字段順序？
需要考慮索引的複用能力，如果通過調整順序，可以少維護一個索引，那麼這個順序就是優先考慮的。
3. 索引下推
例如使用者表有字段：ID,name,age,ismale …，建有一個索引（name,age）。
現在查詢：
select * from tuser where name like '張 %' and age=10 and ismale=1; MySQL5.6 之前，查詢過程是：
根據索引找到以“張”開頭的名字的ID，然後回表，進一步判斷 age 和 ismale。
在 5.6 引入了索引下推，在索引中找到“張”開頭的以後，先在索引中判斷其 age 是否符合條件，因為 age 已經在索引中，不需要回表判斷了，把 age 不符合要求的先過濾掉，然後再回表判斷 ismale，這就減少了回表次數，提升了查詢效率。