引言

之前松哥寫(xiě)過(guò)一個(gè) MySQL 系列，但是當(dāng)時(shí)是基于 MySQL5.7 的，最近有空在看 MySQL8 的文檔，發(fā)現(xiàn)和 MySQL5.7 相比還是有不少變化，同時(shí) MySQL 又是小伙伴們?cè)诿嬖嚂r(shí)一個(gè)非常重要的知識(shí)點(diǎn)，因此松哥打算最近再抽空和小伙伴們聊一聊 MySQL，講講原理，講講優(yōu)化，我會(huì)從最基本最簡(jiǎn)單的開(kāi)始，和大家梳理 MySQL 中常見(jiàn)的面試知識(shí)點(diǎn)。

本文我們就先從最簡(jiǎn)單的索引開(kāi)始吧～

1. 什么是索引

說(shuō)到索引，最常見(jiàn)的例子就是查字典，當(dāng)我們需要查詢某一個(gè)字的含義時(shí)，正常操作都是先根據(jù)字典的索引，找到該字在哪一頁(yè)，然后直接翻到該頁(yè)就行了。如果沒(méi)有這個(gè)索引的話，那么我們就得一頁(yè)一頁(yè)的翻字典，直到找到該字。很明顯，相對(duì)于第一種方案，第二種方案效率就要低很多了。

數(shù)據(jù)庫(kù)中的索引也是類似的。

索引，我們也稱之為 index 或者 key，當(dāng)數(shù)據(jù)量比較少的時(shí)候，索引對(duì)于查詢產(chǎn)生的效果并不明顯，所以索引常常被人所忽略，但是當(dāng)數(shù)據(jù)量比較大的時(shí)候，一個(gè)優(yōu)秀的索引對(duì)查詢產(chǎn)生的影響就是非常明顯的了。在我們所掌握的各種 SQL 優(yōu)化策略中，索引對(duì) SQL 優(yōu)化產(chǎn)生的效果算是最好的了，用好索引，SQL 性能可能會(huì)提升好幾個(gè)數(shù)量級(jí)。

這里有的小伙伴可能會(huì)有一個(gè)疑惑，很多索引優(yōu)化策略都是針對(duì)傳統(tǒng)的機(jī)械硬盤的，然而現(xiàn)在我們大部分都是固態(tài)硬盤（SSD），很多針對(duì)機(jī)械硬盤的優(yōu)化策略在 SSD 上似乎并沒(méi)有必要，那還有必要去考慮索引優(yōu)化嗎？答案當(dāng)然是有！無(wú)論是用什么樣的磁盤，索引優(yōu)化的整體原則都是不變的，只不過(guò)在 SSD 上，如果你的索引沒(méi)有創(chuàng)建好，那么它對(duì)查詢的影響不像對(duì)機(jī)械硬盤那么糟糕。

2. 索引的數(shù)據(jù)結(jié)構(gòu)

2.1 B+Tree 和 B-Tree

小伙伴們知道，由于 MySQL 中的存儲(chǔ)引擎設(shè)計(jì)成了可插拔的形式，任何機(jī)構(gòu)和個(gè)人如果你有能力，都可以設(shè)計(jì)自己的存儲(chǔ)引擎，而 MySQL 的索引是在存儲(chǔ)引擎層實(shí)現(xiàn)的，而不是在服務(wù)器層實(shí)現(xiàn)的，所以不同存儲(chǔ)引擎的索引工作方式都不一樣，甚至，相同類型的索引，在不同的存儲(chǔ)引擎中實(shí)現(xiàn)方案都不同。

本文松哥主要和小伙伴們介紹我們?nèi)粘ｉ_(kāi)發(fā)中最最常見(jiàn)的 InnoDB 存儲(chǔ)引擎中的索引。

小伙伴們知道，InnoDB 存儲(chǔ)引擎的索引數(shù)據(jù)結(jié)構(gòu)是一個(gè) B+Tree，至于什么是 B+Tree，這并非本文的重點(diǎn)，我這里不啰嗦，不了解 B+Tree 的小伙伴可以自行搜索一下學(xué)習(xí)一下。

