B+Tree

B+Tree 是資料庫最經典的索引結構，幾乎所有關聯式資料庫（MySQL InnoDB、PostgreSQL、SQLite）都以它作為主要的 on-disk index。我們學習 B+Tree 是因為它的高 fan-out 特性讓樹的高度極低，大幅減少磁碟 I/O 次數。在這個單元中，我們會介紹 B+Tree 的結構（inner node 只負責 routing，leaf node 以 linked list 串接）、它與 slotted page 的配合關係（leaf node 透過 CTID 指向 heap page），以及 prefix truncation 如何進一步提高 fan-out。

貢獻 HackMD 共筆 💲大抄

Key Concepts

我理解 B+Tree 的基本結構：inner node 只存放 routing key，所有實際資料都儲存在 leaf node 中

我理解 leaf node 之間以 linked list 串接，使得 range query 可以循序掃描而不需回到上層 node

我能計算 fan-out 並理解高 fan-out 如何讓 B+Tree 的高度極低，減少每次查詢所需的 disk I/O 次數

我理解 B+Tree leaf node 透過 CTID 指向 slotted page 中的 record，以及 slot indirection 為什麼讓這個設計能運作

我理解 prefix truncation 如何透過縮短 routing key 來提高 fan-out

Recommended Resources

(Optional) "Modern B-Tree Techniques" by Goetz Graefe。經典中的經典。勇敢的人可以看