索引是一種用于快速查詢行的數據結構，就像一本書的目錄就是一個索引，如果想在一本書中找到某個主題，一般會先找到對應頁碼。在MySQL中，存儲引擎用類似的方法使用索引，先在索引中找到對應值，然后根據匹配的索引記錄找到對應的行。

我們首先了解一下索引的幾種類型和索引的結構。

索引類型

B樹

大多數存儲引擎都支持B樹索引。b樹通常意味著所有的值都是按順序存儲的，并且每一個葉子也到根的距離相同。B樹索引能夠加快訪問數據的速度，因為存儲引擎不再需要進行全表掃描來獲取數據。下圖就是一顆簡單的B數。

B樹的查詢流程：

如上圖我要從找到E字母，查找流程如下：

獲取根節點的關鍵字進行比較，當前根節點關鍵字為M，E<M（26個字母順序），所以往找到指向左邊的子節點（二分法規則，左小右大，左邊放小于當前節點值的子節點、右邊放大于當前節點值的子節點）；
拿到關鍵字D和G，D<E<G 所以直接找到D和G中間的節點；
拿到E和F，因為E=E 所以直接返回關鍵字和指針信息（如果樹結構里面沒有包含所要查找的節點則返回null）；
通過指針信息取出這條記錄的所有信息；

B+樹

下圖為B+樹的結構，B+樹是B樹的升級版，我們可以觀察一下，B樹和B+樹的區別是什么？

B+樹和B樹的區別是：

B樹的節點中沒有重復元素，B+樹有。
B樹的中間節點會存儲數據指針信息，而B+樹只有葉子節點才存儲。
B+樹的每個葉子節點有一個指針指向下一個節點，把所有的葉子節點串在了一起。

從下圖我們可以直觀的看到B樹和B+樹的區別：紫紅色的箭頭是指向被索引的數據的指針，大紅色的箭頭即指向下一個葉子節點的指針。

我們假設被索引的列是主鍵，現在查找主鍵為5的記錄，模擬一下查找的過程：

B樹，在倒數第二層的節點中找到5后，可以立刻拿到指針獲取行數據，查找停止。

B+樹，在倒數第二層的節點中找到5后，由于中間節點不存有指針信息，則繼續往下查找，在葉子節點中找到5，拿到指針獲取行數據，查找停止。

B+樹每個父節點的元素都會出現在子節點中，是子節點的最大（或最小）元素。葉子節點存儲了被索引列的所有的數據。

那B+樹比起B樹有什么優點呢？

由于中間節點不存指針，同樣大小的磁盤頁可以容納更多的節點元素，樹的高度就小。（數據量相同的情況下，B+樹比B樹更加“矮胖”），查找起來就更快。
B+樹每次查找都必須到葉子節點才能獲取數據，而B樹不一定，B樹可以在非葉子節點上獲取數據。因此B+樹查找的時間更穩定。
B+樹的每一個葉子節點都有指向下一個葉子節點的指針，方便范圍查詢和全表查詢：只需要從第一個葉子節點開始順著指針一直掃描下去即可，而B樹則要對樹做中序遍歷。

了解了B+樹的結構之后，我們對一張具體的表做分析：

create table Student(
 last_name varchar(50) not null, 
 first_name varchar(50) not null, 
 birthday date not null, 
 gender int(2) not null, 
 key(last_name, first_name, birthday)
);

對于表中的每一行數據，索引中包含了name，birthday列的值。下圖顯示了該索引的結構：

索引對多個值進行排序的依據是create table語句中定義索引時列的順序，即如果名字相同，則根據生日來排序。

B+樹的結構決定了這種索引對以下類型的查詢有效：

全值匹配 和索引中所有的列進行匹配，例如查找姓名為Cuba Allen，生日為1960-01-01的人。
匹配最左前綴 查找姓為Allen的人，即只用索引的第一列。
匹配列前綴 匹配某一列的值的開頭部分，例如查找所有以J開頭的姓的人。
匹配范圍值 查找姓在Allen和Barrymore之間的人。
精確匹配某一列并范圍匹配另外一列 查找姓為Allen，名字是字母K開頭的人。即第一列last_name全匹配，第二列first_name范圍匹配。
只訪問索引的查詢 查詢只需要訪問索引，無需訪問數據行。這種索引叫做覆蓋索引。

一些限制：

