當(dāng)人們談?wù)撍饕臅r候犹赖，如果沒有特別指明類型么翰，多半說的是B-Tree索引急灭，它使用B-Tree數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)。實際上很多存儲引擎使用的是B+Tree珠增，即每個葉子節(jié)點都包含指向下一個葉子節(jié)點的指針超歌，從而方便葉子節(jié)點的范圍遍歷。
??常用的存儲引擎以不同的方式使用B-Tree索引蒂教，性能也各有不同巍举，各有優(yōu)劣。MyISAM和InnoDB都使用B+Tree凝垛。例如：

• MyISAM使用前綴壓縮技術(shù)使得索引更小懊悯，InnoDB則按照原數(shù)據(jù)格式進(jìn)行存儲蜓谋。
• MyISAM索引通過數(shù)據(jù)的物理位置引用被索引的行，InnoDB則根據(jù)主鍵引用被索引的行炭分。

B-Tree通常意味著所有的值都是按順序存儲的桃焕，井且每一個葉子頁到根的距離相同。下面圖1捧毛、圖2展示了B-Tree索引的抽象表示观堂，大致反映了InnoDB索引是如何工作的。MyISAM使用的結(jié)構(gòu)有所不同呀忧，但基本思想是類似的师痕。

圖1 建立在B-Tree結(jié)構(gòu)（技術(shù)上是B+Tree）上的索引

圖2 建立在B-Tree結(jié)構(gòu)（技術(shù)上是B+Tree）上的索引

B-Tree索引能夠加快訪問數(shù)據(jù)的速度，因為存儲引擎不再需要進(jìn)行全表掃描來獲取需要的數(shù)據(jù)荐虐，取而代之的是從索引的根節(jié)點（圖示并未畫出）開始進(jìn)行搜索七兜。根節(jié)點的槽中存放了指向子節(jié)點的指針，存儲引擎根據(jù)這些指針向下層查找福扬。通過比較節(jié)點頁的值和要查找的值可以找到合適的指針進(jìn)入下層子節(jié)點腕铸，這些指針實際上定義了子節(jié)點頁中值的上限和下限。最終存儲引擎要么是找到對應(yīng)的值铛碑，要么該記錄不存在狠裹。
??葉子節(jié)點比較特別，它們的指針指向的是被索引的數(shù)據(jù)汽烦，而不是其他的節(jié)點頁（不同引擎的“指針”類型不同）涛菠。圖1和圖2中僅繪制了一個節(jié)點和其對應(yīng)的葉子節(jié)點，其實在根節(jié)點和葉子節(jié)點之間可能有很多層節(jié)點頁撇吞。樹的深度和表的大小直接相關(guān)俗冻。
??B-Tree對索引列是順序組織存儲的，所以很適合查找范圍數(shù)據(jù)牍颈。例如迄薄，在一個基于文本域的索引樹上，按字母順序傳遞連續(xù)的值進(jìn)行查找是非常合適的煮岁，所以像“找出所有以I到K開頭的名字”這樣的查找效率會非常高讥蔽。
假設(shè)有如下數(shù)據(jù)表：

CREATE TABLE `People` (
  `last_name` varchar(32) NOT NULL,
  `first_name` varchar(32) NOT NULL,
  `dob` date NOT NULL,
  `gender` enum('m','f') NOT NULL,
  KEY `last_name` (`last_name`,`first_name`,`dob`)
)

對于表中的每一行數(shù)據(jù)，索引中包含了last_name画机、first_name和dob列的值冶伞，下圖顯示了該索引是如何組織數(shù)據(jù)的存儲的。

建立在B-Tree結(jié)構(gòu)（技術(shù)上是B+Tree）索引樹中的部分條目示例

請注意步氏，索引對多個值進(jìn)行排序的依據(jù)是CREATE TABLE語句中定義索引時列的順序响禽。看一下最后兩個條目，兩個人的姓和名都一樣金抡，則根據(jù)他們的出生日期來排列順序瀑焦。B-Tree索引適用于全鍵值腌且、鍵值范圍或鍵前綴查找梗肝。其中鍵前綴查找只適用于根據(jù)最左前綴的查找。

全值匹配

全值匹配指的是和索引中的所有列進(jìn)行匹配铺董，例如前面提到的索引可用于查找姓名為Cuba Allen巫击、出生于1960-01-01的人。

匹配最左前綴

