一、索引底層實(shí)現(xiàn)

MySQL有多種存儲(chǔ)引擎的實(shí)現(xiàn)，

SHOW ENGINES;

其中，InnoDB和MyISAM存儲(chǔ)引擎應(yīng)用最普遍，

默認(rèn)是InnoDB，唯獨(dú)InnoDB支持事務(wù)。是否支持事務(wù)，這也是任憑系統(tǒng)瓶頸往往就在數(shù)據(jù)庫(kù)，以及任憑各種高性能非關(guān)系數(shù)據(jù)庫(kù)應(yīng)用得如何廣泛，而關(guān)系數(shù)據(jù)庫(kù)始終占有重要地位的因素。

不管是RDBMS還是NoSQL，都是為了查取數(shù)據(jù)，伴隨著數(shù)據(jù)量越來(lái)越大，查詢壓力也越來(lái)越大，所以多種RDBMS和NoSQL都有索引，來(lái)保障快速查到數(shù)據(jù)。

索引的本質(zhì)就是一種數(shù)據(jù)結(jié)構(gòu)，InnoDB的索引有兩種實(shí)現(xiàn)，B+樹(shù)以及hash表。hash表便于快速定位到一條數(shù)據(jù)，前提是hash沖突少，而B(niǎo)+樹(shù)的適用場(chǎng)景更廣泛，支持包括部分模糊匹配的各種范圍查詢。

這里主要討論InnoDB中B+樹(shù)結(jié)構(gòu)的索引。

1.1、局部性原理

最原始，每插入一條數(shù)據(jù)就放進(jìn)一個(gè)鏈表里，并要根據(jù)主鍵排序，查詢一條數(shù)據(jù)的辦法就是逐條查找匹配，每一次匹配就是一次磁盤IO，當(dāng)數(shù)據(jù)越來(lái)越多，查詢效率就很低。為了減少IO次數(shù)，可以借用操作系統(tǒng)中頁(yè)的概念，每次查詢可以多返回一些數(shù)據(jù)到內(nèi)存，而且訪問(wèn)某些數(shù)據(jù)通常也會(huì)訪問(wèn)它附近的數(shù)據(jù)，所以都包含進(jìn)一個(gè)頁(yè)里，一次性IO讀取。這就是局部性原理。

頁(yè)可以認(rèn)為是一次IO的最小單位，操作系統(tǒng)一般4kB，arm64已經(jīng)支持8kB、16kB。

getconf PAGE_SIZE

查詢MySQL默認(rèn)的頁(yè)大小，

SHOW GLOBAL STATUS LIKE 'Innodb_page_size';  --16384

InnoDB將所有記錄存儲(chǔ)在一個(gè)固定大小的單元中，該單元通常稱為“頁(yè)面”（盡管 InnoDB有時(shí)將其稱為“塊”）。這也是為什么查看數(shù)據(jù)表和索引的數(shù)據(jù)長(zhǎng)度大小，都是16kB的整數(shù)倍。

接著，借鑒字典前面的目錄，試圖對(duì)這一大批數(shù)據(jù)分組（比如根據(jù)主鍵），這樣每次查詢先用二分法等匹配目錄中的位置，然后再定位到具體某一組查詢，效率更高。

當(dāng)一個(gè)頁(yè)面的數(shù)據(jù)已經(jīng)塞滿了，需要開(kāi)辟新一頁(yè)，頁(yè)面越來(lái)越多，也要維持?jǐn)?shù)據(jù)的有序性，所以頁(yè)面之間要有前后指針便于關(guān)聯(lián)，為了進(jìn)一步提升查詢效率，可以使用B樹(shù)將這些數(shù)據(jù)頁(yè)串起來(lái)。

MySQL中頁(yè)的屬性：https://dev.mysql.com/doc/internals/en/innodb-fil-header.html

1.2、B樹(shù)和B+樹(shù)

隨著數(shù)據(jù)量的進(jìn)一步增長(zhǎng)，需要對(duì)B樹(shù)優(yōu)化為B+樹(shù)，B+樹(shù)相比B樹(shù)：

• B樹(shù)所有節(jié)點(diǎn)都保存數(shù)據(jù)，B+樹(shù)只有葉子節(jié)點(diǎn)保存數(shù)據(jù)，非葉子節(jié)點(diǎn)只保存索引字段值。所以同一個(gè)節(jié)點(diǎn)的占用空間內(nèi)，B+樹(shù)的非葉子節(jié)點(diǎn)可以存放更多索引信息，使樹(shù)的高度更低，意味著IO次數(shù)更少，查詢效率更高。
• B+樹(shù)的葉子節(jié)點(diǎn)是有序的，支持直接遍歷葉子節(jié)點(diǎn)進(jìn)行范圍查詢。

