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