什么是索引

索引又可以稱為鍵(key)是存儲(chǔ)引擎用于快速找到記錄的一種數(shù)據(jù)結(jié)構(gòu)。

索引是提高M(jìn)ySQL查詢性能最有效的手段，我們常說的MySQL性能調(diào)優(yōu)基本都是對索引的優(yōu)化。所以這是每個(gè)開發(fā)需要掌握并會(huì)應(yīng)用的知識點(diǎn)。

索引是一種數(shù)據(jù)結(jié)構(gòu)，它也是存儲(chǔ)在磁盤的一個(gè)文件。上一篇我們學(xué)習(xí)MySQL的邏輯架構(gòu)的時(shí)候了解了InnoDB和MyISM存儲(chǔ)引擎，InnoDB存儲(chǔ)引擎索引和數(shù)據(jù)是同一個(gè)文件，MyISAM索引和數(shù)據(jù)是兩個(gè)獨(dú)立的文件。

在MySQL中，索引是在存儲(chǔ)引擎層實(shí)現(xiàn)的而不是Server層實(shí)現(xiàn)的，所以不同的存儲(chǔ)引擎的索引的工作方式是不一樣的。我們對索引的分析應(yīng)該是建立在存儲(chǔ)引擎的基礎(chǔ)上的，InnoDB是MySQL默認(rèn)的存儲(chǔ)引擎。

索引的優(yōu)點(diǎn)：

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

索引的缺點(diǎn)：

• 索引是數(shù)據(jù)結(jié)構(gòu)，它占用了額外的磁盤空間。
• 當(dāng)表數(shù)據(jù)量比較大時(shí)，維護(hù)索引的代價(jià)比較大。

索引數(shù)據(jù)模型

每個(gè)存儲(chǔ)引擎的數(shù)據(jù)結(jié)構(gòu)和算法都是存在區(qū)別，我們先看下MySQL本身支持的索引類型。

B-Tree索引

一般我們說的索引結(jié)構(gòu)就是指B-Tree索引，MySQL大部分的存儲(chǔ)引擎都支持這種索引，但是不同的存儲(chǔ)引擎以不同的方式使用B-Tree索引，性能也各有不同。InnoDB使用的是B+Tree，按照原有的數(shù)據(jù)格式進(jìn)行存儲(chǔ)，根據(jù)主鍵引用被索引的行。

B-Tree所有的值都是按順序存儲(chǔ)的，并且每一個(gè)葉子到根的距離相同。下圖是B-Tree的抽象圖：

B-Tree能夠加快訪問數(shù)據(jù)的速度。

存儲(chǔ)引擎不需要全表掃描來獲取所需要的數(shù)據(jù)，它是從索引的根節(jié)點(diǎn)開始搜索。根節(jié)點(diǎn)的槽中存放指向子節(jié)點(diǎn)的指針，搜索引擎根據(jù)這些指針向下層查找。通過比較節(jié)點(diǎn)頁的值和要查找的值可以找到合適的指針進(jìn)入到下層節(jié)點(diǎn)。最終引擎要么找到對應(yīng)的值，要么該記錄不存在。

B-Tree的索引如果多個(gè)列，索引值的排序是按照建表時(shí)定義的索引順序，所以索引的順序是比較重要的。

B-Tree是N叉樹，N的大小取決于數(shù)據(jù)塊的大小。

以InnoDB的一個(gè)整數(shù)字段索引為例，N大概為1200，當(dāng)樹高是4的時(shí)候，就可以存1200的3次方的數(shù)據(jù)，大概為17億。一個(gè)擁有10億的表上一個(gè)整數(shù)字段的索引，查找一個(gè)值最多訪問3次磁盤。其實(shí)在應(yīng)用時(shí)，如果第二層被提前加載到內(nèi)存中，那么磁盤的訪問次數(shù)就更少了。

哈希索引

哈希索引是基于哈希表實(shí)現(xiàn)的，只有精確匹配所有列的查詢才有效。

對于每一行數(shù)據(jù)，存儲(chǔ)引擎都會(huì)對所有的索引列計(jì)算一個(gè)哈希碼(hash code)，哈希碼是一個(gè)比較小的值，并且不同鍵值的行計(jì)算出來的哈希碼也不一樣。哈希索引將所有的哈希碼存儲(chǔ)在索引中，同時(shí)在hash表中保存指向每個(gè)數(shù)據(jù)行的指針。

