[[440384]]

本文轉載自微信公眾號「小林coding」，作者小林coding 。轉載本文請聯系小林coding公眾號。

大家好，我是小林。

大家背八股文的時候，都知道 MySQL 里 InnoDB 存儲引擎是采用 B+ 樹來組織數據的。

這點沒錯，但是大家知道 B+ 樹里的節點里存放的是什么呢?查詢數據的過程又是怎樣的?

這次，我們從數據頁的角度看 B+ 樹，看看每個節點長啥樣。

InnoDB 是如何存儲數據的?

MySQL 支持多種存儲引擎，不同的存儲引擎，存儲數據的方式也是不同的，我們最常使用的是 InnoDB 存儲引擎，所以就跟大家圖解下InnoDB 是如何存儲數據的。

記錄是按照行來存儲的，但是數據庫的讀取并不以「行」為單位，否則一次讀取(也就是一次 I/O 操作)只能處理一行數據，效率會非常低。

因此，InnoDB 的數據是按「數據頁」為單位來讀寫的，也就是說，當需要讀一條記錄的時候，并不是將這個記錄本身從磁盤讀出來，而是以頁為單位，將其整體讀入內存。

數據庫的 I/O 操作的最小單位是頁，InnoDB 數據頁的默認大小是 16KB，意味著數據庫每次讀寫都是以 16KB 為單位的，一次最少從磁盤中讀取 16K 的內容到內存中，一次最少把內存中的 16K 內容刷新到磁盤中。

數據頁包括七個部分，結構如下圖：

這 7 個部分的作用如下圖：

在 File Header 中有兩個指針，分別指向上一個數據頁和下一個數據頁，連接起來的頁相當于一個雙向的鏈表，如下圖所示：

采用鏈表的結構是讓數據頁之間不需要是物理上的連續的，而是邏輯上的連續。

數據頁的主要作用是存儲記錄，也就是數據庫的數據，所以重點說一下數據頁中的 User Records 是怎么組織數據的。

數據頁中的記錄按照「主鍵」順序組成單向鏈表，單向鏈表的特點就是插入、刪除非常方便，但是檢索效率不高，最差的情況下需要遍歷鏈表上的所有節點才能完成檢索。

因此，數據頁中有一個頁目錄，起到記錄的索引作用，就像我們書那樣，針對書中內容的每個章節設立了一個目錄，想看某個章節的時候，可以查看目錄，快速找到對應的章節的頁數，而數據頁中的頁目錄就是為了能快速找到記錄。

那 InnoDB 是如何給記錄創建頁目錄的呢?頁目錄與記錄的關系如下圖：

頁目錄創建的過程如下：

• 將所有的記錄劃分成幾個組，這些記錄包括最小記錄和最大記錄，但不包括標記為“已刪除”的記錄;
• 每個記錄組的最后一條記錄就是組內最大的那條記錄，并且最后一條記錄的頭信息中會存儲該組一共有多少條記錄，作為 n_owned 字段(上圖中粉紅色字段)
• 頁目錄用來存儲每組最后一條記錄的地址偏移量，這些地址偏移量會按照先后順序存儲起來，每組的地址偏移量也被稱之為槽(slot)，每個槽相當于指針指向了不同組的最后一個記錄。

從圖可以看到，頁目錄就是由多個槽組成的，槽相當于分組記錄的索引。然后，因為記錄是按照「主鍵值」從小到大排序的，所以我們通過槽查找記錄時，可以使用二分法快速定位要查詢的記錄在哪個槽(哪個記錄分組)，定位到槽后，再遍歷槽內的所有記錄，找到對應的記錄，無需從最小記錄開始遍歷整個頁中的記錄鏈表。

以上面那張圖舉個例子，5 個槽的編號分別為 0，1，2，3，4，我想查找主鍵為 11 的用戶記錄：

• 先二分得出槽中間位是 (0+4)/2=2 ，2號槽里最大的記錄為 8。因為 11 > 8，所以需要從 2 號槽后繼續搜索記錄;
• 再使用二分搜索出 2 號和 4 槽的中間位是 (2+4)/2= 3，3 號槽里最大的記錄為 12。因為 11 < 12，所以主鍵為 11 的記錄在 3 號槽里;
• 再從 3 號槽指向的主鍵值為 9 記錄開始向下搜索 2 次，定位到主鍵為 11 的記錄，取出該條記錄的信息即為我們想要查找的內容。

看到第三步的時候，可能有的同學會疑問，如果某個槽內的記錄很多，然后因為記錄都是單向鏈表串起來的，那這樣在槽內查找某個記錄的時間復雜度不就是 O(n) 了嗎?

這點不用擔心，InnoDB 對每個分組中的記錄條數都是有規定的，槽內的記錄就只有幾條：

• 第一個分組中的記錄只能有 1 條記錄;
• 最后一個分組中的記錄條數范圍只能在 1-8 條之間;
• 剩下的分組中記錄條數范圍只能在 4-8 條之間。

B+ 樹是如何進行查詢的?

上面我們都是在說一個數據頁中的記錄檢索，因為一個數據頁中的記錄是有限的，且主鍵值是有序的，所以通過對所有記錄進行分組，然后將組號(槽號)存儲到頁目錄，使其起到索引作用，通過二分查找的方法快速檢索到記錄在哪個分組，來降低檢索的時間復雜度。

