全面透徹，深刻理解 MySQL 索引

hello，大家好，我是張張，「架構精進之路」公號作者。

對於 MySQL 索引，相信每位後端同學日常工作中經常會用到，但是對其索引原理，卻可能未曾真正深入瞭解。B- 樹和 B+ 樹是 MySQL 索引使用的數據結構，對於索引優化和原理理解都非常重要，下面就揭開 B- 樹和 B+ 樹的神祕面紗，讓大家在面試的時候碰到這個知識點一往無前，不再成爲你前進的羈絆！

本文主要內容：

  1. MySQL 查詢耗時分析，抓性能優化核心問題點

  2. 常見用於查詢的數據結構，性能優劣對比

  3. B-Tree 與 B+Tree 如何選擇，結合場景來做分析更靠譜

  4. InnoDB 中的索引介紹，知己知彼，應用得心應手

一、查詢耗時分析

我們首先進行下查詢耗時分析，抓性能優化核心問題點。

1.1 記錄讀取順序

MYSQL 維護着自己的緩存空間，如果要讀取一條記錄，根據優先順序，路徑如下：

緩存區 => 磁盤緩存區 => 磁盤

1.1.1 緩存區讀取

這是成本最低的方式，可以直接被 CPU 使用，不涉及磁盤 IO，可以考慮 IO 時間爲 0。

1.1.2 從磁盤緩存區讀取

如果磁盤緩存區有需要的記錄，則只需要直接讀出，傳輸時間考慮爲 1ms。

1.1.3 從磁盤讀取

由於 SSD 比較貴，常用的還是機械硬盤，對於機械硬盤，要讀取指定地址的數據，是需要經過尋道的，機械臂需要先移動到指定位置，因此無論讀取多少數據，準備工作都會耗費一段時間。整個 IO 流程包括：排隊等待 => 尋道 => 半圈旋轉 => 傳輸。

一次隨機讀取中，有 90% 的時間都花費在排隊和準備工作，真正的傳輸時間只有 1ms，但總 I/O 時間卻爲 10ms。

當隨機讀取 10 頁，就需要 10*10=100ms，但如果是順序讀，對於傳輸速度爲 40MB/s 的硬盤，讀取一個 4kb 的頁僅需要 0.1ms，即使順序讀取 100 頁，也只需要 1 頁隨機讀 99 頁順序讀，也就是 10ms+9.9ms=19.9ms。

速度差距幾十倍，這也是爲何我們想要儘量保證需要讀取的數據都在物理上排列在一起，因爲這樣就可以順序讀取多個頁，而不需要進行多次隨機讀取。

這樣做的理論依據是計算機科學中著名的局部性原理：

當一個數據被用到時，其附近的數據也通常會馬上被使用。

通過以上分析可知：對於數據讀取速度的優化，主要就是需要降低 IO 時間，而降低 IO 時間的關鍵，就在於減少隨機讀次數以及讀取更少的數據。

二、常見查詢數據結構對比

在此梳理常見用於查詢的數據結構，性能優劣大比拼。

2.1 二叉查找樹

二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。是數據結構中的一類。在一般情況下，查詢效率比鏈表結構要高。

如圖所示：

查詢數據的效率不穩定，若樹左右比較平衡的時，最差情況爲 O(logN)，如果插入數據是有序的，退化爲了鏈表，查詢時間變成了 O(N)。

數據量大的情況下，會導致樹的高度變高，如果每個節點對應磁盤的一個塊來存儲一條數據，需 IO 次數大幅增加，顯然用此結構來存儲數據是不可取的。

2.2 平衡二叉樹（AVL 樹）

平衡二叉樹（Balanced Binary Tree）指的是棵空樹或它的左右兩個子樹的高度差的絕對值不超過 1，並且左右兩個子樹都是一棵平衡二叉樹。

如圖所示：

如果數據都存儲在內存中，採用 AVL 樹來存儲，還是可以的，查詢效率非常高。不過我們的數據是存在磁盤中，用過採用這種結構，每個節點對應一個磁盤塊，數據量大的時候，也會和二叉樹一樣，會導致樹的高度變高，這樣邏輯上很近的節點實際可能非常遠，無法很好的利用磁盤預讀（局部性原理），會增加 IO 次數，顯然用這種結構存儲數據也是不可取的。

2.3 B - 樹

B 樹（英語：B-tree），這裏的 B 表示 balance(平衡的意思)，是一種自平衡的樹，能夠保持數據有序，B - 樹允許每個節點有更多的子節點。