B+樹(shù)的磁盤IO次數(shù)更少，更適合用作基于磁盤的存儲(chǔ)系統(tǒng)。

更多數(shù)據(jù)結(jié)構(gòu)和算法演示：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

這樣一路推演得來(lái)B+樹(shù)的索引，同時(shí)也是一個(gè)基于主鍵的聚簇索引，所以InnoDB表必須要有主鍵，否則沒(méi)辦法將數(shù)據(jù)用B+樹(shù)串起來(lái)。若未主動(dòng)創(chuàng)建主鍵，InnoDB內(nèi)部也會(huì)自動(dòng)加一個(gè)rowId作為隱藏的主鍵。而且主動(dòng)創(chuàng)建主鍵最好保持自增或具有單調(diào)性，一方面便于索引排序比對(duì)，另一方面插入新數(shù)據(jù)時(shí)對(duì)索引結(jié)構(gòu)的影響最小。

二、索引實(shí)際效果

2.0、準(zhǔn)備數(shù)據(jù)

MySQL5.7.21，建一張表并初始化數(shù)據(jù)，

CREATE TABLE `t` (
  `a` int(10) NOT NULL,
  `b` int(10) DEFAULT NULL,
  `c` int(10) DEFAULT NULL,
  `d` int(10) DEFAULT NULL,
  `e` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`a`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
INSERT INTO t VALUES(4,1,1,1,'d');
INSERT INTO t VALUES(1,1,1,1,'a');
INSERT INTO t VALUES(8,8,8,8,'h');
INSERT INTO t VALUES(2,2,2,2,'b');
INSERT INTO t VALUES(5,2,3,5,'e');
INSERT INTO t VALUES(3,3,2,2,'c');
INSERT INTO t VALUES(7,4,5,5,'g');
INSERT INTO t VALUES(6,6,4,4,'f');

全查數(shù)據(jù)，

SELECT * FROM t;

全表掃描，對(duì)主鍵索引的葉子節(jié)點(diǎn)逐個(gè)掃描，時(shí)間復(fù)雜度O(n)。執(zhí)行計(jì)劃explain的type=ALL。

type效率：ALL<index<range<ref<eq_ref<const<system。

SELECT * FROM t WHERE a=4;

避免了全表掃描，explain的type=const，possible_keys=PRIMARY（估算走主鍵索引），key=PRIMARY（用到了主鍵索引，實(shí)際是從上到下走主鍵索引樹(shù)，縮小了查詢范圍），時(shí)間復(fù)雜度O(logn)。

2.1、聯(lián)合索引和最左前綴匹配

前面是針對(duì)InnoDB的主鍵索引（聚簇索引），除了主鍵索引還有輔助索引（即非主鍵索引，也是非聚簇索引，包含唯一索引、普通索引、聯(lián)合索引、全文索引），葉子節(jié)點(diǎn)存的數(shù)據(jù)只是主鍵，不需要冗余其他字段值，其他字段值去回表查主鍵索引樹(shù)。比如對(duì)b、c、d三列加聯(lián)合索引，

create index idx_bcd on t(b, c, d);

聯(lián)合索引就是把三個(gè)字段值按順序拼在一起作為整體，在B+樹(shù)里進(jìn)行排序放置。一般要使聯(lián)合索引生效就要遵循最左前綴匹配原則。

2.2、全表掃描一定比使用索引慢？

select * from t where b>1;

這條sql是符合最左前綴匹配規(guī)則的，推測(cè)執(zhí)行計(jì)劃會(huì)用到索引，explain一下，

possible_keys=idx_bcd，執(zhí)行計(jì)劃推測(cè)可能用到聯(lián)合索引，但實(shí)際查詢中，會(huì)做優(yōu)化，不用索引，type=ALL進(jìn)行了全表掃描，但效率比用到聯(lián)合索引要高（因?yàn)閟elect *所以需要回表再查主鍵索引樹(shù)），IO次數(shù)更少，因?yàn)槿砜偣簿?條數(shù)據(jù)，而且b字段值大于1的占絕大部分，意味著全表掃描后再進(jìn)行過(guò)濾就很高效，filtered=75代表最終返回的記錄數(shù)和總共掃描的記錄數(shù)rows=8的百分比，數(shù)字越大越好，表示索引生效或本次查詢掃描的匹配性很高，所以直接去主鍵索引樹(shù)遍歷葉子節(jié)點(diǎn)就夠了。