假設(shè)我有如下數(shù)據(jù)：

現(xiàn)在我給 username 和 age 字段建立聯(lián)合索引，那么最終數(shù)據(jù)在磁盤上的存儲(chǔ)結(jié)構(gòu)是 B+Tree，為了小伙伴能夠更好的理解 B+Tree 和 B-Tree，我畫(huà)了如下兩張圖：

這兩張圖看懂了，InnoDB 存儲(chǔ)引擎的索引我覺(jué)得基本上都搞懂了 80% 了，松哥來(lái)和大家稍微梳理一下這張圖：

• 首先這兩張圖都是一個(gè)多路平衡查找樹(shù)，即，不是二叉樹(shù)，是多叉樹(shù)。
• 綠色的方塊表示指向下一個(gè)節(jié)點(diǎn)的指針；紅色的方塊表示指向下一個(gè)葉子節(jié)點(diǎn)的指針（B-Tree 中不存在該部分）；帶陰影的矩形則表示索引數(shù)據(jù)。

• B+Tree 非葉子節(jié)點(diǎn)只保存關(guān)鍵字的索引和指向下一個(gè)節(jié)點(diǎn)的指針（綠色區(qū)域），所有的數(shù)據(jù)最終都會(huì)保存到葉子節(jié)點(diǎn)。因此在具體的搜索過(guò)程中，所有數(shù)據(jù)都必須要到葉子節(jié)點(diǎn)才能獲取到，因此每次數(shù)據(jù)查詢所需的 IO 次數(shù)都一樣，這也就意味著 B+Tree 的查詢速度比較穩(wěn)定。

• 如果是 B-Tree 則分支節(jié)點(diǎn)上也保存了指向具體數(shù)據(jù)的指針，并且分支節(jié)點(diǎn)上出現(xiàn)的索引數(shù)據(jù)不會(huì)再次出現(xiàn)在葉子節(jié)點(diǎn)中，所以搜索的時(shí)候可能搜索到分支節(jié)點(diǎn)就找到需要的數(shù)據(jù)了，搜索效率不穩(wěn)定，如 af 在分支節(jié)點(diǎn)上就找到了，而 ac 則要到葉子節(jié)點(diǎn)上才能找到）。

• B+Tree 中，由于分支節(jié)點(diǎn)只保存索引數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針，所以在相同的磁盤空間中，能夠指向更多的子節(jié)點(diǎn)，這就意味樹(shù)的高度更低，搜索所需要的 IO 次數(shù)更少，搜索效率更高。

• B-Tree 中，由于分支節(jié)點(diǎn)不僅保存索引數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針，還保存了指向具體數(shù)據(jù)的指針，所以在相同的空間下能夠指向的子節(jié)點(diǎn)數(shù)量就少于 B+Tree，這就意味著相同的數(shù)據(jù)量，B-Tree 樹(shù)高更高，搜索所需的 IO 次數(shù)更多，搜索效率低。

• B+Tree 葉子節(jié)點(diǎn)的關(guān)鍵字從小到大按順序排列，左邊結(jié)尾數(shù)據(jù)都會(huì)保存右邊節(jié)點(diǎn)開(kāi)始數(shù)據(jù)的指針（紅色區(qū)域），這個(gè)指針在范圍搜索的時(shí)候非常有用，例如想搜索姓名在 ac～bc 之間的數(shù)據(jù)，按照樹(shù)找到第一個(gè)節(jié)點(diǎn) ac 之后，順著指針一直往后找，找到第一個(gè)不滿足條件的數(shù)據(jù)結(jié)束。

• 如果是 B-Tree 則沒(méi)有 ac 指向 bc 的指針，需要先回到分支節(jié)點(diǎn) af 再繼續(xù)向下搜索，效率就會(huì)低很多。

• B+Tree 的葉子節(jié)點(diǎn)都是有序排列的，所以 B+Tree 對(duì)于數(shù)據(jù)的排序有著更好的支持。