如圖所示：

B - 樹不利於範圍查找，範圍查找也是我們經常用到的，所以 B - 樹也不太適合在磁盤中存儲需要檢索的數據。

2.4 B + 樹

B + 樹是 B - 樹的一個升級版，也是一種多路搜索樹，相對於 B 樹來說 B + 樹更充分的利用了節點的空間，讓查詢速度更加穩定，其速度完全接近於二分法查找。B + 樹元素自底向上插入，這與二叉樹恰好相反。

如圖所示：

如上圖所示，每個節點佔用一個盤塊的磁盤空間，一個節點上有兩個升序排序的關鍵字和三個指向子樹根節點的指針，指針存儲的是子節點所在磁盤塊的地址。

2.5 B-Tree vs B+Tree

對於 B-Tree 和 B+Tree，我們該如何選擇呢？結合場景來做分析更靠譜。

讓我們來想想平時的高頻查詢場景吧，大概存在如下幾種：

  1. 按照 id 查詢唯一一條記錄 

  2. 查找某個範圍的所有記錄

接下來，just do it！

**2.5.1 場景：按照 id 查詢唯一一條記錄 **

B - 樹 模擬查找關鍵字 20 的過程 (3 次 io 操作 + 內存中二分法))：

  1. 根據根節點找到磁盤塊 1，讀入內存。【磁盤 I/O 操作第 1 次】

  2. 比較關鍵字 20 在區間（12，32），找到磁盤塊 1 的指針 P2

  3. 根據 P2 指針找到磁盤塊 3，讀入內存。【磁盤 I/O 操作第 2 次】

  4. 比較關鍵字 20 在區間（15，26），找到磁盤塊 3 的指針 P2

  5. 根據 P2 指針找到磁盤塊 7，讀入內存。【磁盤 I/O 操作第 3 次】

  6. 在磁盤塊 7 中的關鍵字列表中找到關鍵字 20

如果我們是關鍵字 15 的話 , 那就是 2 次 io 操作 + 內存中二分法。但是如果是 B + 樹，就只能通讀到底了。

2.5.2 場景：查找某個範圍的所有記錄

B - 樹要查找 [8，52] 區間的數據，需要訪問 8 個磁盤塊（1/2/6/3/7/8/4/9），IO 次數又上去了。

2.5.3 小結

故 B-Tree vs B+Tree 兩種在索引的區別如下：

1.B-Tree 查找某個關鍵字的效率更高

B-Tree 因爲非葉子結點也保存具體數據，所以在查找某個關鍵字的時候找到即可返回。而 B+Tree 所有的數據都在葉子結點，每次查找都得到葉子結點。所以在同樣高度的 B-Tree 和 B+Tree 中，B-Tree 查找某個關鍵字的效率更高。

2.B-Tree 不利於範圍查詢

由於 B+Tree 所有的數據都在葉子結點，並且結點之間有指針連接，在找大於某個關鍵字或者小於某個關鍵字的數據的時候，B+Tree 只需要找到該關鍵字然後沿着鏈表遍歷就可以了，而 B-Tree 還需要遍歷該關鍵字結點的根結點去搜索。

3.B-Tree 的深度會更大

由於 B-Tree 的每個結點（這裏的結點可以理解爲一個數據頁）都存儲主鍵 + 實際數據，而 B+Tree 非葉子結點只存儲關鍵字信息，而每個頁的大小有限是有限的，所以同一頁能存儲的 B-Tree 的數據會比 B+Tree 存儲的更少。這樣同樣總量的數據，B-Tree 的深度會更大，增大查詢時的磁盤 I/O 次數，進而影響查詢效率。

4.B + 樹的磁盤讀寫代價更低

B + 樹的內部節點並沒有指向關鍵字具體信息的指針，因此其內部節點相對 B 樹更小，如果把所有同一內部節點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多，一次性讀入內存的需要查找的關鍵字也就越多，相對 IO 讀寫次數就降低了。

5.B + 樹的查詢效率更加穩定

由於非終結點並不是最終指向文件內容的結點，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率相當。

三、InnoDB 中的索引

InnoDB 中的索引介紹，知己知彼，應用起來得心應手。

3.1 InnoDB 索引實現

InnoDB 數據頁有 7 個組成部分，各個數據頁可以組成一個雙向鏈表。而每個數據頁中的記錄會按照主鍵值從小到大的順序組成一個單向鏈表，每個數據頁都會爲存儲在它裏邊兒的記錄生成一個頁目錄。在通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應的槽，然後再遍歷該槽對應分組中的記錄即可快速找到指定的記錄。

