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

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

SHOW ENGINES;

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

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

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

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

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

1.1、局部性原理

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

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

getconf PAGE_SIZE

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

SHOW GLOBAL STATUS LIKE 'Innodb_page_size';  --16384

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

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

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

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

1.2、B樹和B+樹

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

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

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

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

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

二、索引實際效果

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;

全表掃描，對主鍵索引的葉子節(jié)點逐個掃描，時間復(fù)雜度O(n)。執(zhí)行計劃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（用到了主鍵索引，實際是從上到下走主鍵索引樹，縮小了查詢范圍），時間復(fù)雜度O(logn)。

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

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

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

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

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

select * from t where b>1;

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

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

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

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

select * from t where b>5;

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

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

2.3、覆蓋索引和回表查詢

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

select b from t where b>1;

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

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

select b,c from t;

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

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

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

2.4、排序order by和using filesort

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

SELECT * FROM t ORDER BY b,d;

排序order by若用不到索引，就會type=ALL全表掃描，Using filesort額外在文件內(nèi)存中排序，因為本身具有排序的B+樹索引都用不到。

order by的Using filesort的邏輯：

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

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

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

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

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

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

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

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

那就需要改變之前的索引idx_bcd，因為在創(chuàng)建索引時未指定升降序，就是默認(rèn)ASC升序的，

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

drop index idx_bcd on t;

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

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

但是再去explain，

Using index和type=index只是因為只需要用到idx_bcd這一個聯(lián)合索引就夠了，畢竟不需要回表查別的字段

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

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

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

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

總結(jié)

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

最新評論