一、索引基礎

1. B-Tree索引

<1> 所有的值都是按順序存儲的，并且每一個葉子頁到根的距離相同。

<2> 順序組織存儲，很適合查找范圍數據，效率會非常高。

<3> 可以有效使用B-Tree索引的查詢：全值匹配、匹配最左前綴、匹配列前綴、匹配范圍值、精確匹配某一列并范圍匹配另一列、只訪問索引的查詢，還可以用于查詢中的order by和group by操作。

<4> B-Tree索引的限制：

　　如果不是按照索引的最左列開始查找，則無法使用索引；

　　不能跳過索引中的列；

　　如果查詢中有某個列的查詢范圍，則其右邊所有列都無法使用索引優化查詢。

2. 哈希索引

<1> 基于哈希表實現，只對精確匹配索引所有列的查詢才有效。

<2> 對于每一行數據，存儲引擎都會對所有的索引列計算一個哈希碼，將所有的哈希碼存儲在索引中，同時在哈希表中保存指向每個數據行的指針。

<3> 在mysql中只有memory引擎顯式支持哈希索引。Memory引擎支持非唯一哈希索引，如果多個哈希列的哈希值相同，索引會以鏈表的方式存放多個記錄指針到同一個哈希條目中。

<4> 哈希索引只需存儲哈希值和對應的行數據地址指針，所以索引的結構十分緊湊，使得哈希索引查找的速度非常快。

<5> 哈希索引限制：

　　哈希索引只包含哈希值和行指針，而不存儲字段值，所以不能使用索引中的值來避免讀取行，即無法使用哈希索引進行索引覆蓋查詢。

　　哈希索引數據并不是按照索引值順序存儲的，所以無法用于排序。

　　不支持部分索引列匹配查找，因為哈希索引始終是使用索引列的全部內容來計算哈希值的。

　　只支持等值比較查詢（=、IN、<=>），不支持任何范圍查詢。

　　出現哈希沖突時需要遍歷鏈表中所有的行指針，逐行進行比較直到找到所有符合條件的行。沖突很多的話一些索引維護操作的代價也會很高。

3. 創建自定義哈希索引

　　如果存儲引擎不支持哈希索引，可以在B-Tree索引基礎上創建一個偽哈希索引。還是使用B-Tree進行查找，但是使用哈希值而不是鍵本身進行索引查找。這在字段值是很長的字符串的時候，可以很好地提升性能。

　　可以選擇CRC32或FNV64作為哈希函數（哈希值為整數），不要使用SHA1和MD5，因為這兩個函數產生的哈希值是非常長的字符串。

　　可以使用觸發器來維護哈希值。

　　為避免哈希沖突，使用哈希索引進行查詢的時候，必須在where條件中帶入哈希值和對應列的值。

 

二、索引優點

1. 大大減少了服務器需要掃描的數據量。

2. 可以幫助服務器避免排序和臨時表。

3. 可以將隨機I/O變為順序I/O。

　　評價一個索引是否適合某個查詢的“三星系統”：索引將相關的記錄放到一起；索引中的數據順序和查詢中的排列順序一致；索引中的列包含了查詢中需要的全部列。

　　然而，索引并不總是最好的解決方案，只有當索引幫助存儲引擎快速查找到記錄帶來的好處大于其帶來的額外工作時索引才是有效的。對于非常小的表，大部分情況下簡單的全表掃描更高效；對于中到大型表，索引就非常有效；但對于特大型表，建立和使用索引的代價增大，需要考慮使用分區、塊級別元數據技術等其他技術。

 

三、高性能的索引策略

1. 獨立的列

　　如果查詢中的列不是獨立的，mysql就不會使用索引，“獨立的列”是指索引列不能是表達式的一部分，也不能是函數的參數。

2. 前綴索引和索引選擇性

<1> 前綴索引可以節約索引空間，提高索引效率。

<2> 使用前綴索引會降低索引的選擇性（不重復的索引值和數據表記錄總數的比值，索引的選擇性越高則查詢效率越高，唯一索引的選擇性是1，這是性能最好的），所以要選擇足夠長的前綴，但又不能太長，太長會占用太多存儲空間，所以需要對最常見值列表進行分析來決定前綴的合適長度。可以將平均選擇性：Select count(distinct left(name,length))/count(*) from ...; 與完整列選擇性進行對比得出最適合的前綴長度。另外，數據分布不均勻時也需要考慮最壞的情況。

<3> 前綴索引無法使用于order by和group by，也無法做覆蓋掃描。

3. 多列索引選擇合適的索引列順序