頁和記錄的關係示意圖如下：

索引同樣存儲在數據頁中，只不過目錄項中的兩個列是主鍵和頁號。

那 InnoDB 怎麼區分一條記錄是普通的用戶記錄還是目錄項記錄呢？是根據記錄頭信息裏的 record_type 屬性，它的各個取值代表的意思如下：

0：普通的用戶記錄

1：目錄項記錄

2：最小記錄

3：最大記錄

3.2 查找步驟

整體結構如下：

現在如果我們想根據主鍵值查找一條用戶記錄大致需要 3 個步驟，以查找主鍵值爲 20 的記錄爲例：

1、確定目錄項記錄頁。

2、通過目錄項記錄頁確定用戶記錄真實所在的頁。

3、在真實存儲用戶記錄的頁中定位到具體的記錄。

四、InnoDB 中的索引分類

InnoDB 中的索引類別介紹，明確後期應用注意事項。

4.1 聚簇索引

上邊介紹的 B + 樹索引。它有兩個特點：

1、根據記錄主鍵值的大小進行記錄和頁的排序

這包括三個方面的含義：

2、B + 樹的葉子節點存儲的是完整的用戶記錄

我們把具有這兩種特性的 B + 樹稱爲聚簇索引，所有完整的用戶記錄都存放在這個聚簇索引的葉子節點處。

4.2 二級索引

上邊介紹的聚簇索引只能在搜索條件是主鍵值時才能發揮作用，因爲 B + 樹中的數據都是按照主鍵進行排序的。

那如果我們想以別的列作爲搜索條件該咋辦呢？

難道只能從頭到尾沿着鏈表依次遍歷記錄麼？

我們可以多建幾棵 B + 樹，不同的 B + 樹中的數據採用不同的排序規則。比方說我們用 c2 列的大小作爲數據頁、頁中記錄的排序規則，再建一棵 B + 樹，效果如下圖所示：

但是但是這個 B + 樹的葉子節點中的記錄只存儲了 c2 和 c1（也就是主鍵）兩個列，所以我們必須再根據主鍵值去聚簇索引中再查找一遍完整的用戶記錄。

由於主鍵值具有唯一性，二級索引不具有唯一性，那麼 新的問題來了：

在上圖中，如果我們想新插入一行記錄，其中 c1、c2、c3 的值分別是：9、1、'c'。

那麼在修改這個爲 c2 列建立的二級索引對應的 B + 樹時便碰到了個大問題：

由於頁 3 中存儲的目錄項記錄是由 c2 列 + 頁號的值構成的，頁 3 中的兩條目錄項記錄對應的 c2 列的值都是 1，而我們新插入的這條記錄的 c2 列的值也是 1，那我們這條新插入的記錄到底應該放到頁 4 中，還是應該放到頁 5 中啊？懵逼了。

爲了讓新插入記錄能找到自己在那個頁裏，我們需要保證在 B + 樹的同一層內節點的目錄項記錄除頁號這個字段以外是唯一的。

所以對於二級索引的內節點的目錄項記錄的內容實際上是由三個部分構成的：1、索引列的值 2、主鍵值 3、頁號。

我們爲 c2 列建立二級索引後的示意圖實際上應該是這樣子的：

4.3 聯合索引

我們可以同時以多個列的大小作爲排序規則，也就是同時爲多個列建立索引，比方說我們想讓 B + 樹按照 c2 和 c3 列的大小進行排序，這個包含兩層含義：

1、先把各個記錄和頁按照 c2 列進行排序；

2、在記錄的 c2 列相同的情況下，採用 c3 列進行排序。

五、總結

MySQL 普遍採用 B+Tree 實現，索引本身很大，不可能全部存儲內存，因此需要以索引文件的形式存儲磁盤。相對於內存讀取，I/O 存取的消耗要高几個數量級，由於 MySQL 數據存儲保存在磁盤中，所以在查詢時磁盤 I/O 是其主要查詢性能瓶頸，而使用索引就可以減少磁盤 I/O。

索引的原理其實是不斷的縮小查找範圍， 就如我們平時用字典查單詞一樣，先找首字母縮小範圍，再第二個字母等等。

對於 B - 樹、B + 樹而言，當高固定情況下，寬度越大索引性能越好。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/LkjsfG-GP7forqSq33awbQ

猜你喜歡