重生之 MySQL B+Tree 提前問世二十年，MySQL之父叫我師父
二叉樹的致命缺陷
場景還原：商品分類表prod_category的父 ID 字段索引。
CREATE TABLE prod_category (
id INT PRIMARY KEY,
parent_id INT,
INDEX idx_parent (parent_id) -- 二叉樹實現
);性能災難：當層級超過 10 層時，查詢子類目需要遞歸遍歷：
// 原始遞歸代碼（林淵的注釋版）
public List<Long> findChildren(Long parentId) {
// WARNING! 每次遞歸都是一次磁盤尋道（8ms）
List<Long> children = jdbc.query("SELECT id FROM prod_category WHERE parent_id=?", parentId);
for (Long child : children) {
children.addAll(findChildren(child)); // 指數級IO爆炸
}
return children;
}林淵的實驗數據（2004 年實驗報告節選）：
數據量 | 樹高 | 平均查詢時間 |
1 萬 | 14 | 112ms |
10 萬 | 17 | 136ms |
100 萬 | 20 | 160ms |
二叉樹的機械困境與復雜度陷阱
圖片
1970 年代，二叉搜索樹（BST）的理論時間復雜度 O(logN)掩蓋了物理實現的致命缺陷。以機械硬盤為例：
- 樹高災難：100 萬數據產生約 20 層高度（log?(1,000,000)=19.9），假設每次 IO 耗時 8ms，單次查詢需 160ms
- 局部性原理失效：隨機磁盤尋道導致緩存命中率趨近于 0。
另外，當所有節點都偏向一側時，二叉樹退化為“鏈表”。
圖片
B Tree
林淵的競爭對手 Jake 說：我設計了一個 B Tree，相信是絕世無雙的設計。
B 樹通過多路平衡設計解決了磁盤 IO 問題。根據《數據庫系統實現》的公式推導，B 樹的階數 m 與磁盤頁大小的關系為：
m ≥ (PageSize - PageHeader) / (KeySize + PointerSize)以 MySQL 默認 16KB 頁為例（PageHeader 約 120 字節，KeySize 8 字節，Pointer 6 字節），階數 m≈(16384-120)/(8+6)=1162。
10 萬數據量下，B 樹高度僅需 2 層（log????(100000)≈2），查詢 IO 次數從 17 次降為 3 次（根節點常駐內存），總延遲 24ms。
首先定義一條記錄為一個二元組[key, data] ，key 為記錄的鍵值，對應表中的主鍵值，data 為一行記錄中除主鍵外的數據。對于不同的記錄，key 值互不相同。
B-Tree 中的每個節點根據實際情況可以包含大量的關鍵字信息和分支，如下圖所示為一個 3 階的 B-Tree：
圖片
每個節點占用一個盤塊的磁盤空間，一個節點上有兩個升序排序的關鍵字和三個指向子樹根節點的指針，指針存儲的是子節點所在磁盤塊的地址。
兩個關鍵詞劃分成的三個范圍域對應三個指針指向的子樹的數據的范圍域。
以根節點為例，關鍵字為 17 和 35，P1 指針指向的子樹的數據范圍為小于 17，P2 指針指向的子樹的數據范圍為 17~35，P3 指針指向的子樹的數據范圍為大于 35。
模擬查找關鍵字 29 的過程：
- 根據根節點找到磁盤塊 1，讀入內存。【磁盤 I/O 操作第 1 次】
- 比較關鍵字 29 在區間（17,35），找到磁盤塊 1 的指針 P2。
- 根據 P2 指針找到磁盤塊 3，讀入內存。【磁盤 I/O 操作第 2 次】
- 比較關鍵字 29 在區間（26,30），找到磁盤塊 3 的指針 P2。
- 根據 P2 指針找到磁盤塊 8，讀入內存。【磁盤 I/O 操作第 3 次】
- 在磁盤塊 8 中的關鍵字列表中找到關鍵字 29。
分析上面過程，發現需要 3 次磁盤 I/O 操作，和 3 次內存查找操作。由于內存中的關鍵字是一個有序表結構，可以利用二分法查找提高效率。
B+Tree
林淵反駁：“每個節點中不僅包含數據的 key 值，還有 data 值。
而每一個頁的存儲空間是有限的，如果 data 數據較大時將會導致每個節點（即一個頁）能存儲的 key 的數量很小，當存儲的數據量很大時同樣會導致 B-Tree 的深度較大，增大查詢時的磁盤 I/O 次數，進而影響查詢效率。”
而且 BTree 的非葉子節點存儲數據，導致范圍查詢需要跨層跳躍。
林淵腦海中立馬翻閱在 2025 年學到的 B+Tree 數據結構，在《MySQL 內核：InnoDB 存儲引擎》中發現這段代碼：
// storage/innobase/btr/btr0btr.cc
void btr_cur_search_to_nth_level(...) {
/* 只有葉子節點存儲數據 */
if (level == 0) {
page_cur_search_with_match(block, index, tuple, page_mode, &up_match,
&up_bytes, &low_match, &low_bytes, cursor);
}
}"原來 B+樹通過葉子層雙向鏈表，把離散的磁盤頁變成了連續空間！"
整理好思緒，繼續補充道：B+樹通過以下創新實現質的飛躍：
- 全數據葉子層：所有數據僅存儲在葉子節點，非葉節點僅作索引目錄
- 雙向鏈表串聯：葉子節點通過指針形成有序鏈表，范圍掃描時間復雜度從 O(logN)降為 O(1)。
在 B+Tree 中，所有數據記錄節點都是按照鍵值大小順序存放在同一層的葉子節點上，而非葉子節點上只存儲 key 值信息，這樣可以大大加大每個節點存儲的 key 值數量，降低 B+Tree 的高度。
B+Tree 的非葉子節點只存儲鍵值信息，假設每個磁盤塊能存儲 4 個鍵值及指針信息，則變成 B+Tree 后其結構如下圖所示：
圖片
通常在 B+Tree 上有兩個頭指針，一個指向根節點，另一個指向關鍵字最小的葉子節點，而且所有葉子節點（即數據節點）之間是一種鏈式環結構。
因此可以對 B+Tree 進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找，另一種是從根節點開始，進行隨機查找。
MysQL 之父眼睛冒光，看著我驚呆了！！恨不得叫我一聲大師。
西湖論劍，單挑首席
一月后，全球數據庫峰會在西子湖畔召開。林淵抱著一臺 IBM 服務器走上講臺："給我 30 秒，讓各位見見‘未來索引’！”
實時 PK 表演：
-- 場景：1億訂單數據查詢
-- 傳統B樹（甲骨文）
SELECT * FROM orders WHERE id BETWEEN 100000 AND 200000;
-- 耗時12.8秒
-- B+樹（林淵魔改版）
SELECT /*+ BPLUS_SCAN */ * FROM orders BETWEEN 100000 AND 200000;
-- 耗時0.3秒名場面臺詞：
"諸位，這不是優化，是維度的碾壓！
B+樹把磁盤的物理運動，變成了內存的閃電舞蹈！"——當日登上《程序員》雜志封面。三月后，林淵成立"深空科技"，發布"伏羲 B+引擎"。
美國商務部緊急會議："絕不能讓中國掌控數據庫心臟！"