創(chuàng)建表test_hash，它的存儲(chǔ)引擎為memory，索引為full_name，索引類型為hash。

CREATE TABLE `test_hash` ( 
  `full_name` varchar(255) DEFAULT NULL, 
  `short_name` varchar(32) DEFAULT NULL, 
  `age` int(11) DEFAULT NULL, 
  KEY `idx` (`full_name`) USING HASH 
) ENGINE=MEMORY DEFAULT CHARSET=utf8; 

 表中的數(shù)據(jù)如下：

mysql> select * from test_hash; 
+-------------------+------------+------+ 
| full_name         | short_name | age  | 
+-------------------+------------+------+ 
| Dwayne Johnson    | Johnson    | NULL | 
| Taylor Swift      | Taylor     | NULL | 
| Leonardo DiCaprio | Leonardo   | NULL | 
| Vin Diesel        | Diesel     | NULL | 
| Kobe Bryant       | Kobe       | NULL | 
+-------------------+------------+------+ 
5 rows in set (0.00 sec) 

 那么哈希索引的數(shù)據(jù)結(jié)構(gòu)可能是：

 當(dāng)我們執(zhí)行查詢語句：

mysql> select short_name from test_hash where full_name = 'Dwayne Johnson'; 

這個(gè)sql語句的執(zhí)行流程：

1)根據(jù)where條件 'Dwayne Johnson'計(jì)算出哈希碼，那么得到的哈希碼為1234。

2)MySQL在索引中查找到1234，并根據(jù)這個(gè)值找到了對應(yīng)的行記錄指針。

3)根據(jù)指針地址找到對應(yīng)的行，最后比較這個(gè)行中的full_name列是否為'Dwayne Johnson'。

那現(xiàn)在有個(gè)問題，哈希碼沖突的時(shí)候怎么辦呢?學(xué)過HashMap的小伙伴此時(shí)肯定靈機(jī)一動(dòng)：哈希碼沖突的時(shí)候使用鏈表。對的，當(dāng)鍵值的哈希碼沖突的時(shí)候，MySQL也是使用的鏈表結(jié)構(gòu)。如果是鏈表結(jié)構(gòu)，在查找的時(shí)候就需要遍歷每個(gè)鏈表指針指向的行記錄做匹配，所以哈希沖突比較大的時(shí)候查找的效率是比較低的。

從上面的示例我們可以看出，哈希索引的結(jié)構(gòu)中只存儲(chǔ)了哈希值，它的結(jié)構(gòu)是比較緊湊的，對于精確查詢的效率是比較快的。

但是哈希索引還是有些限制的：

• 哈希索引中存儲(chǔ)的是鍵值的哈希值，它不是按照索引列的順序的，所以它不無法用于排序。
• 哈希索引不支持部分索引匹配查找，因?yàn)楣Ｋ饕冀K是索引列的全部內(nèi)容。如果我們索引有兩個(gè)列(A，B)，查詢的時(shí)候只想使用A列，這個(gè)時(shí)候是無法應(yīng)用索引的。
• 哈希索引只支持等值查詢，比如=、in等，它不支持任何范圍查詢。
• 當(dāng)哈希沖突的時(shí)候，存儲(chǔ)引擎必須要遍歷鏈表中的所有行指針，逐行比較，直到找到所有符合條件的行，如果哈希沖突比較多的時(shí)候，索引維護(hù)的代價(jià)比較高。

在MySQL中，目前只有memory引擎顯式支持哈希索引。

InnoDB索引模型

我們前面提到，InnoDB的索引結(jié)構(gòu)是B+Tee，它是以主鍵引用被索引的行。所以在InnoDB中，表都是根據(jù)主鍵順序以索引的形式存放的，每一個(gè)索引在InnoDB里面對應(yīng)一棵B+樹。

B+Tree索引

B+Tree是我們前面提到的B-Tree的擴(kuò)展，B-Tree的每一個(gè)節(jié)點(diǎn)都包含了數(shù)據(jù)項(xiàng)，這樣每一塊磁盤存儲(chǔ)的索引值就會(huì)比較少，樹的高度就會(huì)變大，查詢的磁盤I/O次數(shù)就會(huì)增加。