• B-Tree 由于有一部分?jǐn)?shù)據(jù)保存在分支節(jié)點(diǎn)中，葉子節(jié)點(diǎn)并不是完整的數(shù)據(jù)，所以對(duì)于排序、范圍搜索的支持并不如 B+Tree。

• B+Tree 數(shù)據(jù)劃分的原則是左閉右開(kāi)，以 (af,88) 這個(gè)節(jié)點(diǎn)為例，小于 (af,88) 節(jié)點(diǎn)的在左邊，大于等于 (af,88) 節(jié)點(diǎn)的在右邊。

• B-Tree 則是左開(kāi)右開(kāi)。

• B+Tree 全表掃描更快，因?yàn)樗袛?shù)據(jù)都出現(xiàn)在葉子節(jié)點(diǎn)上，并且葉子節(jié)點(diǎn)之間還有指針相連，直接遍歷即可。

• B-Tree 在全表掃描的時(shí)候則需要對(duì)樹(shù)的每一層進(jìn)行遍歷才能讀到所有數(shù)據(jù)。

• 葉子節(jié)點(diǎn)指向數(shù)據(jù)的指針，如果是聚簇索引，則指向的是表中一條完整的記錄；如果是非聚簇索引，則指向的是具體的主鍵值。在以非聚簇索引為依據(jù)進(jìn)行搜索的時(shí)候，先找到記錄的主鍵值，再根據(jù) 主鍵值去聚簇索引找到完整的記錄，這個(gè)過(guò)程就是回表（InnoDB 中）。

好了，相信通過(guò)上面八點(diǎn)的介紹，大家對(duì)于 B-Tree 和 B+Tree 已經(jīng)有了基本的認(rèn)知了。

當(dāng)我們想要搜索一條記錄的時(shí)候，順著根節(jié)點(diǎn)從上往下掃描樹(shù)，比直接遍歷一條一條的記錄顯然是要快很多。

說(shuō)一個(gè)不太恰當(dāng)?shù)谋扔?，MySQL 中的數(shù)據(jù)存儲(chǔ)，就像是通過(guò)一個(gè)鏈表把所有數(shù)據(jù)按照順序串到一起，然后在這個(gè)鏈表上面又架了一個(gè)多路平衡查找樹(shù)的感覺(jué)，搜索的時(shí)候，按照鏈表一個(gè)一個(gè)找，就是全表掃描；從樹(shù)的根節(jié)點(diǎn)開(kāi)始找，就是用索引。

2.2 樹(shù)高問(wèn)題

一個(gè)經(jīng)典的問(wèn)題，高度為 3 的 B+Tree 大概可以保存多少條數(shù)據(jù)？

計(jì)算機(jī)在存儲(chǔ)數(shù)據(jù)的時(shí)候，最小存儲(chǔ)單元是扇區(qū)，一個(gè)扇區(qū)的大小是 512 字節(jié)，而文件系統(tǒng)（例如 XFS/EXT4）最小單元是塊，一個(gè)塊的大小是 4KB。但是 InnoDB 在進(jìn)行磁盤操作的時(shí)候，并不是以扇區(qū)或者塊為依據(jù)的，InnoDB 在進(jìn)行磁盤操作的時(shí)候，是以頁(yè)為單位的，有時(shí)候也稱作邏輯頁(yè)，每個(gè)邏輯頁(yè)的大小默認(rèn)是 16KB，即四個(gè)塊。這就意味著，InnoDB 在實(shí)際操作磁盤的時(shí)候，每次從磁盤上讀取數(shù)據(jù)，至少讀取 16KB，每次向磁盤上寫(xiě)數(shù)據(jù)，也至少寫(xiě) 16KB，并不是你需要 1KB 就讀取 1KB，即使你只需要 1KB 的數(shù)據(jù)，InnoDB 也會(huì)從磁盤中將 16KB 的數(shù)據(jù)讀取到內(nèi)存中。