　　多列索引的索引列順序選擇通常都要考慮如何更好滿足查詢、排序、分組的需要。當不需要考慮排序和分組時，將選擇性最高的列放在前面通常是很好的，當然也需要結合值的分布考慮，可能需要根據那些運行頻率最高的查詢來調整索引列的順序。

4. 聚簇索引

<1> 當表有聚簇索引時，它的數據行實際上存放在索引的葉子頁中。（葉子頁包含了行的全部列數據，但是節點頁只包含了索引列）

<2> 一個表只能有一個聚簇索引。（覆蓋索引可以模擬多個聚簇索引的情況）

<3> 不是所有的存儲引擎都支持聚簇索引。

<4> 一些數據庫服務器允許選擇哪個索引作為聚簇索引，但mysql的存儲引擎并不支持。InnoDB通過主鍵聚集數據，如果沒有定義主鍵，則選擇一個唯一的非空索引代替。如果沒有這樣的索引，就隱式定義一個主鍵來作為聚簇索引。InnoDB只聚集在同一個頁面中的記錄，包含相鄰鍵值的頁面可能會相距甚遠。

<5> 聚簇索引的優點：

　　可以把相關的數據保存在一起。

　　數據訪問更快。

　　使用覆蓋索引掃描的查詢可以直接使用頁節點中的主鍵值。

<6> 聚簇索引缺點：

　　聚簇數據最大限度地提高了I/O密集型應用的性能，但是如果數據全部都放在內存中，則訪問的順序就沒那么重要了，聚簇索引也就沒什么優勢了。

　　插入速度嚴重依賴于插入順序。

　　更新聚簇索引列的代價很高，因為會強制InnoDB將每個被更新的列移動到新的位置。

　　基于聚簇索引的表在插入新行或者主鍵被更新導致需要移動行的時候，可能面臨“頁分裂”的問題，導致表占用更多的磁盤空間。

　　聚簇索引可能導致全表掃描變慢，尤其是行比較稀疏，或者由于頁分裂導致數據存儲不連續的時候。

　　二級索引（非聚簇索引）可能要更大，因為在二級索引的葉子節點包含了引用行的主鍵列。

　　二級索引訪問需要兩次索引查找。（對于InnoDB，自適應哈希索引能減少這樣的重復工作）

InnoDB和MyISAM的數據分布對比：

<1> MyISAM按照數據插入的順序存儲在磁盤上。

<2> MyISAM中主鍵索引和其他索引在結構上沒什么不同，主鍵索引就是一個名為primary的唯一非空索引。

<3> 聚簇索引的每一個葉子節點都包含了主鍵、事務ID、用于事務和MVCC的回滾指針以及所有的剩余列。

<4> InnoDB二級索引的葉子節點存儲的不是“行指針”而是主鍵值，并以此作為指向行的“指針”。好處：InnoDB在移動行時無須更新二級索引中的這個“指針”，壞處：二級索引占用更多的空間。

在InnoDB表中按主鍵順序插入行：

　　使用InnoDB時應該盡可能地按主鍵順序插入數據，并且盡可能地使用單調增加的聚簇鍵的值來插入新行，否則會導致已經刷到磁盤上的目標頁被重新讀取到內存中、頁分裂、數據碎片等情況。需要optimize table來重建表并優化頁的填充。

　　對于高并發工作負載，在InnoDB中按主鍵順序插入可能會造成明顯的爭用，可能需要考慮重新設計表或應用，或者更改innodb_autoinc_lock_mode配置。

5. 覆蓋索引

　　索引包含了所有需要查詢的字段的值，無須讀取數據行。

覆蓋索引優點：

<1> MySql會極大地減少數據訪問量。

<2> 對于I/O密集型的范圍查詢會比隨機從磁盤中讀取每一行數據的I/O要少得多。

<3> 一些存儲引擎如MyISAM在內存中只緩存索引，數據則依賴于操作系統來緩存，因此訪問數據需要一次系統調用，使用覆蓋索引就不需要系統調用了。

<4> 如果InnoDB的二級索引為覆蓋索引，則可以避免對主鍵索引的二次查詢。

注意：不是所有類型的索引都可以成為覆蓋索引，也不是所有存儲引擎都支持覆蓋索引。MySql只能使用B-Tree索引做覆蓋索引。

索引覆蓋查詢：

　　MySQL查詢優化器會在執行查詢前判斷是否有一個索引能進行覆蓋。（就算沒有where子句也可以使用索引覆蓋查詢）Explain出來的“extra”列為“using index”說明查詢使用了覆蓋索引。

使用索引掃描來做排序：

