針對不同的應用場景創建合適的索引對於優化mysql查詢速度非常關鍵，今天一起來學習一下mysql索引相關的原理性內容。
mysql索引的數據結構
如圖是以二叉搜索樹為數據結構建立起的索引，這樣的索引數據結構樹高是O(log2n), 我們知道mysql數據記錄和索引樹節點都是存在磁盤上的，mysql磁盤IO的次數是和索引樹高成正比的。一張有1千萬條記錄的表索引樹的樹高大約是23，也就是近乎23次磁盤IO，以二叉搜索樹為數據結構的索引樹顯然是不合適的。
- B樹
mysql並沒有使用二叉搜索樹組織索引，而是基於B樹，B樹是由二叉搜索樹演變的，有以下幾個特點：
- m叉搜索樹
- 每個節點的key左側分支都不大於key，右側分支不小於key
- 每個節點n-1個key和n個指針（「m/2<=n<=m）
- 一個節點中key非遞減排列
- 指針或指向另一個節點，或為null
- 葉子節點、非葉子節點都存儲數據
由於B樹在一個節點可以存儲更多的key，因此B樹索引樹樹高比二叉搜索樹要低很多。但直接拿B樹做索引還存在一些問題，比如SQL中的範圍查詢，直接用B樹索引就無法很好的支持。
2. B+樹
B+樹滿足以下性質：
- m叉搜索樹
- 每個節點的key左側分支都不大於key，右側分支不小於key
- 每個節點n-1個key和n個指針（「m/2<=n<=m）
- 一個節點中key非遞減排列
- 指針或指向另一個節點，或為null
- 葉子節點，非葉子節點都存儲數據
- 非頁節點不再存儲數據，數據統一存儲在葉子節點
- 葉節點之間增加了鏈表
相比於B樹B+增加了兩個比較重要關鍵的性質（加黑的兩條）
“非葉子節點不再存儲數據，數據統一存儲在葉子節點”可以減小非葉子索引節點的大小，讓一個磁盤頁存儲儘可能多的索引key，降低樹高。
“葉子節點之間增加鏈表”可以使索引很好的支持SQL中的範圍查詢。
在總結為什麼B+樹索引效率高的之前回顧一下我們學操作系統時所學過的兩個小知識：程序訪問局部性原理和磁盤預讀。
- 程序訪問局部性原理：程序訪問某個數據時，其下個指令大概率會訪問其附近數據(局部性原理)
- 磁盤預讀：磁盤數據按頁組織，一頁大小一般是4KB，操作系統一次加載磁盤中的一頁或幾頁數據到內存，減少磁盤IO
3. 為什麼B+樹索引效率高
- 充分利用局部性原理和磁盤預讀，將索引節點的大小設置為磁盤頁（4K）的大小
- 樹的出度通常很大，可達幾百，因此索引樹的高度很低，一般不超過3
- 能夠很好的支持單點查詢和範圍查詢
InnoDB和MyISAM存儲引擎索引實現的差異
mysql常用的存儲引擎主要是InnoDB和MyISAM，兩種引擎分別有不同的特點。比如InnoDB支持事務，行鎖，而MyISAM不支持事務，支持表級別鎖等等。在兩種存儲引擎在索引實現上也存在一定的差異，下面我們一起來看下兩種存儲引擎在索引實現上差別在哪兒。
存儲引擎對於主鍵字段和非主鍵字段在建立索引時會有不同，在分析存儲引擎索引實現時需要分別看看它們的主鍵索引和普通索引(非主鍵索引)的差異。
1.MyISAM索引實現
- 主鍵索引（Primary index）
主鍵索引是在數據表主鍵上建立的索引，MyISAM主鍵索引有以下幾個特點：
(1). 基於B+樹實現
(2). 葉節點存儲的是數據的地址
(3). 獨立連續的區域存儲數據行
- 輔助索引（Secondary index）
輔助索引是在非主鍵字段上建立的索引：
(1). 基於B+樹實現
(2). 葉節點存儲的是數據的地址
(3). 獨立連續的區域存儲數據行
可以看到MyISAM的主鍵索引和輔助索引在實現上是沒有差別的，僅僅把索引的列改成對應的索引字段。
2.InnoDB索引實現
- 主鍵索引（Primary index）
(1) 基於B+樹實現
(2) 葉節點存儲的是數據行
- 輔助索引（Secondary index）
(1)基於B+樹實現
(2)葉節點存儲的是對應的主鍵
InnoDB輔助索引葉子節點存儲的是記錄對應的主鍵，然後利用主鍵去索引對應的記錄。也就是說利用輔助去索引記錄一定會用到InnoDB的主鍵索引，InnoDB一定會建立一個主鍵索引，不論表中是否指定了主鍵。
3.MyISAM和InnoDB索引差異總結
- MyISAM索引和數據分開存儲(非聚簇索引)
- MyISAM索引的葉子存儲指針，主鍵索引和輔助索引無太大差異
- InnoDB的主鍵索引存儲的是數據內容，索引和數據存在一起 (聚簇索引)
- InnoDB輔助索引葉子節點存儲記錄的主鍵，再利用主鍵索引查詢記錄
- InnoDB有且只有一個聚簇索引
聯合索引和最左前綴匹配
- 聯合索引
前面兩部分介紹的內容都是基於一個字段上的索引，mysql還支持建立聯合索引，聯合索引是在多個字段上建立起一個索引。例如在下面這個表上建一個的聯合索引：
聯合索引索引樹的構建與索引字段的順序有關。聯合索引雖然是多個字段共同構成索引，但索引樹和單列索引一樣，仍然是一個，其實單列索引也是一種特殊的聯合索引。例子中，聯合索引最左索引字段是col3，因此索引樹以col3字段構建，對於col3相同的字段再以col2字段做索引。邏輯類似於：group by col3 , clo2。
- 最左前綴匹配原則
最左前綴匹配原則：在mysql上建立聯合索引會遵循最左匹配原則，即在建立索引時會以最左字段作為主索引，同時where查詢條件中也須包含索引最左字段才能利用到聯合索引。
我們通過一個例子對where查詢條件中必須包含索引最左字段進行說明。
在tb_user表上建立了三列聯合索引，最左字段為name。
查詢條件中不包含name字段
查詢條件中包含name字段
可以看到當我們在查詢條件中不包含name(建立聯合索引的最左字段)字段時，查詢語句是沒有用到聯合索引的，包含name字段時查詢語句就能夠用到聯合索引"ids_name_addr_pwd"。
建立一個聯合索引，實際上相當於建立了（col1）、（col1,col2）,(col1,col2,col3)三個索引，相比於建立多個單個索引而言使用聯合索引可以大大減小維護索引的開銷
索引使用建議
- 不是索引越多，性能就好（考慮索引對更新的影響）
- 強烈建議使用自增主鍵（主鍵不隨機、性能保第一）
- 儘量不要在選擇性不多的列上添加索引
- 索引列字段值不宜過長
- 避免在索引上使用like（like性能本身就很低，且like ‘%...’會導致全表掃描）
- 儘量使用聯合（多列）索引、少創建多個單列索引
