二叉樹(shù)的致命缺陷

場(chǎng)景還原：商品分類表prod_category的父 ID 字段索引。

CREATE TABLE prod_category (
  id INT PRIMARY KEY,
  parent_id INT,
  INDEX idx_parent (parent_id) -- 二叉樹(shù)實(shí)現(xiàn)
);

性能災(zāi)難：當(dāng)層級(jí)超過(guò) 10 層時(shí)，查詢子類目需要遞歸遍歷：

// 原始遞歸代碼（林淵的注釋版）
public List<Long> findChildren(Long parentId) {
  // WARNING! 每次遞歸都是一次磁盤(pán)尋道（8ms）
  List<Long> children = jdbc.query("SELECT id FROM prod_category WHERE parent_id=?", parentId);
  for (Long child : children) {
    children.addAll(findChildren(child)); // 指數(shù)級(jí)IO爆炸
  }
  return children;
}

林淵的實(shí)驗(yàn)數(shù)據(jù)（2004 年實(shí)驗(yàn)報(bào)告節(jié)選）：

二叉樹(shù)的機(jī)械困境與復(fù)雜度陷阱

圖片

1970 年代，二叉搜索樹(shù)（BST）的理論時(shí)間復(fù)雜度 O(logN)掩蓋了物理實(shí)現(xiàn)的致命缺陷。以機(jī)械硬盤(pán)為例：

• 樹(shù)高災(zāi)難：100 萬(wàn)數(shù)據(jù)產(chǎn)生約 20 層高度（log?(1,000,000)=19.9），假設(shè)每次 IO 耗時(shí) 8ms，單次查詢需 160ms
• 局部性原理失效：隨機(jī)磁盤(pán)尋道導(dǎo)致緩存命中率趨近于 0。

另外，當(dāng)所有節(jié)點(diǎn)都偏向一側(cè)時(shí)，二叉樹(shù)退化為“鏈表”。

圖片

B Tree

林淵的競(jìng)爭(zhēng)對(duì)手 Jake 說(shuō)：我設(shè)計(jì)了一個(gè) B Tree，相信是絕世無(wú)雙的設(shè)計(jì)。

B 樹(shù)通過(guò)多路平衡設(shè)計(jì)解決了磁盤(pán) IO 問(wèn)題。根據(jù)《數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)》的公式推導(dǎo)，B 樹(shù)的階數(shù) m 與磁盤(pán)頁(yè)大小的關(guān)系為：

m ≥ (PageSize - PageHeader) / (KeySize + PointerSize)

以 MySQL 默認(rèn) 16KB 頁(yè)為例（PageHeader 約 120 字節(jié)，KeySize 8 字節(jié)，Pointer 6 字節(jié)），階數(shù) m≈(16384-120)/(8+6)=1162。

10 萬(wàn)數(shù)據(jù)量下，B 樹(shù)高度僅需 2 層（log????(100000)≈2），查詢 IO 次數(shù)從 17 次降為 3 次（根節(jié)點(diǎn)常駐內(nèi)存），總延遲 24ms。

首先定義一條記錄為一個(gè)二元組[key, data] ，key 為記錄的鍵值，對(duì)應(yīng)表中的主鍵值，data 為一行記錄中除主鍵外的數(shù)據(jù)。對(duì)于不同的記錄，key 值互不相同。

B-Tree 中的每個(gè)節(jié)點(diǎn)根據(jù)實(shí)際情況可以包含大量的關(guān)鍵字信息和分支，如下圖所示為一個(gè) 3 階的 B-Tree：

圖片

每個(gè)節(jié)點(diǎn)占用一個(gè)盤(pán)塊的磁盤(pán)空間，一個(gè)節(jié)點(diǎn)上有兩個(gè)升序排序的關(guān)鍵字和三個(gè)指向子樹(shù)根節(jié)點(diǎn)的指針，指針存儲(chǔ)的是子節(jié)點(diǎn)所在磁盤(pán)塊的地址。

兩個(gè)關(guān)鍵詞劃分成的三個(gè)范圍域?qū)?yīng)三個(gè)指針指向的子樹(shù)的數(shù)據(jù)的范圍域。

以根節(jié)點(diǎn)為例，關(guān)鍵字為 17 和 35，P1 指針指向的子樹(shù)的數(shù)據(jù)范圍為小于 17，P2 指針指向的子樹(shù)的數(shù)據(jù)范圍為 17~35，P3 指針指向的子樹(shù)的數(shù)據(jù)范圍為大于 35。

模擬查找關(guān)鍵字 29 的過(guò)程：

1. 根據(jù)根節(jié)點(diǎn)找到磁盤(pán)塊 1，讀入內(nèi)存?！敬疟P(pán) I/O 操作第 1 次】
2. 比較關(guān)鍵字 29 在區(qū)間（17,35），找到磁盤(pán)塊 1 的指針 P2。
3. 根據(jù) P2 指針找到磁盤(pán)塊 3，讀入內(nèi)存?！敬疟P(pán) I/O 操作第 2 次】
4. 比較關(guān)鍵字 29 在區(qū)間（26,30），找到磁盤(pán)塊 3 的指針 P2。
5. 根據(jù) P2 指針找到磁盤(pán)塊 8，讀入內(nèi)存?！敬疟P(pán) I/O 操作第 3 次】
6. 在磁盤(pán)塊 8 中的關(guān)鍵字列表中找到關(guān)鍵字 29。

