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