1.寫在前面
索引對于良好的性能非常關(guān)鍵沪伙，特別是當(dāng)表中的數(shù)據(jù)量越來越大的時候喷好，索引對性能的影響愈發(fā)重要泌类。而索引優(yōu)化應(yīng)該是對查詢優(yōu)化最有效的手段了卧抗，索引能夠輕易將查詢性能提高幾個數(shù)量級藤滥。本文是對MySQL索引的一個總結(jié)，希望通過本文能夠回答以下問題：
- 聚簇索引和非聚簇索引的區(qū)別社裆？
- 對于InnoDB引擎拙绊，為什么建議使用一個與業(yè)務(wù)無關(guān)的自增代理鍵做為主鍵？
- 對于InnoDB引擎，為什么索引列的順序會影響到查詢的性能标沪？
2.索引基礎(chǔ)
按照MySQL官方的定義：索引（在MySQL中也叫鍵(key)）是存在引擎用于快速找到記錄的一種數(shù)據(jù)結(jié)構(gòu)榄攀。
從索引的定義可以知道，索引其本質(zhì)是一種數(shù)據(jù)結(jié)構(gòu)金句。索引有多種類型檩赢，如B-Tree索引、哈希索引违寞、全文索引贞瞒、空間數(shù)據(jù)索引（R-Tree）等。對于MySQL趁曼，索引是在存儲引擎層實現(xiàn)军浆，如果沒有特別說明，我們說的索引都是使用B-Tree索引挡闰，從技術(shù)實現(xiàn)上來講乒融，MySQL B-Tree索引是其變種B+Tree實現(xiàn)的，下圖大致反映InnoDB索引是如何工作的尿这，MyISAM使用的結(jié)構(gòu)有所不同簇抵，但基本思想類似庆杜，后邊會詳細(xì)說：
簡單來說射众，對于非葉子結(jié)點：除了保存鍵值（key）外，還保存了指定子頁結(jié)點的指針晃财，且key左邊指針指向的結(jié)點的值均小于key叨橱，key右邊指針指向的值均大于等于key；對于葉子結(jié)點断盛，結(jié)點中的每一個key包含了一個指向數(shù)據(jù)的指針（依賴于不同存儲引擎罗洗，InnoDB存儲了原始數(shù)據(jù)，MyISAM存儲了被索引行的物理位置）并且每個結(jié)點包含一個指向下一個葉子頁的指針钢猛。
為什么說B-Tree索引能夠加快訪問數(shù)據(jù)的速度呢伙菜？因為存儲引擎不需要再進(jìn)行全表掃描來獲取需要的數(shù)據(jù)，取而代之的是從索引根結(jié)點開始進(jìn)行二分查找命迈，如果找到則返回對應(yīng)節(jié)點的值贩绕，否則對相應(yīng)槽中的指針指向的頁結(jié)點遞歸進(jìn)行查找，直到找到節(jié)點或記錄不存在壶愤。
3.索引的優(yōu)缺點
3.1優(yōu)點
- 索引大大減少了服務(wù)器需要掃描的數(shù)據(jù)量淑倾；
- 索引可以幫忙服務(wù)器避免排序和臨時表；
- 索引可以將隨機I/O變?yōu)轫樞騃/O征椒；
3.2缺點
- 索引占用存儲空間娇哆；
- 索引降低了修改操作（增加、修改、刪除）的性能碍讨；
4. B-Tree索引的查詢類型
通過上節(jié)已經(jīng)知道了B-Tree索引的數(shù)據(jù)結(jié)構(gòu)治力，下面通過例子看看為什么B-Tree索引的順序至關(guān)重要，假如有如下數(shù)據(jù)表：
CREATE TABLE People (
last_name varchar(50) not null,
first_name varchar(50) not null,
dob date not null,
gender enum('m', 'f') not null,
key(last_name, first_name, dob)
)ENGINE=InnoDB;
對于每一行數(shù)據(jù)勃黍，索引中包含 last_name, first_name和dob列的值琴许，下圖展示了索引是如何組織數(shù)據(jù)存儲的：
需要注意的是，索引對于多個值進(jìn)行排序的依賴是CREATE TABLE語句中定義索引時列的順序溉躲。如最后兩個人的姓我名都一樣榜田，則根據(jù)他們的出生日期進(jìn)行排序。
B-Tree索引適合于全鍵值锻梳、鍵值范圍或鍵前綴查找箭券。其中鍵前綴查找只適用于最左前綴查找，上例索引對如下類型的查詢有效：
全值匹配
全值匹配指的是和索引中的所有列進(jìn)行匹配疑枯，如前面提到的索引可以查找姓名為Cuba Allen辩块、出生于1960-01-01的人。匹配最左前綴
前面提到的索引可以用于查找所有姓為Allen的人荆永，即只使用索引的第一列废亭。匹配列前綴
也可以匹配某一列的值的開頭部分。如前面提到的索引可以用于查找所有以J開頭的姓的人具钥。這里也只使用了索引的第一列豆村。匹配范圍值
例如前面提到的索引可以用于查找Allen和Barrymore之間的人。這里也只使用了索引的第一列骂删。精確匹配某一列并范圍匹配另一列
前面提到的索引可以用于查找姓為Allen掌动，并且名是以字母K開頭（如Kim Karl）的人，即第一列last_name全匹配宁玫，第二列first_name范圍匹配粗恢。只訪問索引的查詢
從B-Tree的數(shù)據(jù)結(jié)構(gòu)中可以看出，索引已經(jīng)存儲在了數(shù)據(jù)結(jié)構(gòu)中欧瘪，B-Tree通尘焐洌可以支持只訪問索引的查詢，即查詢只需要訪問索引佛掖，也稱為“覆蓋索引”妖碉。
如果不按索引的最左列開始查找，則無法使用索引苦囱。例如上面例子中如果我們查找名字為Bill的人或查找某個特定生日的人嗅绸，則無法使用索引，存儲引擎會進(jìn)行會表掃描撕彤，這便是為什么索引列的順序會影響到查詢的原因鱼鸠。
5. 高性能索引策略
正確地創(chuàng)建和使用索引是實現(xiàn)高性能查詢的基礎(chǔ)猛拴。通過下面這些索引策略可以真正發(fā)揮索引的優(yōu)勢。
5.1 前綴索引和索引選擇性
有時候需要索引很長的字符串蚀狰，這會讓索引變得大且慢愉昆，根據(jù)前面講過的最左前綴，通過可以索引字符串開始的部分字符麻蹋，這樣可以大大節(jié)約索引存儲空間跛溉，提高索引效率。但這會降低索引的選擇性扮授。
索引的選擇性是指不重復(fù)的索引值芳室，也稱為基數(shù)（cardinality）和數(shù)據(jù)表的記錄總數(shù)（#T）的比值，范圍從1/#T到1之間刹勃，索引的選擇性越高則查詢效率越高堪侯。我們通常可以采用以下公式進(jìn)行選擇性計算：
Selectivity = COUNT(DISTINCT(field)) / COUNT(*)
來看一個例子荔仁，例子來源MySQL employee example：
CREATE TABLE `employees` (
`emp_no` int(11) NOT NULL,
`birth_date` date NOT NULL,
`first_name` varchar(14) NOT NULL,
`last_name` varchar(16) NOT NULL,
`gender` enum('M','F') NOT NULL,
`hire_date` date NOT NULL,
PRIMARY KEY (`emp_no`),
) ENGINE=InnoDB;
如上表伍宦，出于業(yè)務(wù)的需求，我們需要根據(jù)first_name和last_name進(jìn)行查找乏梁，可以為<first_name次洼，last_name>建立索引，但fist_name和last_name加起來長度為30遇骑，可以考慮用first_name和last_name的前幾個字符建立索引卖毁。但last_name取幾個字符呢，我們可以通過計算其選擇性來決定质蕉，比如<first_name, left(last_name, 3)>势篡，其選擇性如下：
mysql> SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
| 0.7879 |
+-------------+
看起來還不錯，如果把last_name的前綴加到4模暗，看看選擇性如下：
mysql> SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
| 0.9007 |
+-------------+
這個選擇性已經(jīng)比較好了，而且索引長度也只有18念祭，比起<first_name, last_name>短了近一半兑宇，于是可以建立索引：
ALTER TABLE employees.employees
ADD INDEX `first_name_last_name4` (first_name, last_name(4));
5.2 多列索引
多列索引也叫聯(lián)合索引。很多人對多列索引理解不夠粱坤，一個常見的錯誤就是為每一個列創(chuàng)建獨立的索引隶糕，或者按照錯誤的順序創(chuàng)建多列索引。這種理解是非常錯誤的站玄，在多個列上建立獨立的索引大部分情況下并不能提高M(jìn)ySQL的查詢性能枚驻。
當(dāng)出現(xiàn)服務(wù)器對多個索引做相交操作（通常是多個AND條件），通常意味著需要一個包含所有相關(guān)列的多列索引株旷，而不是多個獨立的單列索引再登。
5.3 選擇合適的索引列順序
在一個多列的B-Tree索引中尔邓，索引列的順序意味著索引首先按照最左列進(jìn)行排序，其次是第二列锉矢，等等梯嗽。索引是按照升序或降序進(jìn)行掃描，以滿足精確符合列順序的ORDER BY沽损、GROUP BY灯节、和DISTINCT等子句的查詢需求。所以多列索引的列順序至關(guān)重要绵估。
5.4 聚簇索引和非聚簇索引
聚簇索引并不是一種單獨的索引類型炎疆，而一種數(shù)據(jù)存儲方式。
InnoDB采用的是聚簇索引国裳，其實現(xiàn)原理是在同一個結(jié)構(gòu)中保存了B-Tree索引和數(shù)據(jù)行磷雇，如下圖是聚簇索引的分布圖，索引列是包含的整數(shù)值躏救，葉子頁中包含了行的全部數(shù)據(jù)：
對于聚簇索引唯笙，插入速度嚴(yán)重依賴于插入順序。按照主鍵的順序插入是加載數(shù)據(jù)到InnoDB表中速度最快的方式盒使。另外基于聚簇索引表在插入新行崩掘，或主鍵被更新導(dǎo)致需要移動行的時候，可能面臨“頁分裂”的問題少办，如果主鍵采用遞增方式順序插入苞慢，也能避免頁分裂造成隨機I/O和占用更多磁盤空間的問題。
對于InnoDB引擎是通過主鍵聚集數(shù)據(jù)的英妓，也就是說上圖中的被索引的列就是主鍵挽放。如果沒有定義主鍵，InnoDB會選擇一個惟一的非空索引代替蔓纠。如果沒有這樣的索引辑畦，InnoDB會隱式定義一個主鍵來作為聚簇索引。
對于InnoDB引擎腿倚，二級索引的葉子節(jié)點保存的不是指向行的物理位置纯出，而是行的主鍵值，也就是說二級索引訪問需要兩次索引查找敷燎，而不是一次暂筝。
相對于聚簇索引，非聚簇索引是指索引和數(shù)據(jù)是分離的硬贯。MyISAM存儲引擎是采用的非聚簇索引焕襟。其索引的葉結(jié)點存放的不再是數(shù)據(jù)，而是存儲的數(shù)據(jù)的物理地址饭豹，為了簡單說明鸵赖，可以理解為“行號”务漩，如下圖所示：
下圖可以很容易看出InnoDB（聚簇索引）和MyISAM（非聚簇索引）保存數(shù)據(jù)和索引的區(qū)別：
5.5 覆蓋索引
如果一個索引包含（或者說覆蓋）所有需要查詢的字段值 ，我們就稱之為覆蓋索引卫漫。覆蓋索引能極大提高查詢性能菲饼，因為只需要掃描索引而無須回表，有如下好處：
- 索引條目通常遠(yuǎn)小于數(shù)據(jù)行大小列赎，所以如果只需要讀索引宏悦，那MySQL就會極大地減小數(shù)據(jù)訪問量。
- 因為索引是按照列值順序存儲的包吝，所以對于I/O密集型的范圍查詢會比隨機從磁盤讀取一行數(shù)據(jù)的I/O要少得多饼煞。
- 一些存儲引擎如MyISAM在內(nèi)存中只緩存索引，數(shù)據(jù)則依賴于操作系統(tǒng)來緩存诗越。而訪問數(shù)據(jù)需要一次系統(tǒng)調(diào)用砖瞧。這可能導(dǎo)致嚴(yán)重的性能問題。
- 由于InnoDB的聚簇索引嚷狞，覆蓋索引對InnoDB表特別有用块促。InnoDB的二級索引在葉子節(jié)點中保存了行的主鍵值，所以如果二級主鍵能夠覆蓋查詢床未，則可以避免對主鍵索引的二次查詢竭翠。
5.6 使用索引掃描做排序
MySQL有兩種方式可以生成有序結(jié)果：
- 通過排序操作；
- 按照索引順序掃描薇搁；
如何判斷使用發(fā)哪些方式呢斋扰？可以使用explain查看type列的值（這里強烈建議看看MySQL幫忙手冊中對explain中各個字段的解釋，這對優(yōu)化查詢的時候至關(guān)重要）啃洋，如果是index則表示MySQL使用了索引掃描來排序传货。
掃描索引本身是很快的，因為只需要從一條索引記錄移動到緊接著的下一條記錄宏娄。但如果索引不能覆蓋查詢所需的全部列问裕，那就不得不掃描一條索引記錄就都回表查詢一次對應(yīng)的行。這基本上都是隨機I/O绝编，因此按索引順序讀取數(shù)據(jù)的速度通常比順序地全表掃描慢僻澎，尤其是在I/O密集型的工作負(fù)載時。
5.7 冗余和重復(fù)索引
MySQL允許在相同的列上創(chuàng)建多個索引十饥。重復(fù)索引是指在相同的列上按照相同的順序創(chuàng)建的相同類型的索引。
注意重復(fù)索引不是冗余索引祖乳。如果創(chuàng)建的索引<A, B>逗堵，再創(chuàng)建索引<A>就是冗余索引，因為索引<A>只是索引<A,B>的前綴索引眷昆。因此<A,B>可以當(dāng)作索引<A>來使用蜒秤。但如果再創(chuàng)建索引<B,A>汁咏，則不是冗余索引，因為<B>不是<A作媚，B>的最左前綴攘滩。
大多數(shù)情況下都不需要冗余索引，但有時候出于性能方面的考慮需要冗余索引纸泡，因為擴(kuò)展已有的索引會導(dǎo)致其變得太大漂问，從而影響其他使用該索引的查詢性能。
總結(jié)
選擇索引和編寫利用這些索引的查詢時女揭，有三個原則始終需要記自榧佟：
- 單行訪問是很慢的。特別是在機械硬盤中吧兔。最好讀取的塊中能包含盡可能多所需要的行磷仰。使用索引可以創(chuàng)建位置引用以提升效率。
- 按照順序訪問數(shù)據(jù)是很快的境蔼，主要有兩個原因灶平。第一，順序I/O不需要多次磁盤尋道箍土；第二逢享，如果服務(wù)器能夠按照需要順序讀取數(shù)據(jù)，那么就不再需要額外的排序操作涮帘。
- 索引覆蓋是很快的拼苍。如果一個索引包含了查詢所需的所有列，那么存儲引擎就不需要再回表查找行调缨。這避免了大量單行訪問疮鲫。
理解索引如果工作對優(yōu)化查詢非常重要。如果判斷一個系統(tǒng)創(chuàng)建的索引是否合理弦叶？一般來說先按響應(yīng)時間來對查詢進(jìn)行分析俊犯。找出消耗最長時間的查詢或者那么給服務(wù)器帶來最大壓力的查詢（查詢性能分析方法），然后檢查這些查詢的schema伤哺、SQL和索引結(jié)構(gòu)燕侠，判斷是否有查詢掃描了太多的行（通過explain)，是否做了額外的排序或者使用了臨時表立莉，是否使用了隨機I/O訪問數(shù)據(jù)绢彤，或者是否有太多回表查詢那些不在索引中的列的操作。
參考
[1] High Performance MySQL
[2] http://blog.codinglabs.org/articles/theory-of-mysql-index.html
[3] https://zh.wikipedia.org/wiki/B%E6%A0%91#%E6%90%9C%E7%B4%A2
