關於InnoDB索引的底層實現和實際效果

一、索引底層實現

MySQL有多種儲存引擎的實現，

SHOW ENGINES;

其中，InnoDB和MyISAM儲存引擎應用最普遍，

預設是InnoDB，唯獨InnoDB支援事務。是否支援事務，這也是任憑系統瓶頸往往就在資料庫，以及任憑各種高效能非關聯式資料庫應用得如何廣泛，而關聯式資料庫始終佔有重要地位的因素。

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

索引的本質就是一種資料結構，InnoDB的索引有兩種實現，B+樹以及hash表。hash表便於快速定位到一條資料，前提是hash衝突少，而B+樹的適用場景更廣泛，支援包括部分模糊匹配的各種範圍查詢。

這裡主要討論InnoDB中B+樹結構的索引。

1.1、區域性性原理

最原始，每插入一條資料就放進一個連結串列裡，並要根據主鍵排序，查詢一條資料的辦法就是逐條查詢匹配，每一次匹配就是一次磁碟IO，當資料越來越多，查詢效率就很低。為了減少IO次數，可以借用作業系統中頁的概念，每次查詢可以多返回一些資料到記憶體，而且存取某些資料通常也會存取它附近的資料，所以都包含進一個頁裡，一次性IO讀取。這就是區域性性原理。

頁可以認為是一次IO的最小單位，作業系統一般4kB，arm64已經支援8kB、16kB。

getconf PAGE_SIZE

查詢MySQL預設的頁大小，

SHOW GLOBAL STATUS LIKE 'Innodb_page_size';  --16384

InnoDB將所有記錄儲存在一個固定大小的單元中，該單元通常稱為“頁面”（儘管 InnoDB有時將其稱為“塊”）。這也是為什麼檢視資料表和索引的資料長度大小，都是16kB的整數倍。

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

當一個頁面的資料已經塞滿了，需要開闢新一頁，頁面越來越多，也要維持資料的有序性，所以頁面之間要有前後指標便於關聯，為了進一步提升查詢效率，可以使用B樹將這些資料頁串起來。

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

1.2、B樹和B+樹

隨著資料量的進一步增長，需要對B樹優化為B+樹，B+樹相比B樹：

• B樹所有節點都儲存資料，B+樹只有葉子節點儲存資料，非葉子節點只儲存索引欄位值。所以同一個節點的佔用空間內，B+樹的非葉子節點可以存放更多索引資訊，使樹的高度更低，意味著IO次數更少，查詢效率更高。
• B+樹的葉子節點是有序的，支援直接遍歷葉子節點進行範圍查詢。

B+樹的磁碟IO次數更少，更適合用作基於磁碟的儲存系統。

更多資料結構和演演算法演示：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

這樣一路推演得來B+樹的索引，同時也是一個基於主鍵的聚簇索引，所以InnoDB表必須要有主鍵，否則沒辦法將資料用B+樹串起來。若未主動建立主鍵，InnoDB內部也會自動加一個rowId作為隱藏的主鍵。而且主動建立主鍵最好保持自增或具有單調性，一方面便於索引排序比對，另一方面插入新資料時對索引結構的影響最小。

二、索引實際效果

2.0、準備資料

MySQL5.7.21，建一張表並初始化資料，

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');

全查資料，

SELECT * FROM t;

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

2.1、聯合索引和最左字首匹配

前面是針對InnoDB的主鍵索引（聚簇索引），除了主鍵索引還有輔助索引（即非主鍵索引，也是非聚簇索引，包含唯一索引、普通索引、聯合索引、全文索引），葉子節點存的資料只是主鍵，不需要冗餘其他欄位值，其他欄位值去回表查主鍵索引樹。比如對b、c、d三列加聯合索引，

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

聯合索引就是把三個欄位值按順序拼在一起作為整體，在B+樹裡進行排序放置。一般要使聯合索引生效就要遵循最左字首匹配原則。

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

select * from t where b>1;

這條sql是符合最左字首匹配規則的，推測執行計劃會用到索引，explain一下，

possible_keys=idx_bcd，執行計劃推測可能用到聯合索引，但實際查詢中，會做優化，不用索引，type=ALL進行了全表掃描，但效率比用到聯合索引要高（因為select *所以需要回表再查主鍵索引樹），IO次數更少，因為全表總共就8條資料，而且b欄位值大於1的佔絕大部分，意味著全表掃描後再進行過濾就很高效，filtered=75代表最終返回的記錄數和總共掃描的記錄數rows=8的百分比，數位越大越好，表示索引生效或本次查詢掃描的匹配性很高，所以直接去主鍵索引樹遍歷葉子節點就夠了。

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

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

select * from t where b>5;

type=range，possible_keys=key=idx_bcd，用到了聯合索引樹。

所以執行計劃內部往往會根據實際情況做查詢優化的調整。

2.3、覆蓋索引和回表查詢

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

select b from t where b>1;

Extra=Using index，覆蓋索引生效，在索引樹中就可以查到所需資料，避免了回表掃描主鍵索引的表資料檔案。這種一般效能不錯。

去掉where條件，全查聯合索引上已有的b/c/d欄位值，

select b,c from t;

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

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

MySQL內部存取資料，很多時候都會認為覆蓋索引的效率比主鍵索引高。所以有時候預設排序都優先用覆蓋索引而不是主鍵：主鍵索引排序失效。

2.4、排序order by和using filesort

不滿足最左字首匹配規則，所以用不到索引，

SELECT * FROM t ORDER BY b,d;

排序order by若用不到索引，就會type=ALL全表掃描，Using filesort額外在檔案記憶體中排序，因為本身具有排序的B+樹索引都用不到。

order by的Using filesort的邏輯：

• 開闢sort buffer排序記憶體空間，show variables like 'sort_buffer_size'；
• 將需要的欄位都放進去，select *一般就是所有，select b的話會自動把d也放進去，因為雖然不查d但是要用d排序；
• 快速排序。

Using filesort當記憶體不夠時可能會用臨時檔案排序，都是一回事。

另外Extra還有個Using temporary，代表查詢有使用臨時表，一般出現於排序、分組和多表join，查詢效率不高，建議優化。

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

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

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

上面是針對MySQL5.7，給表t加了聯合索引idx_bcd，如果對b/c/d三列排序時是有降序的，因為實際場景中往往有很多的查詢是根據某個業務時間欄位降序排的。

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

那就需要改變之前的索引idx_bcd，因為在建立索引時未指定升降序，就是預設ASC升序的，

那麼要支援c/d欄位降序的聯合索引，可以刪掉舊索引idx_bcd，

drop index idx_bcd on t;

再重建一個新順序的聯合索引，

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

但是再去explain，

Using index和type=index只是因為只需要用到idx_bcd這一個聯合索引就夠了，畢竟不需要回表查別的欄位

Using filesort還是證明了聯合索引在排序中未生效，再去檢視表的索引，發現Collation還都是A。

這是因為在MySQL5.7中只是語法上支援建立自定義順序的索引，但實際上總是用預設的升序。所以升級到實際支援的MySQL8再試試，

可以看到Collation已經支援降序D了，再explain一下，

已經沒有Using filesort了。

總結

以上為個人經驗，希望能給大家一個參考，也希望大家多多支援it145.com。