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