前面提到的索引可用于查找所有姓為Allen的人精续，即只使用索引的第一列坝锰。匹配列前綴也可以只匹配第一列值的開頭部分。例如前面提到的索引可用于查找所有以A開頭的姓的人重付。

mysql> explain select * from People where last_name = 'Allen';
+----+-------------+--------+------+---------------+-----------+---------+-------+------+-------------+
| id | select_type | table  | type | possible_keys | key       | key_len | ref   | rows | Extra       |
+----+-------------+--------+------+---------------+-----------+---------+-------+------+-------------+
|  1 | SIMPLE      | People | ref  | last_name     | last_name | 98      | const |    1 | Using where |
+----+-------------+--------+------+---------------+-----------+---------+-------+------+-------------+

mysql> explain select * from People where last_name like 'A%';
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key       | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+
|  1 | SIMPLE      | People | range | last_name     | last_name | 98      | NULL |    1 | Using where |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+

如下例子顷级，匹配列前綴不是第一列值的開頭部分，不會用到索引确垫。

mysql> explain select * from People where last_name like '%ll%';
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | People | ALL  | NULL          | NULL | NULL    | NULL |    4 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+

如下例子弓颈，當(dāng)使用中間列first_name查詢時，不會用到索引删掀。

mysql> explain select * from People where first_name = 'Cuba';
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | People | ALL  | NULL          | NULL | NULL    | NULL |    4 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+

匹配范圍值

例如前面提到的索引可用于查找姓在Allen和Barrymore之間的人翔冀，這里也只使用了索引的第一列。其實也是匹配最左前綴披泪。

精確匹配到某一列并范圍匹配另外一列

前面提到的索引也可用于查找所有姓為Allen纤子，并且名字是字母C開頭（比如Cuba、Carl等）的人款票。即第一列l(wèi)ast_name全匹配控硼，第二列first_name范圍匹配。

mysql> explain select * from People where last_name = 'Allen' and first_name like 'C%';
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key       | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+
|  1 | SIMPLE      | People | range | last_name     | last_name | 196     | NULL |    1 | Using where |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+

只訪問索引的查詢

B-Tree通嘲伲可以支持“只訪問索引的查詢”卡乾，即查詢只需要訪問索引，而無須訪問數(shù)據(jù)行姆钉。用Explain查看Extra可以看到Using index说订，如下所示。

mysql> explain select dob from People where last_name = "Allen" and first_name = 'Cu%';
+----+-------------+--------+------+---------------+-----------+---------+-------------+------+--------------------------+
| id | select_type | table  | type | possible_keys | key       | key_len | ref         | rows | Extra                    |
+----+-------------+--------+------+---------------+-----------+---------+-------------+------+--------------------------+
|  1 | SIMPLE      | People | ref  | last_name     | last_name | 196     | const,const |    1 | Using where; Using index |
+----+-------------+--------+------+---------------+-----------+---------+-------------+------+--------------------------+

因為索引樹中的節(jié)點是有序的潮瓶，所以除了按值查找之外陶冷，索引還可以用于查詢中的ORDER BY操作（按順序查找）。如果B-Tree可以按照某種方式查找到值毯辅，那么也可以按照這種方式用于排序埂伦。所以，如果ORDER BY子句滿足前面列出的幾種查詢類型思恐，則這個索引也可以滿足對應(yīng)的排序需求沾谜。
以第一列l(wèi)ast_name ORDER BY膊毁，可以使用索引，如下所示基跑。

mysql> explain select dob from People order by last_name;
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key       | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+
|  1 | SIMPLE      | People | index | NULL          | last_name | 199     | NULL |    4 | Using index |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+

以第一列first_name ORDER BY婚温，出現(xiàn)Using filesort，重新到數(shù)據(jù)行獲取first_name排序媳否，如下所示栅螟。

mysql> explain select dob from People order by first_name;
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-----------------------------+
| id | select_type | table  | type  | possible_keys | key       | key_len | ref  | rows | Extra                       |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-----------------------------+
|  1 | SIMPLE      | People | index | NULL          | last_name | 199     | NULL |    4 | Using index; Using filesort |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-----------------------------+

下面是一些關(guān)于B-Tree索引的限制：