　　如果Explain出來的“type”列為“index”說明使用了索引掃描來做排序。按索引順序讀取數據的速度通常要比順序地全表掃描慢，因為如果索引不能覆蓋查詢所需的全部列，每掃描一條索引記錄就要回表查詢一次對應的行，這基本上都是隨機I/O。

　　MySQL可以使用同一個索引既滿足排序又用于查找行。用于排序的索引需要滿足以下條件：

<1> 索引的列順序和order by子句的順序完全一致，并且所有列的排序方向都一樣。

<2> 如果查詢需要關聯多張表，則只有當order by子句引用的字段全部為第一張表時，才能使用索引做排序。

<3> order by子句引用的字段需要滿足索引的最左前綴的要求。有一種情況order by子句可以不滿足索引的最左前綴的要求，就是前導列為常量的時候，例如where子句或join子句中對這些列指定了常量。

壓縮（前綴壓縮）索引：

　　MyISAM存儲引擎使用前綴壓縮來減少索引大小，從而讓更多的索引可以放入內存中，提高性能。具體方法：先完全保存索引塊中的第一個值，然后將其他值和第一個值進行比較得到相同前綴的字節數和剩余的不同后綴部分，把相同前綴的字節數和剩余的不同后綴部分存儲起來即可。

　　壓縮索引的缺點是：myiSAM查找時無法在索引塊使用二分查找而只能從頭開始掃描，order by desc時倒序掃描更慢。

　　可以在create table語句中指定pack_keys參數來控制索引壓縮的方式。

冗余和重復索引：

　　重復索引是指在相同的列上按照相同的順序創建相同類型的索引。MySQL需要單獨維護重復的索引，并且優化器在優化查詢的時候也需要逐個進行考慮，重復索引會影響性能。

　　MySQL的唯一限制和主鍵限制都是通過索引實現的。

　　如果創建了索引(A,B)，再創建索引(A)就是冗余索引。不同類型的索引不算冗余。應該盡量擴展已有的索引而不是創建新索引，除非擴展之后會對性能有不好的影響。

索引和鎖：

<1> 索引可以讓查詢鎖定更少的行。

<2> 即使使用了索引，InnoDB也可能鎖住一些不需要的數據。

<3> InnoDB在二級索引上使用共享讀鎖，但訪問主鍵索引需要排它鎖，這消除了使用覆蓋索引的可能性，并且使得select for update比lock in share mode或非鎖定查詢要慢很多。

 

四、索引優化策略

1. 有些列雖然選擇性低，但如果在where子句中使用頻率很高的話也應該創建索引，或將其作為多列索引的前綴列。

2. 就算在查詢中沒有某個列的限制，也可以加上這個列的判斷，這樣mysql才能匹配索引的最左前綴。如：sex in (‘m’,’f’)，但也不能濫用，每增加一個In條件優化器需要做的組合都將以指數形式增加，降低查詢性能。

3. Mysql查詢只能使用索引的最左前綴，直到遇到第一個范圍條件列，所以盡可能將需要做范圍查詢的列放在索引的后面，以便優化器能使用盡可能多的索引列。（用IN來來代替范圍條件）

4.除了or查詢，MySQL查詢每次最多只使用一個索引，因為相對于全表掃描和只使用一個索引，去分析兩個或兩個以上的索引二叉樹更加耗時。對于查詢：select col from table where col1=** and col2=*** and col3=****，建立復合索引(col1,col2,col3)來進行查詢的性能是最好的。

 

五、維護索引和表

1. check table：檢查索引和表的錯誤。

2. repair table：修復損壞的表。如果存儲引擎不支持可以通過一個不做任何操作的alter命令來重建表。

3. analyze table：重新生成索引統計信息。

　　MySQL的查詢優化器會通過records_in_range()和info()這兩個API來了解存儲引擎的索引值的分布信息，以決定如何使用索引。每種存儲引擎實現索引統計信息的方式不同：Memory引擎不存儲索引統計信息，myisam將索引統計信息存儲在磁盤中，InnoDB通過隨機的索引訪問進行評估并將統計信息存儲在內存中。InnoDB在打開某些information_schema表，或使用show table status和show index，或在mysql客戶端開啟自動補全功能的時候都會觸發索引統計信息的更新。

4. optimize table/導出再導入：減少索引和數據的碎片。如果存儲引擎不支持可以通過不做任何操作的alter命令來重建表。

 

最后推薦一篇博文：MySQL索引背后的數據結構及算法原理，這篇博文中結合數據結構和計算機磁盤讀寫原理詳細分析了數據庫系統為何使用Btree作為索引數據結構，以及MySQL聚簇索引和非聚簇索引的實現，如何高性能使用索引的策略，是我閱讀過寫得最好的文章了，強力推薦！！！