所以，全表掃描不一定比使用到索引慢，而且key也不一定是possible_keys的子集。

而改查詢條件b>1為b>5，就又用到了聯(lián)合索引，

select * from t where b>5;

type=range，possible_keys=key=idx_bcd，用到了聯(lián)合索引樹(shù)。

所以執(zhí)行計(jì)劃內(nèi)部往往會(huì)根據(jù)實(shí)際情況做查詢優(yōu)化的調(diào)整。

2.3、覆蓋索引和回表查詢

繼續(xù)上面where b>1，這次不去select *，只select b/c/d，就會(huì)用到聯(lián)合索引，不必回表查主鍵索引樹(shù)。

select b from t where b>1;

Extra=Using index，覆蓋索引生效，在索引樹(shù)中就可以查到所需數(shù)據(jù)，避免了回表掃描主鍵索引的表數(shù)據(jù)文件。這種一般性能不錯(cuò)。

去掉where條件，全查聯(lián)合索引上已有的b/c/d字段值，

select b,c from t;

possible_keys=NULL，推測(cè)不用索引；type=index，key=idx_bcd，實(shí)際用到了聯(lián)合索引，只需要遍歷這個(gè)覆蓋索引即可，不用遍歷主鍵索引樹(shù)。

這個(gè)案例也證明了key不一定是possible_keys的子集。

MySQL內(nèi)部訪問(wèn)數(shù)據(jù)，很多時(shí)候都會(huì)認(rèn)為覆蓋索引的效率比主鍵索引高。所以有時(shí)候默認(rèn)排序都優(yōu)先用覆蓋索引而不是主鍵：主鍵索引排序失效。

2.4、排序order by和using filesort

不滿足最左前綴匹配規(guī)則，所以用不到索引，

SELECT * FROM t ORDER BY b,d;

排序order by若用不到索引，就會(huì)type=ALL全表掃描，Using filesort額外在文件內(nèi)存中排序，因?yàn)楸旧砭哂信判虻腂+樹(shù)索引都用不到。

order by的Using filesort的邏輯：

• 開(kāi)辟sort buffer排序內(nèi)存空間，show variables like 'sort_buffer_size'；
• 將需要的字段都放進(jìn)去，select *一般就是所有，select b的話會(huì)自動(dòng)把d也放進(jìn)去，因?yàn)殡m然不查d但是要用d排序；
• 快速排序。

Using filesort當(dāng)內(nèi)存不夠時(shí)可能會(huì)用臨時(shí)文件排序，都是一回事。

另外Extra還有個(gè)Using temporary，代表查詢有使用臨時(shí)表，一般出現(xiàn)于排序、分組和多表join，查詢效率不高，建議優(yōu)化。

Using filesort和Using temporary一般都建議對(duì)排序字段加索引。

若是order by a，a是主鍵，已有索引中的順序，就用不到filesort，也就不需要上面那三步了。order by b,c,d也一樣不會(huì)filesort。

2.5、MySQL8之前只支持索引ASC升序

上面是針對(duì)MySQL5.7，給表t加了聯(lián)合索引idx_bcd，如果對(duì)b/c/d三列排序時(shí)是有降序的，因?yàn)閷?shí)際場(chǎng)景中往往有很多的查詢是根據(jù)某個(gè)業(yè)務(wù)時(shí)間字段降序排的。

SELECT b,c,d FROM t ORDER BY b ASC,c DESC,d DESC;

那就需要改變之前的索引idx_bcd，因?yàn)樵趧?chuàng)建索引時(shí)未指定升降序，就是默認(rèn)ASC升序的，

那么要支持c/d字段降序的聯(lián)合索引，可以刪掉舊索引idx_bcd，

drop index idx_bcd on t;

再重建一個(gè)新順序的聯(lián)合索引，

create index idx_bcd on t(b asc, c desc, d desc);

但是再去explain，

Using index和type=index只是因?yàn)橹恍枰玫絠dx_bcd這一個(gè)聯(lián)合索引就夠了，畢竟不需要回表查別的字段

Using filesort還是證明了聯(lián)合索引在排序中未生效，再去查看表的索引，發(fā)現(xiàn)Collation還都是A。

這是因?yàn)樵?code>MySQL5.7中只是語(yǔ)法上支持創(chuàng)建自定義順序的索引，但實(shí)際上總是用默認(rèn)的升序。所以升級(jí)到實(shí)際支持的MySQL8再試試，

可以看到Collation已經(jīng)支持降序D了，再explain一下，

已經(jīng)沒(méi)有Using filesort了。

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論