• 如果不是按照索引的最左列開始查找，則無法使用索引篱竭。例如上面例子中的索引不能用于查找名字為Bill的人力图，也無法查找某個特定生日的人，因為這兩列都不是最左數(shù)據(jù)列掺逼。類似地吃媒，也無法查找姓氏以某個字母結(jié)尾的人。
• 不能跳過索引中的列吕喘。也就是說赘那，前面所述的索引無法用于查找姓為Smith并且在某個特定日期出生的人。如果不指定名（first_name）兽泄，則MySQL只能使用索引的第一列漓概。
• 如果查詢中有某個列的范圍(like between > <都算范圍查詢)查詢，則其右邊所有列都無法使用索引優(yōu)化查找病梢。例如有查詢WHERE last_name='Smith’AND first_name like '%J%'AND dob＝’1976-12-23'胃珍，這個查詢只能使用索引的前兩列，因為這里的like是一個范圍條件（但是服務(wù)器可以把其余列用于其他目的）蜓陌，并且first_name不是最左開始查找觅彰，索引也不能用first_name。如果范圍查詢列值的數(shù)量有限钮热，那么可以通過使用多個等于條件來代替范圍條件填抬。

所以前面提到的索引列的順序是多么的重要：這些限制都和索引列的順序有關(guān)。在優(yōu)化性能的時候隧期，可能需要使用相同的列但順序不同的索引來滿足不同類型的查詢需求飒责。

索引的優(yōu)點

最常見的B-Tree索引，按照順序存儲數(shù)據(jù)仆潮，所以MySQL可以用來做ORDER BY和GROUP BY操作宏蛉。因為數(shù)據(jù)是有序的，所以B-Tree也就會將相關(guān)的列值存儲在一起性置。最后拾并，因為索引中存儲了實際的列值，所以某些查詢只使用索引就能夠完成全部查詢⌒嵋澹總結(jié)下來索引有如下三個優(yōu)點：

• 索引大大減少了服務(wù)器需要掃描的數(shù)據(jù)量屏歹。
• 索引可以幫助服務(wù)器避免排序和臨時表。
• 索引可以將隨機(jī)I/O變?yōu)轫樞騃/O之碗。

三星索引理論

Lahdenmaki和Leach的三星索引理論：

• 一星：索引將相關(guān)的記錄放到一起蝙眶。
• 二星：索引中的數(shù)據(jù)順序和查找中的排列順序一致。
• 三星：索引中的列包含了查詢中需要的全部列继控。

表shop結(jié)構(gòu)：

mysql> desc shop;
+----------+---------------+------+-----+---------+----------------+
| Field    | Type          | Null | Key | Default | Extra          |
+----------+---------------+------+-----+---------+----------------+
| id       | int(11)       | NO   | PRI | NULL    | auto_increment |
| shop_id  | int(11)       | NO   | MUL | NULL    |                |
| goods_id | int(11)       | NO   |     | NULL    |                |
| pay_type | tinyint(1)    | NO   | MUL | NULL    |                |
| price    | decimal(10,2) | NO   | MUL | NULL    |                |
| comment  | varchar(4000) | YES  | MUL | NULL    |                |
+----------+---------------+------+-----+---------+----------------+

查詢下面的SQL：

select pay_type, price from shop where shop_id = 2 and goods_id = 2 order by price

沒有創(chuàng)建任何索引之前械馆，Explain結(jié)果：

explain select pay_type, price from shop where shop_id = 2 and goods_id = 2 order by price\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: shop
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 20029
        Extra: Using where; Using filesort

第一步構(gòu)建一星索引

根據(jù)where后面等值條件，或者范圍條件來構(gòu)建索引武通，即index(shop_id,goods_id) ，如下所示珊搀，用explain查看上面SQL使用這個索引冶忱。SQL優(yōu)化一般都說索引是為了能以最快的速度定位到想要的數(shù)據(jù)，即用空間來換時間境析，快速定位想要的數(shù)據(jù)后囚枪，也就過濾掉了不必要的數(shù)據(jù)，所以一星索引的核心就是利用索引來盡可能的過濾不必要的數(shù)據(jù)劳淆，減少數(shù)據(jù)處理的規(guī)模链沼，對于RDBMS來說是極為關(guān)鍵的，比如說shop表有1000000行沛鸵，shop_id的過濾度是10%括勺，goods_id的過濾度是0.1%，如果沒有索引曲掰，數(shù)據(jù)庫不得不把表里所有的一百萬行數(shù)據(jù)都讀出來疾捍，做處理，但是如果有了這個一星索引栏妖，需要處理的數(shù)據(jù)被極大的縮小乱豆，只需要根據(jù)索引找到符合條件的索引葉子節(jié)點的范圍，讀取0.1%10%1000000=100 rows就可以了吊趾，哪怕我們樂觀的假定產(chǎn)生的都是邏輯IO宛裕， 而不是物理IO，單次的差別就已經(jīng)很明顯论泛，更別說是執(zhí)行頻率很高的時候揩尸，我們線上很多爛SQL對DB造成了影響，一看機(jī)器邏輯讀都好幾百萬孵奶，基本上可以定位是SQL索引缺失疲酌，或者索引不合理造成的。

