InnoDB存儲引擎支持以下幾種常見的索引，如B+樹索引、哈希索引、全文索引。哈希索引是自適應的，InnoDB會根據表的使用情況自動為表生成哈希索引。

B+樹索引是目前關系型數據庫中最常用、最有效的索引之一，其索引結構是一種多路平衡樹結構（與二叉樹類似，B代表的不是Binary，而是Balance）。通過B+樹索引能夠快速的定位要要查找的數據所在的數據頁，然后將頁讀入內存，在通過頁字典槽快速尋找到數據行。

InnoDB引擎中實現了B+樹結構的索引，其高度一般在2~3層，換句話說，查詢記錄的IO操作次數最多3次。InnoDB索引可以分為聚簇索引和非聚簇索引，這兩種分類的索引都是B+樹結構的。

聚簇索引（Clustered Index）

聚簇索引，又稱聚集索引，其是一種數據存儲的方式。在InnoDB存儲引擎中B+樹索引與數據是存儲在一起的，換句話說InnoDB存儲引擎的數據是由B+樹索引組織的。

建表

在進行索引講解前，我們先建立如下表：

-- ----------------------------
-- Table structure for index_test
-- ----------------------------
DROP TABLE IF EXISTS `index_test`;
CREATE TABLE `index_test` (
  `id` int NOT NULL AUTO_INCREMENT,
  `name` varchar(50) NOT NULL,
  `age` int NOT NULL,
  `profession` varchar(100) NOT NULL,
  `sex` char(1) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `index_name_profession` (`name`,`profession`)
) ENGINE=InnoDB AUTO_INCREMENT=8 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

-- ----------------------------
-- Records of index_test
-- ----------------------------
BEGIN;
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (1, 'Tom', 33, 'teacher', 'm');
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (2, 'Ryan', 25, 'programmer', 'm');
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (3, 'Li', 18, 'student', 'w');
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (4, 'Bob', 40, 'doctor', 'm');
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (5, 'Jim', 60, 'doctor', 'm');
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (6, 'Ben', 34, 'teacher', 'm');
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (7, 'Joy', 28, 'programmer', 'w');
COMMIT;

聚簇索引結構

數據行實際存儲在數據頁中，通過B+樹索引結構的葉子節(jié)點將數據頁組織起來。如下圖所示（若對B+樹結構不了解可以看我另外一篇文章《數據結構-B樹族》）：

聚簇索引結構

• B+樹的每一個葉子節(jié)點都是一個數據頁。
• B+樹的內部節(jié)點都是索引節(jié)點，鍵的左右指針指向的都是數據頁。
• 葉子節(jié)點間（數據頁）是通過指針（頁指針）相連的，是一個雙向鏈表結構。
• 葉子節(jié)點（數據頁）內部是數據行，數據行之間也是通過指針相連。
• 葉子節(jié)點（數據頁）與葉子節(jié)點內的數據行，都是按照主鍵順序排列的（注意：葉子節(jié)點之間與行之間都不是物理連續(xù)的，而都是鏈表結構）。

主鍵選擇原則

使用B+樹作為數據存儲的結構我們需要讓主鍵（鍵值）滿足以下特性：

鍵值長度盡量?。烘I值是會占用空間的，我們希望的是其越小越好。

鍵值盡量單調遞增：B+樹的插入可能會引起節(jié)點的分裂，如果不是單調遞增，我們可能會插入到頁中間位置，這就可能導致數據的分裂以及數據的挪動，嚴重的影響插入性能。

非聚簇索引（Secondary Index）

非聚簇索引，也稱非聚集索引、二級索引、輔助索引等。在InnoDB中，非聚簇索引的頁節(jié)點除了包含鍵之外，還包含一個bookmark，也就是一個可以找到該鍵對應的數據行所在位置。結合我們上面講到的，這里的書簽值就對應的是聚簇索引的鍵。

輔助索引與聚簇索引關系

單列索引

單列索引，即一個索引樹中只包含一個列的值，一張表可以建立多個單列索引，如果一個查詢語句中包含了單列索引列，優(yōu)化器可能只會選擇一個最優(yōu)的單列索引，具體遵循如下原則：

• 如果查詢條件是AND連接，且用到的所有（或部分）列都建立了索引，則優(yōu)化器會按照最優(yōu)策略，可能會命中一個或多個索引。
• 如果查詢條件是OR連接，且用到的所有列都建立了索引，則所有索引都會命中。
• 如果查詢條件是OR連接，且用到的只有部分列建立了索引，則執(zhí)行全表掃表。