如果不是按照索引的最左列開始查找，無法使用索引。例如上面例子中的索引無法用于查找某個特定生日的人，因為生日不是最左數據列。也不能查找last_name以某個字母結尾的人。
不能跳過索引的列。上述索引無法用于查找last_name為Smith并且某個特定生日的人。如果不指定first_name，則mysql只能使用索引的第一列。
如果查詢中有某個列的范圍查詢，則右邊所有的列都無法使用索引優化查找。例如查詢WHERE last_name=’Smith’ AND first_name LIKE ‘J%’ AND birthday=‘1996-05-19’，這個查詢只能使用索引的前兩列。

哈希索引

哈希索引，只有精確匹配索引所有列的查詢才有效。對于每一行數據，存儲引擎都會對所有的索引列計算一個哈希碼。哈希索引將所有的哈希碼存儲在索引中，同時在哈希表中保存指向每個數據行的指針。如果多個列的哈希值相同，索引會以鏈表的方式存放多個指針記錄到同一個哈希條目中。

因為索引自身只存儲對應的哈希值，所以索引的結構十分緊湊，哈希索引查找的速度非常快。但是哈希索引也有它的限制：

哈希索引不是按照索引順序存儲的，無法用于排序。
不支持部分索引列匹配查找。
不支持范圍查找。

聚集索引（clusterd index）

每個存儲引擎為InnoDB的表都有一個特殊的索引，叫聚集索引。聚集索引并不是一種單獨的索引類型，而是一種數據存儲方式。當表有聚集索引的時候，它的數據行實際上存放在葉子頁中。一個表不可能有兩個地方存放數據，所以一個表只能有一個聚集索引。

因為是存儲引擎負責實現索引，因此不是所有的存儲引擎都支持聚集索引。InnoDB表中聚集索引的索引列就是主鍵，所以聚集索引也叫主鍵索引。

例如下面這張InnoDB表：

create table Student(
 id int(11) primary key auto_increment,
 last_name varchar(50) not null, 
 first_name varchar(50) not null, 
 birthday date not null
);

聚集索引（主鍵索引）的結構如下圖：

這是一課B+樹，它的葉子頁包含了行的全部數據，節點頁只包含了索引列（即主鍵）。

二級索引（secondary indexes）

對于InnoDB表，在非主鍵列的其他列上建的索引就是二級索引（因為聚集索引只有一個）。二級索引可以有0個，1個或者多個。二級索引和聚集索引的區別是什么呢？二級索引的節點頁和聚集索引一樣，只存被索引列的值，而二級索引的葉子頁除了索引列值，還存這一列對應的主鍵值。

InnoDB和MyISAM的數據分布對比

以下表為例，我們看下InnoDB和MyISAM是如何存儲這個表的：

create table layout_test(
 col1 int(11) primary key, 
 col2 int(11) not null, 
 key(col2)
);

InnoDB表的數據分布

聚集索引（主鍵索引）分布如下：

可以看到，葉子節點存儲了整個表的數據，而不是只有索引列，每個葉子節點包含了主鍵值、事務ID、用于事務和MVCC的回滾指針以及所有的剩余列（col2）。

二級索引分布如下：

二級索引的葉子節點中存儲的不是“行指針”，而是主鍵值，并以此作為指向行的“指針”。這樣的策略減少了當出現行移動或者數據頁分裂時二級索引的維護工作。使用主鍵當做指針會讓二級索引占更多空間，但好處是InnoDB在移動行時無需更新二級索引中的這個指針。

MyISAM表的數據分布

col1列上的索引：

col2列上的索引：

實際上MyISAM中主鍵索引和其他索引在結構上沒有什么不同。

從下圖可以看出InnoDB和MyISAM保存數據和索引的區別。

聚集索引的優點：

可以把相關數據保存在一起，例如實現電子郵箱時，根據用戶ID來聚集數據，讀取少數的數據頁就能獲取某個用戶的全部郵件。
聚集索引將索引和數據保存在同一個B樹中，因此從聚集索引中獲取數據比在非聚集索引中要快一些。

聚集索引的缺點：

插入速度嚴重依賴插入順序。按照主鍵的順序插入是加載數據到InnoDB表中速度最快的方式。假如磁盤中的某一個已經存滿了，但是新增的行要插入到這一頁當中，存儲引擎就會把該也分裂成兩個頁面來容納該行，這就是一次頁分裂操作。頁分裂會導致表占用更多的磁盤空間。
更新聚集索引列的代價很高，會強制InnoDB將每個被更新的行移動到新的位置。
用二級索引訪問數據需要兩個索引查找，不是一次。因為要先從二級索引的葉子節點獲得主鍵值，再根據這主鍵去聚集索引中查到對應的行，所以需要兩次B樹查找。