那B+Tree是怎么樣的數(shù)據(jù)結(jié)構(gòu)呢?下圖是B+Tree的抽象圖：

B+Tree與B-Tree的區(qū)別：

• B+Tree的非葉子節(jié)點(diǎn)不保存數(shù)據(jù)信息，只保存索引值和指向下一層節(jié)點(diǎn)的指針。
• B+Tree的葉子節(jié)點(diǎn)保存了數(shù)據(jù)
• B+Tree的葉子節(jié)點(diǎn)是順序排列的，并且葉子相鄰節(jié)點(diǎn)之間有指針的互相引用

B+Tree能夠更好地配合磁盤的讀寫特性，減少單次查詢的磁盤訪問次數(shù)。

InnoDB的索引類型分為主鍵索引和非主鍵索引。

主鍵索引和非主鍵索引

創(chuàng)建表user，它的存儲(chǔ)引擎為InnoDB，id為主鍵，name為普通索引。

CREATE TABLE `user` ( 
  `id` int(10) NOT NULL, 
  `name` varchar(32) DEFAULT NULL, 
  `age` int(3) DEFAULT NULL, 
  `sex` varchar(1) DEFAULT NULL, 
  `comment` varchar(255) DEFAULT NULL, 
  `date` date DEFAULT NULL, 
  PRIMARY KEY (`id`), 
  KEY `idx` (`name`) USING BTREE 
) ENGINE=InnoDB DEFAULT CHARSET=utf8; 

 表中的數(shù)據(jù)如下: 

mysql> select * from user; 
+----+-------+------+------+---------+------------+ 
| id | name  | age  | sex  | comment | date       | 
+----+-------+------+------+---------+------------+ 
|  1 | Alen  |   20 | 1    | NULL    | 2021-02-16 | 
|  2 | Alex  |   21 | 1    | NULL    | 2021-02-16 | 
|  3 | Saria |   16 | 0    | NULL    | 2021-02-16 | 
|  4 | Semyt |   18 | 0    | NULL    | 2021-02-16 | 
|  5 | Summy |   17 | 1    | NULL    | 2021-02-16 | 
|  6 | Tom   |   19 | 0    | NULL    | 2021-02-16 | 
+----+-------+------+------+---------+------------+ 
6 rows in set (0.00 sec) 

 主鍵索引也稱為聚簇索引，它的葉子節(jié)點(diǎn)都包含了主鍵值、事務(wù)ID、用于事務(wù)和MVCC的回滾指針以及所有剩余的列。

mysql> select * from user where id = 1; 

主鍵索引只需要搜索ID這棵B+Tree就可以拿到符合條件的行記錄。

InnoDB是通過主鍵索引聚集數(shù)據(jù)，如果表中沒有定義主鍵，InnoDB會(huì)選擇一個(gè)唯一的非空索引代替。如果沒有這樣的索引，InnoDB會(huì)隱式定義一個(gè)主鍵來作為聚簇索引。這也是勾勾為每個(gè)表都創(chuàng)建主鍵的原因。

聚簇索引的優(yōu)點(diǎn)：

• 把相關(guān)的數(shù)據(jù)保存在一起，減少了磁盤I/O;
• 聚簇索引將數(shù)據(jù)和索引保存在同一顆BTree上，數(shù)據(jù)訪問更快;

聚簇索引的缺點(diǎn)：

• 如果數(shù)據(jù)都在內(nèi)存中，聚簇索引的查詢性能就沒有那么好的優(yōu)勢了。
• 插入的速度嚴(yán)重依賴于插入順序。盡量保證主鍵索引是有序的。
• 更新聚簇索引列的代價(jià)更高。
• 在插入行或者更新主鍵的時(shí)候?qū)е滦枰苿?dòng)行的時(shí)候可能導(dǎo)致頁分裂的問題。當(dāng)插入到一個(gè)已滿的頁中，存儲(chǔ)引擎會(huì)將該頁分裂為兩頁來容納數(shù)據(jù)，頁分裂會(huì)導(dǎo)致占用更多的磁盤空間。

非主鍵索引也稱為非聚簇索引，在InnoDB中又被稱為二級索引。非主鍵索引的葉子節(jié)點(diǎn)內(nèi)容是主鍵的值。

