MySQL學(xué)習(xí)（七）：Innodb存儲引擎索引的實現(xiàn)原理詳解

概述

在數(shù)據(jù)庫當(dāng)中，索引就跟樹的目錄一樣用來加快數(shù)據(jù)的查找速度，對于一個SQL查詢操作，根據(jù)索引快速過濾掉不符合要求的數(shù)據(jù)并定位到符合要求的數(shù)據(jù)，從而不需要掃描整個表來獲取所需的數(shù)據(jù)。

在innodb存儲引擎中，主要是基于B+樹來實現(xiàn)索引，在非葉子節(jié)點存放索引關(guān)鍵字，在葉子節(jié)點存放數(shù)據(jù)記錄或者主鍵索引（或者說是聚簇索引）中的主鍵值，所有的數(shù)據(jù)記錄都在同一層，葉子節(jié)點，即數(shù)據(jù)記錄直接之間通過指針相連，構(gòu)成一個雙向鏈表，從而可以方便地遍歷到所有的或者某一范圍的數(shù)據(jù)記錄。

B樹，B+樹

B樹和B+樹都是多路平衡搜索樹，通過在每個節(jié)點存放更多的關(guān)鍵字和通過旋轉(zhuǎn)、分裂操作來保持樹的平衡來降低樹的高度，從而減少數(shù)據(jù)檢索的磁盤訪問量。

B+樹相對于B樹的一個主要的不同點是B+的葉子節(jié)點通過指針前后相連，具體為通過雙向鏈表來前后相連，所以非常適合執(zhí)行范圍查找。具體可以參考：

數(shù)據(jù)結(jié)構(gòu)-樹（三）：多路搜索樹B樹、B+樹

innodb存儲引擎的聚簇和非聚簇索引都是基于B+樹實現(xiàn)的。
主鍵索引

innodb存儲引擎使用主鍵索引作為表的聚簇索引，聚簇索引的特點是非葉子節(jié)點存放主鍵作為查找關(guān)鍵字，葉子節(jié)點存放實際的數(shù)據(jù)記錄本身（也稱為數(shù)據(jù)頁），從左到右以關(guān)鍵字的順序，存放數(shù)據(jù)記錄，故聚簇索引其實就是數(shù)據(jù)存放的方式，所以每個表只能存在一個聚簇索引，innodb存儲引擎的數(shù)據(jù)表也稱為索引組織表。結(jié)構(gòu)如下：（圖片引自《MySQL技術(shù)內(nèi)幕：Innodb存儲引擎》）

在查詢當(dāng)中，如果是通過主鍵來查找數(shù)據(jù)，即使用explain分析SQL的key顯示PRIMARY時，查找效率是最高的，因為葉子節(jié)點存放的就是數(shù)據(jù)記錄本身，所有可以直接返回，而不需要像非聚簇索引一樣需要通過額外回表查詢（在主鍵索引中）獲取數(shù)據(jù)記錄。

其次是對于ORDER BY排序操作，不管是正序ASC還是逆序DESC，如果ORDER BY的列是主鍵，則由于主鍵索引對應(yīng)的B+樹本身是有序的， 故存儲引擎返回的數(shù)據(jù)就是已經(jīng)根據(jù)主鍵有序的，不需要在MySQL服務(wù)器層再進行排序，提高了性能，如果通過explain分析SQL時，extra顯示Using filesort，則說明需要在MySQL服務(wù)器層進行排序，此時可能需要使用臨時表或者外部文件排序，這種情況一般需要想辦法優(yōu)化。

對于基于主鍵的范圍查找，由于聚簇索引的葉子節(jié)點已經(jīng)根據(jù)主鍵的順序，使用雙向鏈表進行了相連，故可以快速找到某一范圍的數(shù)據(jù)記錄。

輔助索引

輔助索引也稱為二級索引，是一種非聚簇索引，一般是為了提高某些查詢的效率而設(shè)計的，即使用該索引列查詢時，通過輔助索引來避免全表掃描。由于輔助索引不是聚簇索引，每個表可以存在多個輔助索引，結(jié)構(gòu)如下：

