本文主要是針對《Mysql技術內幕：InnoDB 存儲引擎》一書中第五章關於 InnoDB 存儲引擎的索引和演算法的學習總結。

InnoDB 主要支持以下幾種常見的索引：B+ 樹索引，哈希索引，全文索引。

一、B+ 樹索引

B+ 樹索引的特點

  • B+ 樹是為磁碟或者存取輔助設備設計的一種平衡查找樹。
  • 在 B+ 樹中所有記錄節點都是按照鍵值大小存放在同一層葉子節點上，並且各個葉子節點通過指針相連。
  • B+ 樹索引並不能找到給定鍵值的具體行，而是能找到具體行所在的頁，然後把該頁讀入內存中，再進行相應的查找。
  • B+ 樹索引具有高扇出性，樹的高度一般是 2~4 層，也就是查某一鍵值的行記錄一般只需要 2~4 次。
  • 資料庫中 B+ 樹索引分為聚集索引和輔助索引，葉子節點存放所有的數據。

聚集 B+ 樹索引

  • 聚集索引是按照每個表的主鍵構造的一顆 B+ 樹，葉子節點是數據頁，而非數據頁的索引頁中存放的僅僅是鍵值以及指向數據頁的偏移量。
  • 因為每張表只有一個主鍵，所以只能擁有一聚集索引。
  • 聚集索引的存儲不是物理上的連續，而是通過雙向鏈表維持邏輯上的連續。
  • 因為主鍵本身是排序的，如果查詢時根據主鍵排序，不會產生再次的 filesort 操作。

輔助 B+ 樹索引

  • 輔助索引頁稱為非聚集索引，葉子節點並不包含行記錄的全部數據。
  • 葉子節點存放的是輔助索引的鍵值以及其對應主鍵值。
  • 對於輔助索引的查找邏輯是先根據輔助索引頁找到輔助索引對應的主鍵列表，然後再根據聚集索引頁查到真正的行記錄。

B+ 樹索引的管理