分析上面過(guò)程，發(fā)現(xiàn)需要 3 次磁盤(pán) I/O 操作，和 3 次內(nèi)存查找操作。由于內(nèi)存中的關(guān)鍵字是一個(gè)有序表結(jié)構(gòu)，可以利用二分法查找提高效率。

B+Tree

林淵反駁：“每個(gè)節(jié)點(diǎn)中不僅包含數(shù)據(jù)的 key 值，還有 data 值。

而每一個(gè)頁(yè)的存儲(chǔ)空間是有限的，如果 data 數(shù)據(jù)較大時(shí)將會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)（即一個(gè)頁(yè)）能存儲(chǔ)的 key 的數(shù)量很小，當(dāng)存儲(chǔ)的數(shù)據(jù)量很大時(shí)同樣會(huì)導(dǎo)致 B-Tree 的深度較大，增大查詢時(shí)的磁盤(pán) I/O 次數(shù)，進(jìn)而影響查詢效率?！?/p>

而且 BTree 的非葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，導(dǎo)致范圍查詢需要跨層跳躍。

林淵腦海中立馬翻閱在 2025 年學(xué)到的 B+Tree 數(shù)據(jù)結(jié)構(gòu)，在《MySQL 內(nèi)核：InnoDB 存儲(chǔ)引擎》中發(fā)現(xiàn)這段代碼：

// storage/innobase/btr/btr0btr.cc
void btr_cur_search_to_nth_level(...) {
  /* 只有葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù) */
  if (level == 0) {
    page_cur_search_with_match(block, index, tuple, page_mode, &up_match,
                              &up_bytes, &low_match, &low_bytes, cursor);
  }
}

"原來(lái) B+樹(shù)通過(guò)葉子層雙向鏈表，把離散的磁盤(pán)頁(yè)變成了連續(xù)空間！"

整理好思緒，繼續(xù)補(bǔ)充道：B+樹(shù)通過(guò)以下創(chuàng)新實(shí)現(xiàn)質(zhì)的飛躍：

1. 全數(shù)據(jù)葉子層：所有數(shù)據(jù)僅存儲(chǔ)在葉子節(jié)點(diǎn)，非葉節(jié)點(diǎn)僅作索引目錄
2. 雙向鏈表串聯(lián)：葉子節(jié)點(diǎn)通過(guò)指針形成有序鏈表，范圍掃描時(shí)間復(fù)雜度從 O(logN)降為 O(1)。

在 B+Tree 中，所有數(shù)據(jù)記錄節(jié)點(diǎn)都是按照鍵值大小順序存放在同一層的葉子節(jié)點(diǎn)上，而非葉子節(jié)點(diǎn)上只存儲(chǔ) key 值信息，這樣可以大大加大每個(gè)節(jié)點(diǎn)存儲(chǔ)的 key 值數(shù)量，降低 B+Tree 的高度。

B+Tree 的非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值信息，假設(shè)每個(gè)磁盤(pán)塊能存儲(chǔ) 4 個(gè)鍵值及指針信息，則變成 B+Tree 后其結(jié)構(gòu)如下圖所示：

圖片

通常在 B+Tree 上有兩個(gè)頭指針，一個(gè)指向根節(jié)點(diǎn)，另一個(gè)指向關(guān)鍵字最小的葉子節(jié)點(diǎn)，而且所有葉子節(jié)點(diǎn)（即數(shù)據(jù)節(jié)點(diǎn)）之間是一種鏈?zhǔn)江h(huán)結(jié)構(gòu)。

因此可以對(duì) B+Tree 進(jìn)行兩種查找運(yùn)算：一種是對(duì)于主鍵的范圍查找和分頁(yè)查找，另一種是從根節(jié)點(diǎn)開(kāi)始，進(jìn)行隨機(jī)查找。

MysQL 之父眼睛冒光，看著我驚呆了??！恨不得叫我一聲大師。

西湖論劍，單挑首席

一月后，全球數(shù)據(jù)庫(kù)峰會(huì)在西子湖畔召開(kāi)。林淵抱著一臺(tái) IBM 服務(wù)器走上講臺(tái)："給我 30 秒，讓各位見(jiàn)見(jiàn)‘未來(lái)索引’！”

實(shí)時(shí) PK 表演：

-- 場(chǎng)景：1億訂單數(shù)據(jù)查詢
-- 傳統(tǒng)B樹(shù)（甲骨文）
SELECT * FROM orders WHERE id BETWEEN 100000 AND 200000;
-- 耗時(shí)12.8秒

-- B+樹(shù)（林淵魔改版）
SELECT /*+ BPLUS_SCAN */ * FROM orders BETWEEN 100000 AND 200000;
-- 耗時(shí)0.3秒

名場(chǎng)面臺(tái)詞：

"諸位，這不是優(yōu)化，是維度的碾壓！

B+樹(shù)把磁盤(pán)的物理運(yùn)動(dòng)，變成了內(nèi)存的閃電舞蹈！"——當(dāng)日登上《程序員》雜志封面。三月后，林淵成立"深空科技"，發(fā)布"伏羲 B+引擎"。

美國(guó)商務(wù)部緊急會(huì)議："絕不能讓中國(guó)掌控?cái)?shù)據(jù)庫(kù)心臟！"