mysql> ALTER TABLE shop add index shop_id(`shop_id`, `goods_id`);

mysql> explain select pay_type, price from shop where shop_id = 2 and goods_id = 2 order by price\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: shop
         type: ref
possible_keys: shop_id
          key: shop_id
      key_len: 8
          ref: const,const
         rows: 19
        Extra: Using where; Using filesort

第二步構(gòu)建二星索引

針對上面的case，我們構(gòu)建索引如下index(shop_id, goods_id, price)朗恳，用explain查看上面SQL已經(jīng)沒有Using filesort湿颅。基本的原理就是利用索引的有序性，把消除order by或者group by等需要排序的操作粥诫，因為大家都知道排序是非常消耗CPU資源的油航，大量的排序操作會把CPU搞得很高，即使CPU吃得消怀浆，如果數(shù)據(jù)量比較大谊囚，需要排序的數(shù)據(jù)放不下內(nèi)存的sort buffer，只能悲劇的和外存換進(jìn)換出执赡，性能下降的就不是一點兩點镰踏，這時候利用索引避免排序的優(yōu)勢就明顯的體現(xiàn)出來了。

mysql> ALTER TABLE shop drop index shop_id;

mysql> ALTER TABLE shop add index shop_id(`shop_id`, `goods_id`, `price`);

mysql> explain select pay_type, price from shop where shop_id = 2 and goods_id = 2 order by price\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: shop
         type: ref
possible_keys: shop_id
          key: shop_id
      key_len: 8
          ref: const,const
         rows: 19
        Extra: Using where

第三步構(gòu)建三星索引

如下index(shop_id, goods_id, price,pay_type)沙合， 跟之前的二星索引的差別在于奠伪，在索引中額外添加了要查詢的列pay_type，這就是所謂的索引覆蓋首懈，用explain查看上面SQL有Using index绊率，即在索引的葉子節(jié)點就能夠讀到查詢SQL所需要的所有信息，而不需要回原表去查詢究履，在目前內(nèi)存如此充足的情況下滤否，很多時候，除了root節(jié)點和branch結(jié)構(gòu)最仑，甚至整個索引都是可以被放入內(nèi)存的藐俺，這樣能大概率的避免，至少是減少物理IO盯仪。

mysql> ALTER TABLE shop drop index shop_id;

mysql> ALTER TABLE shop add index shop_id(`shop_id`, `goods_id`, `price`, `pay_type`);

mysql> explain select pay_type, price from shop where shop_id = 2 and goods_id = 2 order by price\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: shop
         type: ref
possible_keys: shop_id
          key: shop_id
      key_len: 8
          ref: const,const
         rows: 19
        Extra: Using where; Using index

注意：索引是最好的解決方案嗎紊搪？

索引并不總是最好的工具。索引其實是一種權(quán)衡全景，是一種拿空間來換時間的藝術(shù)耀石。總的來說爸黄，只有當(dāng)索引幫助存儲引擎快速查找到記錄帶來的好處大于其帶來的額外工作時滞伟，索引才是有效的。對于非常小的表炕贵，大部分情況下簡單的全表掃描更高效梆奈。對于中到大表，索引就非常有效称开。但對于特大型的表亩钟，建立和使用索引的代價將隨之增長乓梨。這種情況下，則需要一種技術(shù)可以直接區(qū)分出需要查詢的一組數(shù)據(jù)清酥，而不是一條記錄一條記錄的匹配扶镀。例如可以使用分區(qū)技術(shù)。
??如果表的數(shù)量特別多焰轻，可以建立一個元數(shù)據(jù)信息表臭觉，用來查詢需要用到的某些特性。例如執(zhí)行那些需要聚合多個應(yīng)用分布在多個表的數(shù)據(jù)的查詢辱志，則需要記錄“哪個用戶的信息存儲在哪個表中”的元數(shù)據(jù)蝠筑，這樣在查詢時就可以直接忽略那些不包含指定用戶信息的表。