索引的創建/刪除

  • 可以對索引的整個列進行索引，也可以只索引一個列的開頭部分數據。

  • 兩種創建索引的方式(ALTER TABLE 和 CREATE/DROP INDEX）。

ALTER TABLE 方式可以一次性創建或者刪除多個索引，創建索引時，索引名稱可以省略：

ALTER TABLE table_name
ADD {INDEX|KEY} [index_name]
[index_type] (index_col_name,...) [index_option]

ALTER TABLE table_name
DROP {INDEX|KEY} index_name

CREATE/DROP INDEX 一次只能創建一個索引，必須指定索引名稱：

CREATE INDEX index_name
[index_type]
ON table_name (index_col_name,...) [index_option]

DROP INDEX table_name
ON table_name

  • 可以通過 SHOW INDEX FROM table_name 查詢相關索引信息：

SHOW INDEX 展示結果中每列的含義：

- Table：表的名稱
- Non_unique：索引是否不唯一，0 表示唯一， 1 表示唯一
- Key_name：索引的名稱
- Seq_in_index：該列在索引中位置，非聯合索引都為 1，聯合索引按照索引展示
- Column_name：列名稱
- Collation：列以什麼方式存儲在索引中。可以是 A 或者 NULL，A 表示有序的，B+ 樹索引都是 A
- Cardinality：索引中唯一值的數目的估計值，該值越大越好。該值不是實時計算的，可以通過運行 ANALYZE TABLE 進行更新
- Sub_part：如果列只是被部分地編入索引，如果是整列索引，則顯示為 NULL
- Packed：指示關鍵字如何被壓縮。如果沒有被壓縮，則為 NULL
- Null：如果列的定義中允許 NULL，則為 YES。如果沒有，則該列含有 NO
- Index_type：索引的類型（BTREE, FULLTEXT, HASH, RTREE）
- Comment：注釋

快速創建索引（Fast Index Creation）

MYSQL 5.5 版本之前對於索引的創建和刪除都是通過複製的方式：

  • 先創建一張臨時表
  • 然後把原表中的數據導入臨時表
  • 刪除原始表
  • 修改臨時表的名字為原始表的名字

從 InnoDB 1.0.x 開始支持 Fast Index Creation 方式創建，簡稱 FIC。對於輔助索引的創建，首先會對該表加一個 S 鎖，在創建的過程中不需要重建表，因此速度相對之前提高很多，但是創建的過程中只能對該表進行讀，不能寫。

在線數據定義(Online DDL)

從 Mysql 5.6 開始支持 Online DDL，允許輔助索引創建的同時還可以對錶進行 UPDATE、DELETE、INSERT 操作，極大提高了資料庫的可用性。

Online DDL 可以支持的操作如下：

  • 輔助索引的創建和刪除
  • 改變自增長值
  • 添加和刪除外鍵約束
  • 列重命名

創建索引通過選項 ALGORITHM 參數指定創建索引的方式：

  • ALGORITHM = COPY：表示通過創建臨時表（複製）的方式
  • ALGORITHM = INPLACE：不需要創建臨時表
  • ALGORITHM = DEFAULT：根據參數 old_alter_table 決定選擇 COPY 還是 INPLACE 方式

Online DDL 的實現原理：

在創建索引時將 INSERT，UPDATE，DELETE 操作日誌寫入緩存，待完成索引創建後再重做引用到表上，保證了數據的一致性。
寫入緩存的大小由參數 innodb_online_alter_log_max_size 參數設置，默認是 128MB。

Cardinality

上文中我們知道通過 SHOW INDEX 命令可以查看對應索引的 Cardinality，該值表示索引中不重複的預估值。

  • Cardinality 很關鍵，決定了索引是否具有高選擇性，優化器會根據該值來判斷是否使用索引。
  • 該值越接近於表中真實的數據行數，選擇性越高，如果使用索引的查詢速度越快。
  • 由於該值計算比較耗時，因此是一個預估的值，通過動態採樣的方式計算得到。
  • 默認情況下 InnnoDB 通過對 8 個葉子節點採樣進行計算，通過參數 innodb_stats_sample_pages 來設置採樣的個數。
  • ANALYSE TABLE，SHOW TABLE STATUS，SHOW INDEX 時都會導致重新去計算 Cardinality 的值，因此這些命令可以比較耗時。

B+ 樹索引的應用

聯合索引

聯合索引是指對表中的多個欄位進行索引。

  • 聯合索引要符合最左原則，假如我們建立了聯合索引(a, b, c)，那麼在查詢時 [a], [a, b], [a, b, c] 的組合查詢都可以使用該索引。
  • 優化器對於聯合索引的選擇：

- 我們建一張表如下：
create table t (
a int,
b DATE
) ENGINNE=InnoDB;

alter table t
add key a_index (a),
add key a_b_index (a, b);

- 執行如下查詢，最終發現優化器選擇 a_index 索引，因為該葉子節點包含單個鍵值，存放的記錄更多
explain select * from t where a = 2;

- 執行如下查詢，發現優化器選擇 a_b_index 索引，因為在 a = 2 的情況下，b 已經排好序了，減少了一次排序的過程
explain select * from t where a = 2 order by b;

覆蓋索引

覆蓋索引是指從輔助索引中就可以查詢出結果，而不需要查詢聚集索引中真正的記錄，由於輔助索引遠遠小於聚集索引，可以大大減少 IO 查詢次數。

  • 如果是使用了覆蓋索引，則通過 explain 查看執行計劃時會發現 Extra 欄位顯示為 Using index。
  • 假如輔助索引 (key1, key2, key3)，聚集索引(pkey1, pkey2)，因為輔助索引葉子節點包含了 (pkey1, pkey2, key1, key2, key3)信息，對於這些值的查詢都會使用覆蓋索引。
  • select count(*) from table_name，如果存在輔助索引，優化器會選擇輔助索引提高查詢效率。

不使用索引的情況

在進行範圍查找或者 join 連接操作時，在不能使用覆蓋索引的情況下，如果發現使用輔助索引查找出來的結果占整個數據集蠻大一部分時，優化器會直接選擇使用聚集索引進行全表順序掃描。因為如果通過輔助索引查找到的數據較大時且為離散無序，則再會執行一次聚集索引的無序離散掃描，如果數據較大時，反而會降低性能。當然我們可以通過 force Index 來強制使用某個索引。

MRR 優化和 ICP 優化

  • MRR(Multi Range Read) 優化

MRR 優化是為了減少磁碟的隨機訪問次數，將隨機訪問轉換為較為順序的數據訪問。優化策略如下：

- 將查詢得到的輔助索引鍵值存放在緩存中
- 將緩存中的輔助索引鍵值根據 ROWID 排序
- 根據 ROWID 排序順序來訪問實際的數據文件，變成了較為順序的聚集查詢

使用 MRR 優化後，我們會在執行計劃結果中看到 Extra 欄位中含有 Using MRR

  • ICP(Index Condition Pushdown) 優化

ICP 從 MYSQL 5.6 版本開始支持，使用了 ICP 優化後，MYSQL 在取出索引的同時，判斷是否可以進行 WHERE 條件的過濾。
也就是將 WHERE 條件的過濾放在存儲引擎層，大大減少上層 SQL 層對數據的讀取，從而提高性能。
如果使用 ICP 優化，執行計劃的 Extra 欄位會包含 Using Index Condition。

哈希索引

前面文章InnoDB 存儲引擎的關鍵特性學習 中提到過，哈希索引是自適應的，也就是 InnoDB 根據使用情況自動為輔助索引建立哈希索引，非人為干預。

  • 通過 SHOW ENGINE INNODB STATUS 可以查看當前自適應哈希索引的使用情況
  • 哈希索引只能用來搜索等值的查詢，對於範圍的查詢便無能為力了
  • 通過 innodb_adaptive_hash_index 參數可以用來禁用或者啟動自適應哈希索引

全文檢索

全文檢索是將存儲中資料庫中的整本書或者整篇文章中的任意內容信息查找出來的技術，InnoDB 從 1.2.x 版本以後開始支持全文索引。

倒排索引

倒排索引是通過在輔助表中存放單詞與單詞在一個或者多個文檔中所在位置的映射關係實現的，通常是用關聯數組作存儲結構。一般的存儲形式有兩種：

  • inverted file index： {單詞， 單詞所在文檔的 ID}
  • full inverted index： {單詞，(單詞所在文檔的 ID，在具體文檔的位置)}

InnoDB 全文檢索的實現

InnoDB 存儲引擎就是採用倒排索引中的 full inverted index 實現的。

  • Auxiliiary Table（輔助表）

存放倒排索引的表叫 Auxiliiary Table（輔助表），該表是持久的表，存放在磁碟上。

  • FTS Index Cache（全文檢索索引緩存）

FTS Index Cache 是用來提高全文檢索性能的，是一個紅黑樹結構。每次事務提交操作，InnoDB 會將倒排索引數據先插入到 FTS Index Cache 中，而不是每次都更新 Auxiliiary Table，然後在下次全文檢索時，首先會將 FTS Index Cache 中 word 欄位合併到 Auxiliiary Table，然後再進行查詢，這種 Merge 操作很類似「插入緩存」的概念，

- innodb_ft_cache_size 參數用來控制 FTS Index Cache 的大小，默認是 32M。
- 當該緩存滿時，會將其中數據同步到 Auxiliiary Table。

  • 通過參數 innodb_ft_aux_table 設置來觀察倒排索引表 Auxiliiary Table 中的數據：

-- 設置 innodb_ft_aux_table 等於 test 數據下的 table_a 表。
set GLOBAL innodb_ft_aux_table=test/table_a;
-- 通過 information_schema 下的表 INNODB_FT_INDEX_TABLE 便可以看到 Auxiliiary Table 數據信息。
select * from information_schema.INNODB_FT_INDEX_TABLE;

  • FTS_DOC_ID

- InnoDB 為了支持全文索引，每個設置全文索引的表中必須有一個欄位用來標記文本的 ID，那就是 FTS_DOC_ID
- FTS_DOC_ID 類型是 BIGINT UNSIGNED NOT NULL
- InnoDB 會自動為 FTS_DOC_ID 列加上名為 FTS_DOC_ID_INDEX 的唯一索引

  • 全文索引的刪除操作

- InnoDB 對於刪除操作，在事務提交時，並不會刪除 Auxiliiary Table 中的記錄，只是刪除 FTS Index Cache 中的記錄
- 在刪除操作後，InnoDB 會記錄其 FTS_DOC_ID 並保存在 DELETED Auxiliiary Table 中
- 通過 information_schema 下的表 INNODB_FT_DELETED 來觀察刪除的 FTS_DOC_ID
- 通過命令 OPTIMIZE TABLE 可以將已經刪除的記錄從 Auxiliiary Table 中徹底刪除

  • stopword 列表

- stopword 列表中存放了不需要對其進行索引分詞的單詞列表
- 通過 information_schema.INNODB_FT_DEFAULT_STOPWORD 可以查看默認的 stopword 列表，默認 36 個
- 用戶可以通過參數 innodb_ft_server_stopword_table 來自定義 stopword 列表

  • InnoDB 全文索引存在的限制：

- 每張表只能有一個全文檢索的索引
- 由多個列組成的全文索引，每個列字符集和排序規則必須相同
- 不支持沒有單詞分界符的語言，如中文，日語等

全文索引語法

添加全文索引

- ALTER TABLE 時添加全文索引
alter table testtable add fulltext index testfulltext(clumn1,clumn2);

- CREATE TABLE 時添加全文索引
CREATE TABLE articles (
id INTUNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
title VARCHAR(200),
body TEXT,
FULLTEXT (title,body)
) ENGINE=InnoDB CHARACTER SET utf8mb4;

使用全文索引查找

通過 MATCH() ... AGAINST() ... 來進行全文檢索的的查詢，MATCH 指定了被查詢的列，AGAINST 指定用何種方法進行查詢。

- 如果沒有設置全文索引使用 MATCH() ... AGAINST() ...，Mysql 會拋出異常
- 在使用 MATCH 函數進行查詢，返回的結果按照返回結果的相關性降序排序，相關性由單詞出現的次數，出現在幾個文檔中等來決定
- 如果查詢的 word 在 stopword 列表中，則忽略該單詞的查詢
- 查詢的 word 長度必須在區間[innodb_ft_min_token_size, innodb_ft_max_token_size]，默認是[3, 84]

  • Natural Language 查詢模式

Natural Language 是默認的查詢模式

- 按自然語言搜索模式查詢
SELECT * FROM articles WHERE MATCH (title,body) AGAINST (關鍵詞 IN NATURAL LANGUAGE MODE);

  • BOOLEAN 查詢模式

若全文檢索按照 BOOLEAN 模式進行查詢，那麼查詢字元串前後的字元有特殊含義：

1. +： 表示該 word 必須存在
2. -： 表示該 word 必須被排除
3. (no operator)：沒有特殊表示 該 word 出現是可選的，如果出現，其相關性會更高
4. >: 表示該單詞出現時，增加其相關性
5. <：表示該單詞出現時，降低其相關性
6. ~：該單詞出現，相關性為負
7. *：表示以該單詞開頭的單詞

以下是以 BOOLEAN 模式進行查詢的例子：

- 按布爾全文搜索模式查詢，匹配既有管理又有資料庫的記錄
SELECT * FROM articles WHERE MATCH (title,body) AGAINST (+資料庫 +管理 IN BOOLEAN MODE);

- 按布爾全文搜索模式查詢，匹配有資料庫，但是沒有管理的記錄
SELECT * FROM articles WHERE MATCH (title,body) AGAINST (+資料庫 -管理 IN BOOLEAN MODE);

- 按布爾全文搜索模式查詢，匹配MySQL，但是把資料庫的相關性降低
SELECT * FROM articles WHERE MATCH (title,body) AGAINST (>資料庫 +MySQL INBOOLEAN MODE);

Query Expansion

Mysql 還支持全文索引的擴展查詢，通過在查詢短語中添加 WITH QUERY EXPANSION 可以開啟擴展查詢，查詢分為兩個階段：

  • 根據搜索的單詞進行全文檢索查詢
  • 根據第一階段產生的單詞再進行一次全文檢索查詢

select * from articles
where MATCH(title, body)
AGAINST(database WITH QUERY EXPANSION)

Query Expansion 查詢會來帶一些非相關性查詢，所以使用起來要謹慎


推薦閱讀：
相关文章