1、2兩條原則涉及到了一個index_merge策略，這是一個多索引合并優(yōu)化策略，這個概念我們下面會講。

單列索引

索引合并

合并索引是在MySQL 5.7的InnoDB引擎引入的一個策略，我們稱之為index_merge，如果使用到了這種策略，執(zhí)行計劃會返回type：index_merge，它具有有以下的特性：

• 它會將幾個索引的范圍掃描結果合并成（AND取交集、OR取并集）一個。
• 該策略只適用于單表操作，多表查詢失效。
• 如果存在某個OR條件沒有建立單列索引，則失效。
• 如果所有條件對應的列都是索引，則AND和OR組合使用也會命中該類型索引。
• 執(zhí)行如下語句我們可以看到type為index_merge，Extra為sort_union。

EXPLAIN SELECT * FROM index_test WHERE name='Tom' OR professinotallow='teacher';

執(zhí)行結果

組合索引

在沒有建立組合索引的情況下，可通過多個單列索引UNION操作快速得到結果。接下來我們介紹一下組合索引，先見下圖：

組合索引

對于組合索引來說，所有參與索引的列都會出現在索引樹上。如上圖，是一個index_profession_name組合索引，存儲引擎首先會根據profession列值順序建立第一個索引列，緊接在第一個列的基礎上建立第二個索引列。

組合索引有以下特性：

• 查詢遵循最左原則，查詢條件必須包含第一個索引列，即profession、profession&name、profession&sex等組合；
• 如果查詢條件包含了第一個索引列，則查詢條件的書寫順序沒有要求，即name&profession、age&profession等寫法都可以，優(yōu)化器會處理順序;
• OR查詢會讓組合索引失效；

回表查詢

組合索引的查詢可能涉及到回表查詢操作，什么是回表查詢呢？

當SELECT的列中包含了非索引列時，我們需要通過聚簇索引來補齊數據，這個就叫回表查詢。

我們來舉個例子：

SELECT profession,name,age,sex FROM index_test WHERE profession = 'xxx';

此時的age、sex列不在索引index_profession_name中，則需要通過查詢index_test的聚簇索引補齊age、sex列信息。

如果我們SELECT的列都是索引列呢？是否就不需要回表查詢了，這個有涉及另一個概念即索引覆蓋。

索引覆蓋

從上面的一個例子我們很容易得出，索引覆蓋就是：

當SELECT的列中包含都是索引列時，我們通過該非聚簇索引就能拿到所有數據，這就叫做索引覆蓋。

如下圖是索引覆蓋時的執(zhí)行計劃的內容，我們可以看到Extra為Usering index。

索引覆蓋

索引下推

關于索引下推從字面上不太好理解（這個詞很唬人，但是我們了解了其邏輯后，你會發(fā)現極其簡單，論起名的重要性），我們先看下面這張圖：

SELECT * FROM index_test WHERE name like 'J%' AND profession = 'programmer' AND sex = 'm';

索引下推

在MySQL5.6以前，只要第一個索引列滿足查詢條件，就會回表查詢，如上圖有3次回表查詢。

在MySQL5.6之后，通過索引下推，會依次匹配多個索引列，過濾掉不符合的，從而減少回表次數，如上圖不等于programmer直接跳過了，減少了1次回表操作。

索引下推可以有效減少回表次數，從而提升查詢效率（也就是多個if判斷，搞個名詞唬人）。

索引的選擇性

索引的選擇性，就是指該索引的建立是否有必要性，因為并不是所有查詢條件中出現的列都需要添加索引。比如性別（男、女），整張表除了男就是女，浪費索引存儲空間且起不到任何提升查詢速度的作用。

索引的選擇性有一個非常重要的指標，即Cardinality（基數），即該索引所統(tǒng)計的不重復記錄數，如果其越接近于聚簇索引，那么其利用率及效率越高，如下圖所示：

索引的選擇性

索引的選擇性公式為：索引的選擇性 = 不重復的索引值數 / 數據表的記錄總數。

聚簇索引選擇性為1，也就是說如果一個索引的選擇性約接近1，其查詢效率越高，但是索引所占用的空間越大。

索引失效

• OR 前后查詢條件不都是索引字段。
• 未遵循最左N個字段。
• 模糊查詢 LIKE 以 % 開頭。
• 需要類型轉換。
• WHERE 中索引列有計算。
• WHERE 中索引列用到了函數。
• 索引字段上使用 NOT、<> 、!= 。
• 當全表掃描速度比索引速度快時。

前綴索引

我們先來看如下兩個索引：

ALTER TABLE index_test ADD INDEX index_name(name);

ALTER TABLE index_test ADD INDEX index_name_pre(name(1));

