引言

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

本文我們就先從最簡單的索引開始吧～

1. 什么是索引

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

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

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

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

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

2.1 B+Tree 和 B-Tree

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• B-Tree 則是左開右開。

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

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

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

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

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

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

2.2 樹高問題

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

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

通過如下命令我們可以查看 MySQL 中 InnoDB 存儲引擎邏輯頁的大小：

16384/16=1024

前面的結(jié)論沒問題。

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

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

16*1024/(8+6)=1170

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

1170*1170*16=21902400

可以存儲 2100萬 條數(shù)據(jù)。

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

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

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

• 全值匹配

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

• 最左匹配

如果我們只是想搜索 username 為 ac 的用戶，很明顯也可以使用上圖索引，因為用戶名是有序的。在上圖中，username 和 age 組成了聯(lián)合索引，其中 username 在前，age 在后，所以索引是先按照 username 進(jìn)行排序，username 相同的時候，再按照 age 進(jìn)行排序的（如 bw 這個用戶），如果我們按照 username 進(jìn)行搜索，那么沒問題，可以用上索引；但是如果我們按照 age 進(jìn)行搜索，很明顯，age 在整個索引樹中是無序的，所以當(dāng)我們使用 age 作為搜索條件的時候，是沒法使用上圖這個聯(lián)合索引的。

• 前綴匹配

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

• 范圍匹配

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

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

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

• 覆蓋索引

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

2.4 使用限制

毫無疑問，基于 B+Tree 的索引，其實也存在一些使用限制。例如：

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

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

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

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

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

對于第三點，如果范圍搜索的字段值的可能性比較少，則可以通過多個等于比較來代替范圍搜索。

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

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

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

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

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

3. 小結(jié)

整體上來說，使用索引有如下優(yōu)點：

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

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

最新評論