輔助索引的非葉子節(jié)存放索引列的關(guān)鍵字，葉子節(jié)點存放對應(yīng)聚簇索引（或者說是主鍵索引）的主鍵值。即通過輔助索引定位到需要的數(shù)據(jù)后，如果不能通過索引覆蓋所需列，即通過該輔助索引列來獲取該次查詢所需的所有數(shù)據(jù)列，則需要通過該對應(yīng)聚簇索引的主鍵值定位到在聚簇索引中的主鍵，然后再通過該主鍵值在聚簇索引中找到對應(yīng)的葉子頁，從而獲取到對應(yīng)的數(shù)據(jù)記錄，所以整個過程涉及到先在輔助索引中查找，再在聚簇索引（即主鍵索引）中查找（回表查詢）兩個過程。

舉個例子：

1. 輔助索引對應(yīng)的B+樹的高度為3，則需要3次磁盤IO來定位到葉子節(jié)點，其中葉子節(jié)點包含對應(yīng)聚簇索引的某個主鍵值；
2. 然后通過葉子節(jié)點的對應(yīng)聚簇索引的主鍵值，在聚簇索引中找到對應(yīng)的數(shù)據(jù)記錄，即如果聚簇索引對應(yīng)的B+樹高度也是3，則也需要3次磁盤IO來定位到聚簇索引的葉子頁，從而在該葉子頁中獲取實際的數(shù)據(jù)記錄。

以上過程總共需要進行6次磁盤IO。故如果需要回表查詢的數(shù)據(jù)行較多，則所需的磁盤IO將會成倍增加，查詢性能會下降。所以需要在過濾程度高，即重復(fù)數(shù)據(jù)少的列來建立輔助索引。

Cardinality：索引列的數(shù)據(jù)重復(fù)度

由以上分析可知，通過輔助索引進行查詢時，如果需要回表查詢并且查詢的數(shù)據(jù)行較多時，需要大量的磁盤IO來獲取數(shù)據(jù)，故這種索引不但沒有提供查詢性能，反而會降低查詢性能，并且MySQL優(yōu)化器在需要返回較多數(shù)據(jù)行時，也會放棄使用該索引，直接進行全表掃描。所以輔助索引所選擇的列需要是重復(fù)度低的列，即一般查詢后只需要返回一兩行數(shù)據(jù)。如果該列存在太多的重復(fù)值，則需要考慮放棄在該列建立輔助索引。

具體可以通過：SHOW INDEX FROM 數(shù)據(jù)表，的Cardinality的值來判斷：

mysql> SHOW INDEX FROM store_order;
+---------------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table   | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+---------------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| store_order |   0 | PRIMARY |   1 | store_id | A   |   201 |  NULL | NULL |  | BTREE  |   |    |
| store_order |   1 | idx_expire |   1 | expire_date | A   |   68 |  NULL | NULL | YES | BTREE  |   |    |
| store_order |   1 | idx_ul  |   1 | ul   | A   |   22 |  NULL | NULL | YES | BTREE  |   |    |
+---------------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
3 rows in set (0.01 sec)

Cardinality表示索引列的唯一值的估計數(shù)量，如果跟數(shù)據(jù)行的數(shù)量接近，則說明該列存在的重復(fù)值少，列的過濾性較好；如果相差太大，即Cardinality / 數(shù)據(jù)行總數(shù)，的值太小，如性別列只包含“男”，“女”兩個值，則說明該列存在大量重復(fù)值，需要考慮是否刪除該索引。

覆蓋索引

1. 由于回表查詢開銷較大，故為了減少回表查詢的次數(shù)，可以在輔助索引中增加查詢所需要的所有列，如使用聯(lián)合索引，這樣可以從輔助索引中獲取查詢所需的所有數(shù)據(jù)（由于輔助索引的葉子頁包含主鍵值，即使索引沒有該主鍵值，如果只需返回主鍵值和索引列，則也會使用覆蓋索引），不需要回表查詢完整的數(shù)據(jù)行，從而提高性能，這種機制稱為覆蓋索引。
2. 當(dāng)使用explain分析查詢SQL時，如果extra顯示 using index 則說明使用了覆蓋索引返回數(shù)據(jù)，該查詢性能較高。
3. 由于索引的存在會增加更新數(shù)據(jù)的開銷，即更新數(shù)據(jù)時，如增加和刪除數(shù)據(jù)行，需要通過更新對應(yīng)的輔助索引，故在具體設(shè)計時，需要在兩者之間取個折中。