但是，當我們需要存儲大量的記錄時，就需要多個數據頁，這時我們就需要考慮如何建立合適的索引，才能方便定位記錄所在的頁。

為了解決這個問題，InnoDB 采用了 B+ 樹作為索引。磁盤的 I/O 操作次數對索引的使用效率至關重要，因此在構造索引的時候，我們更傾向于采用“矮胖”的 B+ 樹數據結構，這樣所需要進行的磁盤 I/O 次數更少，而且 B+ 樹 更適合進行關鍵字的范圍查詢。

更詳細的為什么采用 B+ 樹作為索引的原因可以看我之前寫的這篇：「索引為什么能提高查詢性能?」

InnoDB 里的 B+ 樹中的每個節點都是一個數據頁，結構示意圖如下：

通過上圖，我們看出 B+ 樹的特點：

• 只有葉子節點(最底層的節點)才存放了數據，非葉子節點(其他上層節)僅用來存放目錄項作為索引。
• 非葉子節點分為不同層次，通過分層來降低每一層的搜索量;
• 所有節點按照索引鍵大小排序，構成一個雙向鏈表，便于范圍查詢;

我們再看看 B+ 樹如何實現快速查找主鍵為 6 的記錄，以上圖為例子：

• 從根節點開始，通過二分法快速定位到符合頁內范圍包含查詢值的頁，因為查詢的主鍵值為 6，在[1, 7)范圍之間，所以到頁 30 中查找更詳細的目錄項;
• 在非葉子節點(頁30)中，繼續通過二分法快速定位到符合頁內范圍包含查詢值的頁，主鍵值大于 5，所以就到葉子節點(頁16)查找記錄;
• 接著，在葉子節點(頁16)中，通過槽查找記錄時，使用二分法快速定位要查詢的記錄在哪個槽(哪個記錄分組)，定位到槽后，再遍歷槽內的所有記錄，找到主鍵為 6 的記錄。

可以看到，在定位記錄所在哪一個頁時，也是通過二分法快速定位到包含該記錄的頁。定位到該頁后，又會在該頁內進行二分法快速定位記錄所在的分組(槽號)，最后在分組內進行遍歷查找。

聚集索引和二級索引

另外，索引又可以分成聚集索引和非聚集索引(二級索引)，它們區別就在于葉子節點存放的是什么數據：

• 聚集索引的葉子節點存放的是實際數據，所有完整的用戶記錄都存放在聚集索引的葉子節點;
• 二級索引的葉子節點存放的是主鍵值，而不是實際數據。

因為表的數據都是存放在聚集索引的葉子節點里，所以 InnoDB 存儲引擎一定會為表創建一個聚集索引，且由于數據在物理上只會保存一份，所以聚簇索引只能有一個。

InnoDB 在創建聚簇索引時，會根據不同的場景選擇不同的列作為索引：

• 如果有主鍵，默認會使用主鍵作為聚簇索引的索引鍵;
• 如果沒有主鍵，就選擇第一個不包含 NULL 值的唯一列作為聚簇索引的索引鍵;
• 在上面兩個都沒有的情況下，InnoDB 將自動生成一個隱式自增 id 列作為聚簇索引的索引鍵;

一張表只能有一個聚簇索引，那為了實現非主鍵字段的快速搜索，就引出了二級索引(非聚簇索引/輔助索引)，它也是利用了 B+ 樹的數據結構，但是二級索引的葉子節點存放的是主鍵值，不是實際數據。

二級索引的 B+ 樹如下圖，數據部分為主鍵值：

因此，如果某個查詢語句使用了二級索引，但是查詢的數據不是主鍵值，這時在二級索引找到主鍵值后，需要去聚簇索引中獲得數據行，這個過程就叫作「回表」，也就是說要查兩個 B+ 樹才能查到數據。不過，當查詢的數據是主鍵值時，因為只在二級索引就能查詢到，不用再去聚簇索引查，這個過程就叫作「索引覆蓋」，也就是只需要查一個 B+ 樹就能找到數據。

總結

InnoDB 的數據是按「數據頁」為單位來讀寫的，默認數據頁大小為 16 KB。每個數據頁之間通過雙向鏈表的形式組織起來，物理上不連續，但是邏輯上連續。

數據頁內包含用戶記錄，每個記錄之間用單項鏈表的方式組織起來，為了加快在數據頁內高效查詢記錄，設計了一個頁目錄，頁目錄存儲各個槽(分組)，且主鍵值是有序的，于是可以通過二分查找法的方式進行檢索從而提高效率。

為了高效查詢記錄所在的數據頁，InnoDB 采用 b+ 樹作為索引，每個節點都是一個數據頁。

如果葉子節點存儲的是實際數據的就是聚簇索引，一個表只能有一個聚簇索引;如果葉子節點存儲的不是實際數據，而是主鍵值則就是二級索引，一個表中可以有多個二級索引。

在使用二級索引進行查找數據時，如果查詢的數據能在二級索引找到，那么就是「索引覆蓋」操作，如果查詢的數據不在二級索引里，就需要先在二級索引找到主鍵值，需要去聚簇索引中獲得數據行，這個過程就叫作「回表」。

關于索引的內容還有很多，比如索引失效、索引優化等等，這些內容我下次在講啦!