圖解 MySQL 索引，清晰易懂，寫得太好了！

作者：shuaibing90?

來源：www.xysycx.cn/articles/2020/12/05/1607146183637.html

什么是索引？

索引是輔助存儲(chǔ)引擎高效獲取數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)。

很多人形象的說索引就是數(shù)據(jù)的目錄，便于存儲(chǔ)引擎快速的定位數(shù)據(jù)。

索引的分類

我們經(jīng)常從以下幾個(gè)方面對(duì)索引進(jìn)行分類

從 「數(shù)據(jù)結(jié)構(gòu)的角度」 對(duì)索引進(jìn)行分類

• B+tree
• Hash
• Full-texts 索引

從 「物理存儲(chǔ)的角度」 對(duì)索引進(jìn)行分類

• 聚簇索引
• 二級(jí)索引(輔助索引)

從 「索引字段特性角度」 分類

• 主鍵索引
• 唯一索引
• 普通索引
• 前綴索引

從 「組成索引的字段個(gè)數(shù)角度」 分類

• 單列索引
• 聯(lián)合索引（復(fù)合索引）

數(shù)據(jù)結(jié)構(gòu)角度看索引

下表是 MySQL 常見的存儲(chǔ)引擎 InnoDB，MyISAM 和 Memory 分別支持的索引類型

在實(shí)際使用中，InnoDB 作為 MySQL 建表時(shí)默認(rèn)的存儲(chǔ)引擎

對(duì)上表進(jìn)行橫向查看可以了解到，B+tree 是 MySQL 中被存儲(chǔ)引擎采用最多的索引類型。

這里淺嘗輒止的談一下 B+tree 與 Hash 和紅黑樹的區(qū)別。

B+tree 和 B-tree

1970 年，R.Bayer 和 E.Mccreight 提出了一種適用于外查找的平衡多叉樹——B-樹，磁盤管理系統(tǒng)中的目錄管理，以及數(shù)據(jù)庫系統(tǒng)中的索引組織多數(shù)采用 B-Tree 這種數(shù)據(jù)結(jié)構(gòu)。--數(shù)據(jù)結(jié)構(gòu) C 語言版第二版 嚴(yán)蔚敏

B+tree 是 B-Tree 的一個(gè)變種。（哦，對(duì)了，B-tree 念 B 樹，它不叫 B 減樹。。。）

B+tree 只在葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，而 B-tree 非葉子節(jié)點(diǎn)也存儲(chǔ)數(shù)據(jù)，對(duì)此處有疑問的可以到下面的連接自己插入數(shù)據(jù)測(cè)試一番。

• B-tree : https://www.cs.usfca.edu/~galles/visualization/BTree.html
• B+tree : https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

因此，B+tree 單個(gè)節(jié)點(diǎn)的數(shù)量更小，在相同的磁盤 IO 下能查詢更多的節(jié)點(diǎn)。

另外 B+tree 葉子節(jié)點(diǎn)采用單鏈表鏈接適合 MySQL 中常見的基于范圍的順序檢索場(chǎng)景，而 B-tree 無法做到這一點(diǎn)。

B+tree 和紅黑樹

對(duì)于有 N 個(gè)葉子節(jié)點(diǎn)的 B+tree，搜索復(fù)雜度為 「O(logdN) ,d 是指 degree 是指 B+tree 的度」，表示節(jié)點(diǎn)允許的最大子節(jié)點(diǎn)個(gè)數(shù)為 d 個(gè)，在實(shí)際的運(yùn)用中 d 值是大于 100 的，即使數(shù)據(jù)達(dá)到千萬級(jí)別時(shí)候 B+tree 的高度依然維持在 3-4 左右，保證了 3-4 次磁盤 I/O 就能查到目標(biāo)數(shù)據(jù)。

從上圖中可以看出紅黑樹是二叉樹，節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)最多為 2 個(gè)，意味著其搜索復(fù)雜度為 「O(logN)」，比 B+ 樹高出不少，因此紅黑樹檢索到目標(biāo)數(shù)據(jù)所需經(jīng)理的磁盤 I/O 次數(shù)更多。

