阿竺 ·1. 前言
對于常見的應用系統，讀的流量遠遠高于寫的流量，比如電商網站，商家在數據庫中寫入商品的價格和庫存之后，訪問頁面的顧客會產生大部分的讀流量。所以常見的現象是當應用系統的流量逐漸增加時，寫操作不會成為數據庫的性能瓶頸，但是復雜查詢語句消耗的查詢時間會越來越長，讀操作更容易觸碰數據庫的查詢性能瓶頸。MySQL 自身為了優化查詢效率，更快的查詢目標集合，定義了索引，也就是常用的 "鍵"（Key），MySQL 中的索引是單獨存儲在磁盤上的數據結構，使用索引可以快速查詢滿足特定條件的記錄。
2. 談一談 InnoDB 存儲引擎的索引數據結構
2.1 不同引擎的數據結構
面試官提問： MySQL 中 InnoDB 存儲引擎底層的數據結構是什么？
題目解析：
以 MySQL 5.7 為例，首先查詢官方文檔，可以發現存儲引擎和索引數據結構的對應關系，例如 InnoDB 對應 BTREE 索引，MEMORY 存儲引擎對應哈希索引和 BTREE 索引，注意這里的 BTREE 實際指代的是 B+ 樹，我們重點關注樹的數據結構。
2.2 B 樹和 B + 樹
如果能正確回答 InnoDB 索引的底層數據結構是 B+ 樹，面試官接下來可能會先考察候選人對數據結構本身的理解程度。
面試官：學過數據結構課程的同學，應該都聽過 B 樹和 B+ 樹吧，這兩種樹有什么區別呢？
題目解析：我們盡量需要通過在白紙上畫出 B 樹和 B+ 樹，畫圖的同時給面試官解釋兩種樹的區別，需要從數據結構、優缺點方面分析（一般來說不需要深入到節點的插入和刪除流程，因為比較復雜）
首先我們畫出一個簡化后的 B 樹，如下圖：
?
參考上圖，我們定義一個 m 階的 B 樹的數據結構：
① 根結點至少有兩個子節點；
② 除了根節點外，每個子節點都包含 n-1 個元素（數據）和 n 個子節點指針，其中 m/2 <= n <= m；
③ 所有的葉子結點都位于同一層；
④ 有序性：每個節點中的元素從小到大排列，節點當中 k-1 個元素正好是 k 個孩子包含的元素的值域分劃。
畫出 B 樹只是為了襯托 B+ 樹，B 樹不會是面試的重點，接下來我們在白紙上畫出一個典型的 B+ 樹結構：
?
對于一個 m 階的 B+ 樹，基本定義同 B 樹相同：
① 除了根之外的每個節點都包含最少 m/2 個元素最多 m-1 個元素，對于任意的結點有最多 m 個子指針；
② 所有的葉子節點都在同一層；
除此之外，B+ 樹相對于 B 樹，需要特別區分的不同點有：
① 數據存儲方式不同：B+ 樹中間節點并不存儲真正的數據，而是保存其葉子節點中最小值作為索引。例如上圖中磁盤塊 2 和磁盤塊 3 中并沒有黃色的 data 節點；
② 數據查找方式不同：每個葉子節點存在一個 next 指針，指向下一個葉子節點，形成了有序雙向鏈表，從圖中能明顯看出來。所以 B 樹只能由根節點往下二分查找，B+ 樹除了這種查找方式，還支持在葉子節點中直接順序遍歷查找。
2.3 為什么使用 B + 樹
在給面試官闡述清楚了 B 樹和 B+ 樹數據結構的區別之后，接下來面試官大概率會追根溯源，引出更深一步的問題：
** 面試官：** 你能說說為什么 MySQL 要選擇 B+ 樹作為索引的數據結構實現嗎？
題目解析：
結合我們畫出的數據結構圖示，這個問題翻譯過來其實是相對于 B 樹，為什么要選擇 B+ 樹？
首先要分析數據庫的讀寫瓶頸受限原因：計算機的存儲是分層次的，CPU 里的 Cache 訪問速度最快，速度更慢的是內存（容量小，斷電情況下數據會丟失），讀寫最慢的是硬盤（容量大，數據可長期存儲）。MySQL 的數據是持久化存儲在硬盤中的，硬盤訪問慢是因為：CPU 訪問硬盤時會經過三個耗時步驟：
（1）尋道耗時：磁臂移動到磁道；
（2）旋轉耗時：例如一個 7200 轉的磁盤，表示每分鐘能轉 7200 次；
（3）數據傳輸耗時：從磁盤讀出數據或者寫入數據的過程。前兩者都依賴于磁盤的機械運動，耗時非常久。所以磁盤 I/O 是一種非常昂貴的操作，數據庫的讀寫操作需要經過盡可能少的磁盤 I/O。
我們在這個硬件基礎上，我們依據 B 樹的圖示，模擬查詢關鍵詞 6 的一次查詢過程：
（1）磁盤第一次 I/O 操作：找到磁盤塊 1，讀入內存；
（2）磁盤第二次 I/O 操作：比較關鍵詞 6 在區間（0，7）之間，找到磁盤塊 1 的左指針，根據指針找到磁盤塊 2，讀入內存；
（3） 磁盤第三次 I/O 操作：比較關鍵詞 6 在區間（5，7）之間，找到磁盤塊 2 的最右側指針，根據指針找到磁盤塊 6，讀入內存；
（4） 尋找關鍵詞：在磁盤塊 6 中找到關鍵詞 6，以及對應 data 數據。
可以發現，樹的深度越深，查找需要的磁盤 I/O 次數就越多?，F在我們再來分析 B + 樹的優勢：
（1） B + 樹的磁盤 I/O 次數相對更少：利用 B 樹 / B+ 樹的有序性，從根節點每往子節點每查找一次，都要經過一次磁盤 I/O。相對 B 樹，B+ 樹的內部節點只包含下級指針，并不存放數據信息，所以對于同樣大小的磁盤塊，能夠存儲的記錄個數更多（樹的階 m 更大），B+ 樹的深度更低，所以磁盤 I/O 次數更少。
（2） B+ 樹更適合范圍查找：在進行范圍查詢時，B 樹查詢只能通過從根節點開始的遞歸查詢，因為相鄰節點在硬盤中不一定連續，緩存命中率差，而 B+ 樹因為葉子節點形成有序鏈表，可以直接進行線性遍歷。
綜上，回答本題的核心點要抓住：
（1）明確磁盤 I/O 是數據庫讀寫的硬件瓶頸。
（2）能夠結合兩種樹不同的數據結構，分析得到 B+ 樹的優勢。
3. 小結
本章節介紹了 MySQL 中 InnoDB 存儲引擎的底層 B+ 樹數據結構，候選人需要區分 B 樹和 B+ 樹，以及從查詢效率和硬件成本角度分析為什么在 MySQL 中會優選使用 B+ 樹作為支撐。
2025 imooc.com All Rights Reserved |