mysql> select * from user where name = 'Alen'; 

非主鍵索引查詢時(shí)，首先根據(jù)name普通查詢搜索name索引樹，找到id為1，再根據(jù)id=1到ID索引樹查詢一次才能獲取到符合條件的行記錄。

我們把先搜索普通索引樹得到主鍵，再搜索主鍵索引樹的過程稱為回表。

普通索引的查詢比主鍵索引多檢索了一棵B+Tree，在實(shí)際應(yīng)用場景下如果能用到主鍵索引盡量選擇主鍵索引。

在創(chuàng)建索引的時(shí)候還有其他的原則，我們接下來繼續(xù)學(xué)習(xí)高性能的索引策略。

索引策略

小伙伴們在學(xué)習(xí)索引策略的時(shí)候可以利用上一篇文章的explian關(guān)鍵字查詢執(zhí)行計(jì)劃。

索引的選擇

索引的分類有多種，我們可以按照索引字段的個(gè)數(shù)將索引分為單列索引和聯(lián)合索引。

單列索引：一個(gè)索引只包含一個(gè)列，一個(gè)表中可以多個(gè)單列索引。

聯(lián)合索引：一個(gè)索引包含多個(gè)列。

我們還可以將索引分為普通索引、唯一索引和主鍵索引。

普通索引：基本的索引類型，常用來提高查詢效率，對數(shù)據(jù)沒有限制。允許在索引列中插入空值和重復(fù)值。

唯一索引：索引列中的值必須是唯一的，允許存在空值。

主鍵索引：不允許空值的特殊的唯一索引。

索引有這么多分類，我們在創(chuàng)建索引的時(shí)候如何選擇呢?

索引的三星系統(tǒng)：

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

正確的創(chuàng)建和使用索引是實(shí)現(xiàn)高性能查詢的基礎(chǔ)。索引的選擇沒有絕對的要求，主要是根據(jù)自己的業(yè)務(wù)需求，但是有些原則我們在創(chuàng)建索引的時(shí)候可以作為參考。

• 索引列的區(qū)分度越高則查詢效率越高。
• 將頻繁搜索的列加入索引，可以提高搜索效率。
• 索引不只提高了查詢效率，也可以參與排序和分組，經(jīng)常用來排序和分組的字段也需考慮加入索引。
• 創(chuàng)建索引時(shí)，應(yīng)將區(qū)分度高的字段排在前面。即需要注意索引字段的順序。
• 索引列不能參與任何運(yùn)算。
• 避免創(chuàng)建重復(fù)索引，即在同一個(gè)列上按照相同的順序創(chuàng)建相同類型的索引。
• 對于從未使用的索引，應(yīng)盡量刪除。
• 對于blob、text或者長varchar類型的列，必須要使用前綴索引，取最夠長的前綴來保證較高的區(qū)分度。
• 普通索引和唯一索引在查詢效率上差別并不大，因?yàn)橐媸前凑枕撟x取數(shù)據(jù)。對于唯一索引在查詢的時(shí)候只要找到就不再繼續(xù)比較了，因?yàn)樗饕呀?jīng)保證了唯一性。而對于普通索引則在找到滿足條件的記錄后還需要繼續(xù)查找直到找到不滿足條件的第一條記錄，但是對于按照頁讀取數(shù)據(jù)的引擎來說，多一次的判斷對性能的影響較小。普通索引和唯一索引的選擇除了保證業(yè)務(wù)的準(zhǔn)確性之外，其他更多的考慮更新數(shù)據(jù)時(shí)對性能的影響。

獨(dú)立的列

”獨(dú)立的列“是指索引不能是表達(dá)式的一部分，也不能是函數(shù)的參數(shù)。

例如，如下sql語句，在查詢時(shí)索引字段name參與了函數(shù)運(yùn)算，會(huì)導(dǎo)致索引失效，全表掃描。

mysql> select * from user where CONCAT(name,'n') = 'Alen'; 

添加索引age字段，如果我們在查詢的時(shí)候?qū)ge字段進(jìn)行了運(yùn)算也會(huì)導(dǎo)致索引失效：

mysql> select * from user where age + 1 = 21; 

我們平時(shí)開發(fā)中要養(yǎng)成簡化where條件的習(xí)慣，始終使用單獨(dú)的索引列。