聯(lián)合索引與最左前戳匹配

1. 聯(lián)合索引是使用多個列作為索引，如（a,b,c)，表示使用a，b，c三個列來作為索引，由B+樹的特征可知，索引都是需要符合最左前戳匹配的，故其實相當(dāng)于建立a，（a,b），(a,b,c)三個索引。
2. 所以在設(shè)計聯(lián)合索引時，除了需要考慮是否可以優(yōu)化為覆蓋索引外，還需要考慮多個列的順序，一般的經(jīng)驗是：查詢頻率最高，過濾性最好（重復(fù)值較少)的列在前，即左邊。

聯(lián)合索引優(yōu)化排序order by

除此之外，可以考慮通過聯(lián)合索引來減少MySQL服務(wù)端層的排序，如用戶訂單表包含聯(lián)合索引(user_id, buy_date)，單列索引(user_id)：（注意這里只是為了演示聯(lián)合索引，實際項目，只需聯(lián)合索引即可，如上所述，(a,b)，相當(dāng)于a, (a,b)兩個索引）：

KEY `idx_user_id` (`user_id`),
KEY `idx_user_id_buy_date` (`user_id`,`buy_date`)

如果只是普通的查詢某個用戶的訂單，則innodb會使用user_id索引，如下：

mysql> explain select user_id, order_id from t_order where user_id = 1;
+----+-------------+---------+------------+------+----------------------------------+-------------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys     | key   | key_len | ref | rows | filtered | Extra  |
+----+-------------+---------+------------+------+----------------------------------+-------------+---------+-------+------+----------+-------------+
| 1 | SIMPLE  | t_order | NULL  | ref | idx_user_id,idx_user_id_buy_date | idx_user_id | 4  | const | 4 | 100.00 | Using index |
+----+-------------+---------+------------+------+----------------------------------+-------------+---------+-------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

但是當(dāng)需要基于購買日期buy_date來排序并取出該用戶最近3天的購買記錄時，則單列索引user_id和聯(lián)合索引（user_id, buy_date）都可以使用，innodb會選擇使用聯(lián)合索引，因為在該聯(lián)合索引中buy_date已經(jīng)有序了，故不需要再在MySQL服務(wù)器層進行一次排序，從而提高了性能，如下：

mysql> explain select user_id, order_id from t_order where user_id = 1 order by buy_date limit 3;
+----+-------------+---------+------------+------+----------------------------------+----------------------+---------+-------+------+----------+--------------------------+
| id | select_type | table | partitions | type | possible_keys     | key     | key_len | ref | rows | filtered | Extra     |
+----+-------------+---------+------------+------+----------------------------------+----------------------+---------+-------+------+----------+--------------------------+
| 1 | SIMPLE  | t_order | NULL  | ref | idx_user_id,idx_user_id_buy_date | idx_user_id_buy_date | 4  | const | 4 | 100.00 | Using where; Using index |
+----+-------------+---------+------------+------+----------------------------------+----------------------+---------+-------+------+----------+--------------------------+
1 row in set, 1 warning (0.01 sec)

如果刪除idx_user_id_buy_date這個聯(lián)合索引，則顯示Using filesort：

mysql> alter table t_order drop index idx_user_id_buy_date;
Query OK, 0 rows affected (0.02 sec)
Records: 0 Duplicates: 0 Warnings: 0

mysql> explain select user_id, order_id from t_order where user_id = 1 order by buy_date limit 3;
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra      |
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| 1 | SIMPLE  | t_order | NULL  | ALL | idx_user_id | NULL | NULL | NULL | 4 | 100.00 | Using where; Using filesort |
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
1 row in set, 1 warning (0.00 sec)

以上所述是小編給大家介紹的Innodb存儲引擎索引的實現(xiàn)詳解整合，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！