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