作者：PeTu
連結：https://www.jianshu.com/p/a935dd9edf04
Mysql的兩種主要的存儲引擎都依賴的數據結構為B+tree，一種從B-tree改進而來的樹狀數據結構
本節將從幾個方面來介紹：
1. 介紹B-tree和B+tree；
2. 介紹兩種主要的存儲引擎如何實現索引；
1.1 介紹B-tree和B+tree
1.1.1 B-tree
B-tree名為多路搜索平衡樹，在此先定義一組值[key,data]，key即為鍵，data即為key鍵所指向的值。
在大多數的文獻與書籍中，對於B-tree的定義有一些差別，本文中參考的是清華大學出版社的《數據結構（C語言版）》（2007年版）。
一棵m階的 B 樹，或為空樹，或為滿足下列特性的m叉樹:
樹中每一個結點至多有m棵子樹； 若根結點不是葉子結點，則至少有兩棵子樹； 除根結點之外的所有非終端結點至少有m/2棵子樹；
4.所有的非終端結點中包含下列信息數據(n,A{0} ,K{1},A{1},K{2} ,A{2},...,K{n},A{n})， 其中：K{i}（i=1,...,n）為關鍵字，且K{i}
B-tree示例圖：
B-tree
1.1.2 B+tree
B+tree是B-tree的變體，對於階數為m的樹其中改變的地方有：
B+tree中每個結點關鍵字個數範圍變為m/2≤n≤m，即結點的最左邊不是子樹指針而是關鍵字key； 內節點不存儲data，只存儲key；葉子節點不存儲指針，並且所有的關鍵字key都會在葉子結點再存儲一遍 一般B+tree都帶有每個葉子節點的指向相鄰葉子節點的順序指針
在做了以上改變後，B+tree的查找則都必須要查找到葉結點，而B-tree則可能在某個內結點即停止查找；還有B+tree的查找可以有根結點和起始葉結點兩個出發點。
B+tree示例圖：
B+tree
1.2 兩種存儲引擎如何實現索引
目前比較主流的存儲引擎貌似是MyISAM和InnoDB兩種，這裡先介紹這兩個
1.2.1 MyISAM實現索引
MyISAM是MySQL的默認數據表類型，基於了傳統的ISAM類型，ISAM是Indexed Sequential Access Method（有索引的順序訪問方法）的縮寫，MyISAM使用B+tree存儲引擎結構，葉節點的data域存放的是數據記錄的地址。
MyISAM採用的是索引文件和數據文件分離存儲，索引文件中存儲的是數據文件中相應數據的地址，只對索引採取B+tree數據結構。
`MyISAM`索引原理圖
這裡使用別人已有的教學例子
設表共有三列，假設我們以Col1為主鍵，則上圖是一個MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件僅僅保存數據記錄的地址。在MyISAM中，主索引和輔助索引（Secondary key）在結構上沒有任何區別，只是主索引要求key是唯一的，而輔助索引的key可以重複。如果我們在Col2上建立一個輔助索引，則此索引的結構如圖
輔助索引原理圖
這樣在利用索引查詢時，會按照B+tree的查詢算法進行查找，當查找到指定的key時，則會讀取到相應葉結點的data域，根據其中的地址信息取出相應的數據。
1.2.2 InnoDB實現索引
InnoDB使用的也是B+tree數據結構存儲器引擎，但是和MyISAM差別比較大。
首先InnoDB的數據文件本身就是索引文件。即數據文件就按照B+tree的結構存儲，這棵樹的key即是InnoDB中的主鍵，這棵樹的葉結點對應的data域存儲的是完整的數據記錄。
輔助索引原理圖
這種索引叫做聚集索引。因為InnoDB的數據文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵，對比MyISAM，MyISAM則不是非要主鍵，MyISAM的索引叫做非聚集索引，如果沒有顯式指定，則MySQL系統會自動選擇一個可以唯一標識數據記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隱含欄位作為主鍵，這個欄位長度為6個位元組，類型為長整形。
第二點不同，在InnoDB中的輔助索引和MyISAM中的輔助索引也不一樣，InnoDB的輔助索引也採用的B+tree結構存儲，但是輔助索引樹的葉結點的data域則存儲的是相應的主鍵值，而不是像MyISAM存儲地址。
例如用上述圖中的第三列做InnoDB的輔助索引，則得下圖：
輔助索引原理圖
聚集索引這種實現方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然後用主鍵到主索引中檢索獲得記錄。但這樣的好處是，如果輔助索引data存放的數據指針，當數據移動或者數據頁分裂時，需要更新data域行指針的值，這就增加維護成本。data存在主鍵的值，就沒有這個問題。數據移動和數據頁分裂，主鍵索引會自動更新。data關聯主鍵的值，不需要更新，相當於增加一個間接層。這個間接層對性能的影響也很小，因為通過主鍵定位記錄是非常快的。
由此我們清楚了InnoDB的主鍵最好使用單調有序的欄位，並且不適合太長的欄位，因為每個輔助索引都存儲主索引欄位，太長的主鍵會造成輔助索引空間太大，一般使用的是自增的整型欄位。
2.1 B-Tree索引及B+Tree索引
前面已經介紹了InnoDB及MyISAM兩種最常用的存儲引擎所基於的數據結構---B-Tree和B+Tree，以及是如何存儲索引和鍵值的，基於這兩種數據結構的索引就是B-Tree索引及B+Tree索引。
本文的示例數據表People，創建如下表：
建表語句
接著介紹下對於這種索引有效的查詢類型。
全值匹配
全值匹配指的是和索引中的所有列進行匹配，以上面的例子即為可查詢姓zhang,名san，出生於1960-01-01的人
匹配最左前綴
即只使用索引的第一列，上述例子中即可用索引查詢姓zhang的人
匹配列前綴
也可以只匹配某一列的值得開頭部分。上述例子中即可用索引查詢姓氏中以zh開頭的信息。也是只使用了索引的第一列。
匹配範圍值
前面提到的索引即可範圍查詢按字母順序姓氏在Li和zhang之間的人。同樣是只使用了第一列
精確匹配某一列並範圍匹配另外一列
上述例子中即可精確匹配所有姓氏為zhang，並且按字母順序名字在san到si之中的信息。
即第一列surname全匹配，第二列name範圍匹配。
只訪問索引的查詢
B-Tree通常可以支持「只訪問索引的查詢」，即查詢只需要訪問索引，而無需訪問數據行。
上述中創建的索引叫做多列索引，對應的另一類即為單列索引，在『高性能索引策略/多列索引』中會詳細介紹。
2.2 哈希索引 及 R-Tree索引
hash 哈希索引基於哈希表實現，只有精確匹配索引所有列的查詢才有效。對於每一行數據，存儲引擎都會對所有的索引列計算一個哈希嗎（hash code），哈希嗎是一個較小的值，並且不同鍵值的行計算出來的哈希碼也不一樣。哈希索引將所有的哈希碼存儲在索引中，同時在哈希表中保存指向每個數據行的指針。 在MySQL中，只有Memory引擎顯式支持哈希索引。 InnoDB引擎有一個特殊的功能叫做「自適應哈希」，當InnodeDB注意到某些索引值被使用的非常頻繁時，它會在內存中基於B-Tree索引之上在創建一個哈希索引，這樣就讓B-Tree索引也具有哈希索引的一些優點，比如快速的哈希查找。
空間數據索引（R-Tree） MyISAM表支持空間索引，可以用做地理數據存儲。和B-Tree索引不同，這類索引無須前綴查詢。空間索引會從所有維度來索引數據。查詢時，可以有效地使用任意維度來組合查詢。必須使用mysql的GIS相關函數如MBRCONTAINS()等來維護數據。mysql的GIS支持並不完善，所以大部分人都不會使用這個特性。開源資料庫中對GIS的解決方案做的比較好的是PostgreSQL的postGIS。
2.3 關於B-tree索引的限制
由此可以得出，類似的在where條件查詢中想進行模糊查詢時，aaa%則可以利用上索引，而%aaa%以及%aaa則無法利用上索引，以及範圍查詢條件最好放到後面，或者範圍查詢列值的數量有限時，可以通過使用多個等於條件來代替範圍查詢。
還有，儘可能將需要做範圍查詢的列放到索引的後面，這樣優化器能使用儘可能多的索引列。 索引的順序很重要。
3.1 獨立的列
『獨立的列』是指索引列不能是表達式的一部分，也不能是函數的參數。
例如：mysql> select x from table where x+1 = 5;
雖然可以很容易的分辯出x的值為4，但是Mysql則無法利用該索引（如果x是索引的話）。儘量養成簡化where的習慣，始終將索引單獨的的放在符號的一側，這樣Mysql才可以利用上索引。
3.2 索引選擇性 和 前綴索引
先介紹索引選擇性
索引的選擇性是指，不重複的索引值和數據表的記錄總數（T）的比值，範圍在 1/T 到 1 之間。不重複的索引值也稱為基數（cardinality）。因為選擇性高的索引可以讓Mysql在查找時過濾掉更多的行，所以索引的選擇性越高則查詢效率越高。唯一索引的基數即為數據的條數，其選擇性為1，所以唯一索引的性能最好。
對於TEXT或是VARCHAR類型的列，當這個列中的值長度很大又必須利用其進行查詢時，就必須使用這個列的前幾位值以作索引，即前綴索引，因為整個列的值當做索引時B+tree會占用非常大的空間，查找也不方便。
而制定前綴索引時要注意的一點就是這個前綴索引的選擇性需要和整個列的選擇性接近，這樣性能不會影響太多，同時還不能太長而占用太多空間。
這有一種尋找最佳前綴索引的方式，即根據選擇性的定義來進行計算其完整列的選擇性及其前綴的選擇性以便對比。
假設：有一個表中的某一列，名為session，其值為十六進位的ID
首先進行完整列的選擇性的計算
mysql> SELECT COUNT(DISTINCT session) / COUNT( * ) FROM table;
如果是唯一ID，則其值應為1，然後計算這個列的前綴長度為x的選擇性，
mysql> SELECT COUNT(DISTINCT LEFT( session , x )) / COUNT( * ) FROM table;
得到一個小數值，可以改變x的值來計算不同前綴的選擇性，最後在多個值中，綜合考慮選擇性接近性和前綴長度的兩個方面，可以選出一個較為合適的前綴索引。
創建一個前綴長度為x的索引：
mysql> ALTER TABLE table ADD KEY (session (x) );
小貼士：例如某個列的值存的是郵箱時，可以先字符串反轉，或者根據@標識符前後顛倒，再存入資料庫，再建立前綴索引，這樣就可以根據前綴索引快速查出特定郵箱域名的所有信息了。
3.3 多列索引
在Mysql執行查詢時，如果是使用多列索引，則會先查詢符合第一列索引的數據集，然後再在這一部分數據集中查詢出符合第二列的數據，以此類推，這樣在不用掃描數據的情況下就能選出數據；
而如果一個多列索引拆分成多個單列索引的話，Mysql在執行查詢時，只會從中選出一個限制最嚴格的索引以供使用，其他的索引就浪費了，所以在上述情況中多列索引性能要好
注：在Mysql 5.0之後，Mysql添加了『索引合併』策略，一定程度上可以使用表上的多個單列索引來定位數據。
實際上，Mysql 5.0之後有種算法可以查詢能夠同時使用這兩個單列索引進行掃描，並將結果合併。
這種算法的三個變種: or條件的聯合(union)， and條件的相交(intersection) 及 組合前兩種情況的聯合及相交
例如:
`and`優化
可見在Extra列中，顯示為兩種索引的相交優化。
雖說如此，這種處理會帶來一些負面影響:
此外，這種優化有使用限制，例如，我的where條件中的使用的是a_id和b_id兩種單列索引，也只有在查詢這兩列的值的情況下才會運用到優化，當查詢這兩列之外的值時就無法使用優化。如下圖:
優化失效
查詢多一個gender欄位時，Extra列顯示並無優化策略。相同模式的sql語句，可能有時能使用索引，有時不能使用索引。是否能使用索引，取決於mysql查詢優化器對統計數據分析後，是否認為使用索引更快。
所以相比之下，對於一些常用多個需要聯合查詢的條件創建一個多列索引更好些。
3.4 選擇合適的索引列順序
這一節主要是針對 B-Tree索引，常用的存儲引擎即為InnoDB和MyISAM。
一條經驗法則(從書上學來的)，即 : 將選擇性最高的列放到索引放到索引的最前列。
按照上述的關於選擇性的介紹中，可以用一條sql計算出所有的需要用到的索引的相對應的選擇性，又或者在知道了該表中的大致數據記錄數的情況下，用show index from table來查看所有的索引對應的基數值(Cardinality)，也能大致比較出索引選擇性的高低。
查看索引
上圖可見People表中所有索引的基數。
也就是提醒大家，別忘了where子句中的排序、分組和範圍條件等因素，說不定你就在這踩了坑。
3.5 覆蓋索引
如果一個索引包含了所有需要查詢的欄位的值，就稱之為「覆蓋索引」。
覆蓋索引有以下幾點好處:
當發起一個索引覆蓋查詢時，在Extra列中可見「Using index」的信息。
例如:
覆蓋索引
建立的多列索引包含了所要查詢的欄位，索引可直接查詢Using index而提升速度。
注:
其一:當查詢中使用了一個 * 時，肯定是無法使用覆蓋索引的；
其二:如果不符合最左前綴匹配原則，也無法使用索引覆蓋。
3.6 冗餘索引
冗餘即多餘
例如，創建了key (a_id, b_id)索引時，如果再創建一個key (a_id)就是多餘的，因為它只是多列索引的前綴而已
但是當創建key (b_id)時，就不屬於冗餘索引了，因為上述的多列索引是無法單獨使用b_id 作索引查詢。
理論上冗餘索引會帶來一定程度上的查詢影響，與當前條查詢語句相關的索引數量越多，效率越低，原因在於優化器需要從information_schema中獲取相關索引的metadata信息並分析，索引數量越多，這個過程越漫長。雖然一般來說這個影響不太大。
索引太複雜，原理要理解，創建需謹慎，使用多思考。
(這句是給我自己說的)
以上。