B+tree 索引與 Hash 表

范圍查詢是 MySQL 數(shù)據(jù)庫中常見的場(chǎng)景，而 Hash 表不適合做范圍查詢，Hash 表更適合做等值查詢，另外 Hash 表還存在 Hash 函數(shù)選擇和 Hash 值沖突等問題。

因?yàn)檫@些原因，B+tree 索引要比 Hash 表索引有更廣的適用場(chǎng)景。

物理存儲(chǔ)角度看索引

MySQL 中的兩種常用存儲(chǔ)引擎對(duì)索引的處理方式差別較大。

InnoDB 的索引

首先看一下 InnoDB 存儲(chǔ)引擎中的索引，InnoDB 表的索引按照葉子節(jié)點(diǎn)存儲(chǔ)的是否為完整表數(shù)據(jù)分為聚簇索引和二級(jí)索引。

全表數(shù)據(jù)就是存儲(chǔ)在聚簇索引中的。

聚簇索引以外的其它索引叫做二級(jí)索引。

下面結(jié)合實(shí)際的例子介紹下這兩類索引。

create?table?workers
?(
?????id????int(11)?????not?null?auto_increment?comment?'員工工號(hào)',
?????name??varchar(16)?not?null?comment?'員工名字',
?????sales?int(11)?default?null?comment?'員工銷售業(yè)績',
?????primary?key?(id)
?)?engine?InnoDB
???AUTO_INCREMENT?=?10
???default?charset?=?utf8;

?insert?into?workers(id,?name,?sales)
?values?(1,?'江南',?12744);
?insert?into?workers(id,?name,?sales)
?values?(3,?'今何在',?14082);
?insert?into?workers(id,?name,?sales)
?values?(7,?'路明非',?14738);
?insert?into?workers(id,?name,?sales)
?values?(8,?'呂歸塵',?7087);
?insert?into?workers(id,?name,?sales)
?values?(11,?'姬野',?8565);
?insert?into?workers(id,?name,?sales)
?values?(15,?'凱撒',?8501);
?insert?into?workers(id,?name,?sales)
?values?(20,?'繪梨衣',?7890);

我們現(xiàn)在自己的測(cè)試數(shù)據(jù)庫中創(chuàng)建一個(gè)包含銷售員信息的測(cè)試表 workers

包含 id(主鍵),name,sales 三個(gè)字段，指定表的存儲(chǔ)引擎為 InnoDB。

然后插入 8 條數(shù)據(jù)

這個(gè)例子當(dāng)中，workers 表的聚簇索引建立在字段 id 上

為了準(zhǔn)確模擬，我們先把主鍵 id 插入 b+tree 得到下圖

然后在此圖基礎(chǔ)上，我畫出了高清版。

從圖中可以看到，聚簇索引的每個(gè)葉子節(jié)點(diǎn)存儲(chǔ)了一行完整的表數(shù)據(jù)，葉子節(jié)點(diǎn)間采用單向鏈表按 id 列遞增連接，可以方便的進(jìn)行順序檢索。

InnoDB 表要求必須有聚簇索引，默認(rèn)在主鍵字段上建立聚簇索引，在沒有主鍵字段的情況下，表的第一個(gè) NOT NULL 的唯一索引將被建立為聚簇索引，在前兩者都沒有的情況下，InnoDB 將自動(dòng)生成一個(gè)隱式自增 id 列并在此列上創(chuàng)建聚簇索引。

接著來看二級(jí)索引。

還以剛才的 workers 表為例

我們?cè)?name 字段上添加二級(jí)索引 index_name

alter?table?workers?add?index?index_name(name);

同樣我們畫出了二級(jí)索引 index_name 的 B+tree 示意圖

圖中可以看出二級(jí)索引的葉子節(jié)點(diǎn)并不存儲(chǔ)一行完整的表數(shù)據(jù)，而是存儲(chǔ)了聚簇索引所在列的值，也就是workers 表中的 id 列的值。

這兩張示意圖中 B+tree 的度設(shè)置為了 3 ，這也主要是為了方便演示。

實(shí)際的 B+tree 索引中，樹的度通常會(huì)大于 100。