通過(guò)如下命令我們可以查看 MySQL 中 InnoDB 存儲(chǔ)引擎邏輯頁(yè)的大小：

16384/16=1024

前面的結(jié)論沒(méi)問(wèn)題。

以聚簇索引為例，現(xiàn)在我們假設(shè)數(shù)據(jù)庫(kù)中一條記錄的大小是 1KB，那么一個(gè)邏輯頁(yè)就可以存 16 條數(shù)據(jù)（葉子節(jié)點(diǎn)）。

對(duì)于非葉子節(jié)點(diǎn)存儲(chǔ)的則是主鍵值+指針，在 InnoDB 中，一個(gè)指針的大小是 6 個(gè)字節(jié)，假設(shè)我們的主鍵是 bigint ，那么主鍵占 8 個(gè)字節(jié)，當(dāng)然還有其他一些頭信息也會(huì)占用字節(jié)我們這里就不考慮了，我們大概算一下，小伙伴們心里有數(shù)即可：

16*1024/(8+6)=1170

即一個(gè)非葉子節(jié)點(diǎn)可以指向 1170 個(gè)子節(jié)點(diǎn)，那么一個(gè)三層的 B+Tree 可以存儲(chǔ)的數(shù)據(jù)量為：

1170*1170*16=21902400

可以存儲(chǔ) 2100萬(wàn) 條數(shù)據(jù)。

在 InnoDB 存儲(chǔ)引擎中，B+Tree 的高度一般為 2-4 層，這就可以滿足千萬(wàn)級(jí)的數(shù)據(jù)的存儲(chǔ)，查找數(shù)據(jù)的時(shí)候，一次頁(yè)的查找代表一次 IO，那我們通過(guò)主鍵索引查詢的時(shí)候，其實(shí)最多只需要 2-4 次 IO 操作就可以了。

2.3 什么樣的搜索可以用到索引？

根據(jù)前面的介紹，我們可以得出結(jié)論，在以下類型的搜索中，會(huì)用到索引：

• 全值匹配

如上圖中，如果我們要搜索 username 為 ac 且 age 為 98 的用戶，就可以直接使用索引精確定位到。

• 最左匹配

如果我們只是想搜索 username 為 ac 的用戶，很明顯也可以使用上圖索引，因?yàn)橛脩裘怯行虻?。在上圖中，username 和 age 組成了聯(lián)合索引，其中 username 在前，age 在后，所以索引是先按照 username 進(jìn)行排序，username 相同的時(shí)候，再按照 age 進(jìn)行排序的（如 bw 這個(gè)用戶），如果我們按照 username 進(jìn)行搜索，那么沒(méi)問(wèn)題，可以用上索引；但是如果我們按照 age 進(jìn)行搜索，很明顯，age 在整個(gè)索引樹(shù)中是無(wú)序的，所以當(dāng)我們使用 age 作為搜索條件的時(shí)候，是沒(méi)法使用上圖這個(gè)聯(lián)合索引的。

• 前綴匹配

如果我們搜索的關(guān)鍵字只是 username 字段的前半部分，那么很明顯，也是可以使用索引的，例如搜索所有以 a 開(kāi)始的 username。

• 范圍匹配

如果我們的搜索條件是一個(gè)范圍，很明顯也可以使用到上述索引，例如搜索姓名介于 ab～cc 之間的用戶，只需要先從索引樹(shù)的根節(jié)點(diǎn)開(kāi)始，先找到 ab，然后根據(jù)葉子節(jié)點(diǎn)之間的指針順藤摸瓜，找到 cc 之后的第一個(gè)數(shù)據(jù)（不滿足條件的第一個(gè)數(shù)據(jù)）結(jié)束。

• 前面全值匹配，后面范圍匹配

例如查找 username 為 bw 且 age 介于 90～99 之間的用戶，這種情況也可以使用到上圖的索引。在上圖索引樹(shù)中，當(dāng) username 相同的時(shí)候，就是按照 age 排序的，所以對(duì)于 username 都為 bw 的用戶，它就是按照 age 進(jìn)行排序的，此時(shí)，我們當(dāng)然可以按照 age 的范圍進(jìn)行搜索了。