上面兩個索引的唯一不同點就是，index_name_pre索引是一個name的前綴索引，前綴的長度為1，也就是說index_name_pre只包含name字段的第一個字符。

我們分別執(zhí)行下面的語句，看一下兩個索引的使用情況：

EXPLAIN SELECT * FROM index_test WHERE name like 'Ben';

• index_name_pre索引

index_name_pre索引

• index_name索引

index_name索引

從兩條執(zhí)行計劃可以看出，若在index_name_pre索引下查詢會掃描2行記錄，而index_name索引下只需要掃描1行記錄。那是不是前綴索引就沒有存在的意義了呢？然而并不是，我們接著看。

前綴索引的選擇原則

• 列值很長且需要建立索引：如果我們?yōu)楸韎ndex_test表建立了一個新列：address varchar(500)，該列是一個存儲用戶的地址列，其實際長度可能有幾百個字符。如果我們?yōu)槠浣⒁粋€完整索引，其所占用的索引空間將是巨大的，這時我們可以為其建立一個前綴索引。
• 前綴索引需要列的一部分前綴作為索引，這個“一部分”的計算依據是根據索引的選擇性來決定的。

我們希望的是：前綴n的選擇性無限趨近于全列的選擇性，但n的值需要盡量?。ü?jié)省空間），計算步驟如下：

column_name的全列選擇性計算方式：

• SELECT COUNT(DISTINCT column_name) / COUNT(*) FROM table_name;

column_name的前綴n的選擇性計算方式：

• SELECT COUNT(DISTINCT LEFT(column_name, n)) / COUNT(*) FROM table_name;

通過調整n的大小，得到一個接近全列選擇性的n值，同時又能保證前綴足夠小。

Hash索引

MySQL的Memory引擎支持Hash索引，但我們今天講的不是該引擎，而是InnoDB的存儲引擎的哈希索引。我這里說的哈希索引，嚴格意義上說應該叫自適應哈希索引（Adaptive Hash Index，AHI）。

自適應哈希索引是不能用戶手動創(chuàng)建的，它是由引擎根據當前視圖的數據訪問頻次在緩沖池建立一個哈希索引。通過訪問頻次建立，換句話說就是為高頻熱點數據建立索引。

結構

哈希索引是通過哈希表來實現的，Key是利用查詢條件中的鍵通過哈希函數計（CRC32算）算得到，Value則是直接指向數據頁中的值。

自適應哈希索引結構

如上圖通過Hash索引可以做到O(1)的時間復雜度查詢，而利用輔助索引則需要N次（與樹的高度有關）。

自適應的觸發(fā)條件

• 使用相同的條件訪問了同一個索引17次；

例如表index_test表有index_profession_name組合索引，如果我們使用以下任意語句訪問（不能是交替訪問）可創(chuàng)建自適應索引：

SELECT * FROM index_test WHERE profession = 'programmer';

SELECT * FROM index_test WHERE profession = 'programmer' AND name = 'Tom';

如果以同一查詢條件進行了100次以上的訪問；

數據頁被相同查詢語句訪問了N次（N = 頁記錄數 * 1/16）;

缺點

• 自適應哈希索引的維護勢必會用到鎖來控制并發(fā)，那么該鎖可能導致性能損耗。
• 自適應哈希索引在DML操作下引發(fā)的數據變化時處理效率成本高。
• 自適應哈希索引的條件很苛刻，需要相同的查詢條件連續(xù)訪問，且只適用于等值搜索條件，order by、模糊查詢等都不行。
• 其本身會可能會占用大量的內存池空間，從而加重引擎的負擔，需要做好參數調節(jié)。

總結

• InnoDB存儲引擎的索引共有以下幾種：B+樹索引、哈希索引、全文索引，本文主要介紹了前兩種。
• InnoDB存儲引擎的數據是由B+樹索引組織的，換句話說：聚簇索引即使索引又存儲完整記錄數據。
• 可以利用多個單列索引的索引合并來實現組合索引的效果，但是不推薦這么做。
• 在設計組合索引時需要注意索引的選擇性，約趨近于1的索引會越高效，但是索引存儲空間也會變大。
• 可以利用覆蓋索引來快速的查詢，覆蓋索引不用回表查詢，非常高效。
• 當遇到非常大的列需要建立索引時可以考慮使用前綴索引，但要注意前綴的長度選擇，可通過索引的選擇性公式計算。
• 索引下推可以有效減少組合索引的回表次數，提示查詢效率。
• 自適應哈希索引的條件非常的苛刻，因此要設法利用它來提升查詢效率。