說了聚簇索引和二級(jí)索引 肯定要提到「回表查詢」。

由于二級(jí)索引的葉子節(jié)點(diǎn)不存儲(chǔ)完整的表數(shù)據(jù)，所以當(dāng)通過二級(jí)索引查詢到聚簇索引的列值后，還需要回到局促索引也就是表數(shù)據(jù)本身進(jìn)一步獲取數(shù)據(jù)。

比如說我們要在 workers 表中查詢 名叫呂歸塵的人

select?*?from?workers?where?name='呂歸塵';

這條 SQL 通過 name='呂歸塵'的條件

在二級(jí)索引 index_name 中查詢到主鍵 id=8 ，接著帶著 id=8 這個(gè)條件

進(jìn)一步回到聚簇索引查詢以后才能獲取到完整的數(shù)據(jù)，很顯然回表需要額外的 B+tree 搜索過程，必然增大查詢耗時(shí)。

需要注意的是通過二級(jí)索引查詢時(shí)，回表不是必須的過程，當(dāng) Query 的所有字段在二級(jí)索引中就能找到時(shí)，就不需要回表，MySQL 稱此時(shí)的二級(jí)索引為覆蓋索引或稱觸發(fā)了 「索引覆蓋」。

select?id,name?from?workers?where?name='呂歸塵';

這句 SQL 只查詢了 id，和 name，二級(jí)索引就已經(jīng)包含了 Query 所以需要的所有字段，就無需回表查詢。

explain?select?id,name?from?workers?where?name='呂歸塵';

使用 explain 查看此條 SQL 的執(zhí)行計(jì)劃

執(zhí)行計(jì)劃的 Extra 字段中出現(xiàn)了 Using where;Using index 表明查詢觸發(fā)了索引 index_name 的索引覆蓋，且對(duì)索引做了 where 篩選，這里不需要回表。

下面做對(duì)比，查詢一下沒有索引的

explain?select?id,name,sales?from?workers?where?name='呂歸塵';

Extra 為 Using Index Condition 表示會(huì)先條件過濾索引，過濾完索引后找到所有符合索引條件的數(shù)據(jù)行，隨后用 WHERE 子句中的其他條件去過濾這些數(shù)據(jù)行。Index Condition Pushdown (ICP)是 MySQL 5.6 以上版本中的新特性，是一種在存儲(chǔ)引擎層使用索引過濾數(shù)據(jù)的一種優(yōu)化方式。ICP 開啟時(shí)的執(zhí)行計(jì)劃含有 Using index condition 標(biāo)示 ，表示優(yōu)化器使用了 ICP 對(duì)數(shù)據(jù)訪問進(jìn)行優(yōu)化。

如果你對(duì)此感興趣去查閱對(duì)應(yīng)的官方文檔和技術(shù)博客。

這次我們簡(jiǎn)化來理解，不考慮 ICP 對(duì)數(shù)據(jù)訪問的優(yōu)化，當(dāng)關(guān)閉 ICP 時(shí)，Index 僅僅是 data access 的一種訪問方式，存儲(chǔ)引擎通過索引回表獲取的數(shù)據(jù)會(huì)傳遞到 MySQL Server 層進(jìn)行 WHERE 條件過濾。

Extra 為 Using where 只是提醒我們 MySQL 將用 where 子句來過濾結(jié)果集。這個(gè)一般發(fā)生在 MySQL 服務(wù)器，而不是存儲(chǔ)引擎層。一般發(fā)生在不能走索引掃描的情況下或者走索引掃描，但是有些查詢條件不在索引當(dāng)中的情況下。

這里表明沒有觸發(fā)索引覆蓋，進(jìn)行回表查詢。

MyISAM 的索引

說完了 InnoDB 的索引，接下來我們來看 MyISAM 的索引

以 MyISAM 存儲(chǔ)引擎存儲(chǔ)的表不存在聚簇索引。

MyISAM 表中的主鍵索引和非主鍵索引的結(jié)構(gòu)是一樣的，從上圖中我們可以看到