覆蓋索引

如果我們把按照普通索引查詢的sql語句修改如下:

mysql> select name from user where name like 'Al%'; 

這時(shí)只需要查詢普通索引樹即可得到要查詢的列，因?yàn)橐樵兊牧幸呀?jīng)在索引樹了，而不需要再回表查詢。

這種索引字段覆蓋了我們需要查詢的結(jié)果字段的場景我們稱為覆蓋索引。

覆蓋索引可以減少回表，減少索引樹的搜索次數(shù)，顯著提高查詢性能，所以覆蓋索引是一個(gè)比較好的優(yōu)化策略。

在實(shí)際開發(fā)中，可以按照業(yè)務(wù)需要把一些常用的檢索字段添加到索引中，利用覆蓋索引提高查詢效率，但是有些場景下不能為了使用覆蓋索引而過多的維護(hù)索引，畢竟索引的維護(hù)成本也是很高的。

最左前綴

這個(gè)時(shí)候我們還需要思考一個(gè)問題，在業(yè)務(wù)場景中我們的查詢是多樣化的，不能為了使用索引而為每一種場景都設(shè)計(jì)一個(gè)索引吧?

這個(gè)時(shí)候我們就要利用B+Tree樹索引結(jié)構(gòu)的另外一個(gè)特性最左前綴。

最左前綴可以是聯(lián)合索引的最左的幾個(gè)字段，也可以是字符串索引的最左的幾個(gè)字符。

創(chuàng)建聯(lián)合索引(name,age)，順序一致。

此時(shí)執(zhí)行sql語句：

mysql> select * from user where name = 'Alen'; 

雖然是聯(lián)合索引，但是name字段排在第一位，也是可以命中索引的。

mysql> select * from user where name like 'Al%'; 

如果使用name索引字段的最左N個(gè)字符串，也是可以命中索引的。但是如果我們使用%Al是不能命中索引的。

如果我們使用如下的sql查詢語句：

mysql>  select * from user where age = '16'； 

雖然age也是聯(lián)合索引的字段，但是他的順序在name之后，直接使用age查詢無法命中索引。所以創(chuàng)建聯(lián)合索引時(shí)一定要考慮索引字段的順序。

索引維護(hù)時(shí)有一個(gè)原則：如果能通過調(diào)整索引順序，可以少維護(hù)一個(gè)索引，那么就需要優(yōu)先調(diào)整順序而不是增加索引。

MySQL可以利用同一個(gè)索引進(jìn)行排序和掃描行，但是只有當(dāng)索引的列順序和order by子句的順序完全一致，并且列的排序方向都一致(正序或者倒序)時(shí)，MySQL才能使用對結(jié)果進(jìn)行排序。

order by子句和查詢類型限制是一樣的，也需要滿足”最左前綴“的原則，否則MySQL無法利用索引排序。

索引下推

當(dāng)我們的查詢語句不滿足最左前綴的時(shí)候會(huì)如何呢?

比如我們查詢名字第一個(gè)字為A，年齡為20，并且性別為1(男)的人員信息，sql語句如下：

mysql>  select * from user where name like 'A%' and age = 20 and sex = 1 ; 

按照我們前面學(xué)習(xí)的最左前綴原則，按照’A‘先搜索到第一個(gè)滿足條件的主鍵1，然后回表查詢判斷其他的兩個(gè)條件是否滿足。

MySQL5.6之后引入了索引下推的優(yōu)化，即會(huì)按照索引中包含的字段優(yōu)先過濾，減少回表的次數(shù)。

我們上述的sql語句在MySQL5.6之前會(huì)回表2次分別對比主鍵1和2兩條的數(shù)據(jù)的其他條件是否滿足，但是引入索引下推的優(yōu)化之后age = 20這個(gè)條件不滿的會(huì)直接過濾掉，只需要對主鍵1回表一次就可以獲取到結(jié)果。

總結(jié)

索引是用于快速查找數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)。

創(chuàng)建并合理的使用索引是提高查詢效率的基礎(chǔ)，在了解索引的數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)之后我們也應(yīng)該花時(shí)間去掌握高性能的索引策略，了解在實(shí)際開發(fā)中創(chuàng)建索引的一些原則，合理的選擇索引。