• 覆蓋索引

有的時(shí)候，我們搜索的數(shù)據(jù)都在索引樹(shù)中了，例如上圖中的索引，我們想搜索 username 為 bw 的用戶的 age，由于 age 就在索引樹(shù)中，直接返回即可，這就是覆蓋索引了。

2.4 使用限制

毫無(wú)疑問(wèn)，基于 B+Tree 的索引，其實(shí)也存在一些使用限制。例如：

• 如果我們將 age 作為搜索條件，雖然 age 也是聯(lián)合索引的一部分，但是 age 整體上在索引樹(shù)中是無(wú)序的，所以將 age 作為搜索條件是沒(méi)法使用上述索引的。
• 基于第一點(diǎn)，如果聯(lián)合索引中還有第三、第四列等，那么凡是跳過(guò)第一列直接使用后面的列作為查詢條件，索引都是不會(huì)生效的。
• 范圍條件的右邊無(wú)法使用索引直接定位。例如搜索 username 以 a 開(kāi)頭并且年齡為 99 的用戶：where username like 'a%' and age=99，此時(shí) age=99 這個(gè)條件就無(wú)法在索引樹(shù)中直接處理了（可以通過(guò)索引下推過(guò)濾）。原因很簡(jiǎn)單，當(dāng)我們找到所有 username 以 a 開(kāi)始的用戶之后，這些用戶的 age 并不是有序的，所以 age 就沒(méi)法繼續(xù)使用索引搜索了（但是可以通過(guò)索引下推過(guò)濾）。

關(guān)于第三點(diǎn)，我舉一個(gè)例子，假設(shè)我們還有兩個(gè)用戶，分別是：

• username 為 ad 且 age 為 80；
• username 為 ae 且 age 為 88；

那么我們完善一下上面 B+Tree 的圖應(yīng)該變成下面這樣：

可以看到，username 以 a 開(kāi)始的用戶，age 并不是有序的，所以就只能通過(guò)索引下推過(guò)濾了，而無(wú)法直接通過(guò)索引掃描定位數(shù)據(jù)。

對(duì)于第三點(diǎn)，如果范圍搜索的字段值的可能性比較少，則可以通過(guò)多個(gè)等于比較來(lái)代替范圍搜索。

2.5 自適應(yīng)哈希索引

Hash 索引在 MySQL 中主要是 Memory 和 NDB 引擎支持，InnoDB 索引本身是 不支持的，但是 InnoDB 索引有一個(gè)特性叫做自適應(yīng)哈希索引，自適應(yīng)三個(gè)字意味著整個(gè)過(guò)程是全自動(dòng)的，不需要開(kāi)發(fā)者配置。

當(dāng) InnoDB 監(jiān)控到某些索引值被頻繁的訪問(wèn)時(shí)，那么它就會(huì)在 B+Tree 索引之上，構(gòu)建一個(gè) Hash 索引，進(jìn)而通過(guò) Hash 查找來(lái)快速訪問(wèn)數(shù)據(jù)。

默認(rèn)情況下，自適應(yīng)哈希索引是開(kāi)啟的狀態(tài)，通過(guò)如下 SQL 我們可以查看：

可以看到，這個(gè)默認(rèn)就是開(kāi)啟的。

3. 小結(jié)

整體上來(lái)說(shuō)，使用索引有如下優(yōu)點(diǎn)：

• 減少了服務(wù)器需要掃描的數(shù)據(jù)量。
• 索引可以幫助服務(wù)器避免排序和創(chuàng)建臨時(shí)表。
• 索引將隨機(jī) IO 變?yōu)榱隧樞?IO。

以上就是MySQL索引數(shù)據(jù)結(jié)構(gòu)入門詳細(xì)教程的詳細(xì)內(nèi)容，更多關(guān)于MySQL索引數(shù)據(jù)結(jié)構(gòu)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！