他們的葉子節(jié)點(diǎn)是不存儲(chǔ)表數(shù)據(jù)的，節(jié)點(diǎn)中存放的是表數(shù)據(jù)的地址，所以 MyISAM 表可以沒有主鍵。

MyISAM 表的數(shù)據(jù)和索引是分開的，是單獨(dú)存放的。

MyISAM 表中的主鍵索引和非主鍵索引的區(qū)別僅在于主鍵索引 B+tree 上的 key 必須符合主鍵的限制，

非主鍵索引 B+tree 上的 key 只要符合相應(yīng)字段的特性就可以了。

索引字段特性角度看索引

「主鍵索引」

• 建立在主鍵字段上的索引
• 一張表最多只有一個(gè)主鍵索引
• 索引列值不允許為 null
• 通常在創(chuàng)建表的時(shí)候一起創(chuàng)建

「唯一索引」

• 建立在 UNIQUE 字段上的索引就是唯一索引
• 一張表可以有多個(gè)唯一索引，索引列值允許為 null

我們演示創(chuàng)建索引

create?table?persons
?(
?????id???int(11)?not?null?auto_increment?comment?'主鍵id',
?????eno??int(11)?comment?'工號(hào)',
?????eid??int(11)?comment?'身份證號(hào)',
?????veid?int(11)?comment?'虛擬身份證號(hào)',
?????name?varchar(16)?comment?'名字',
?????primary?key?(id)?comment?'主鍵索引',
?????UNIQUE?key?(eno)?comment?'eno唯一索引',
?????UNIQUE?key?(eid)?comment?'eid唯一索引'
?)?engine?=?InnoDB
???auto_increment?=?1000
???default?charset?=?utf8;
?alter?table?persons
?????add?unique?index?index_veid?(veid)?comment?'veid唯一索引';

通過 show index from persons;命令我們看到已經(jīng)成功創(chuàng)建了三個(gè)唯一索引。

普通索引

主鍵索引和唯一索引對(duì)字段的要求是要求字段為主鍵或 unique 字段，

而那些建立在普通字段上的索引叫做普通索引，既不要求字段為主鍵也不要求字段為 unique。

前綴索引

前綴索引是指對(duì)字符類型字段的前幾個(gè)字符或?qū)ΧM(jìn)制類型字段的前幾個(gè) bytes 建立的索引，而不是在整個(gè)字段上建索引。

例如，可以對(duì) persons 表中的 name(varchar(16))字段 中 name 的前 5 個(gè)字符建立索引。

create?index?index_name?on?persons?(name(5))?comment?'前綴索引';
show?index?from?persons;

前綴索引可以建立在類型為

• char
• varchar
• binary
• varbinary

的列上，可以大大減少索引占用的存儲(chǔ)空間，也能提升索引的查詢效率。

索引列的個(gè)數(shù)角度看索引

• 建立在單個(gè)列上的索引為單列索引

• 
  
• 
  
• 上文演示的都是單列索引

• 建立在多列上的稱為聯(lián)合索引（復(fù)合索引）

演示一下聯(lián)合索引create index index_id_name on workers(id,name) comment '組合索引';這條語句在我們演示表 workers 中建立 id，name 這兩個(gè)字段的聯(lián)合索引。借助 show index 命令查看索引的詳細(xì)信息 操作后結(jié)果如下：

雖然詳細(xì)信息當(dāng)中列出了兩條關(guān)于聯(lián)合索引的條目，但并不表示聯(lián)合索引是建立了多個(gè)索引，聯(lián)合索引是一個(gè)索引結(jié)構(gòu)，這兩個(gè)條目表示的是組合索引中字段的具體信息，按建立索引時(shí)的書寫順序排序。

同樣我們來看下聯(lián)合索引的 B+tree 示意圖

從圖中看到組合索引的非葉子節(jié)點(diǎn)保存了兩個(gè)字段的值作為 B+tree 的 key 值，當(dāng) B+tree 上插入數(shù)據(jù)時(shí)，先按字段 id 比較，在 id 相同的情況下按 name 字段比較。

加鋒哥微信:?java3459??
圍觀鋒哥朋友圈，每天推送Java干貨！