B 樹與資料庫索引 (2024)

背景

這篇文章由 PlanetScale 的工程師 Ben Dicken 撰寫，深入淺出地介紹了 B-tree 與 B+tree 的運作原理，以及為什麼這些數據結構會成為現代資料庫索引的基石。透過互動式動畫，作者展示了節點分裂、樹狀平衡以及磁碟區塊優化等核心概念，並特別針對 MySQL 的 InnoDB 引擎如何利用 B+tree 存儲資料進行了詳盡說明。

社群觀點

在 Hacker News 的討論中，社群成員對於 B-tree 的應用場景與效能權衡展開了深入探討。針對原文提到的主鍵選擇，不少開發者分享了關於「順序型 ID」與「隨機 UUID」的實務經驗。傳統觀點認為順序型 ID 有助於寫入效能，因為這能讓新資料以追加方式寫入 B+tree 的葉子節點，維持較高的填充率；然而，部分留言者指出在分散式系統或分片架構中，順序型 ID 可能導致特定節點成為寫入熱點。對此，作者回應建議可以透過對 ID 進行雜湊處理來決定分片鍵，如此既能保有單一節點內的寫入效率，又能實現負載均衡。

關於資料庫引擎的演進，討論區也出現了對不同數據結構的比較。有開發者提到，雖然 B-tree 在讀取密集型場景表現優異，但在極高寫入吞吐量的需求下，LSM-tree 通常是更好的選擇。此外，針對 MySQL 與 PostgreSQL 索引建議的爭議，有留言者觀察到近期許多文章盲目推崇 UUID v4 或 v7，但從底層結構來看，簡單的順序整數或具備時間順序性的 UUID v7 才是維持索引效能的關鍵。

更有趣的觀點來自於對資料庫本質的思考。有留言者認為，資料庫的核心其實就是索引，甚至連順序掃描也可以視為一種索引形式。這種觀點將「建立資料表」視為「建立索引」的延伸，反映出底層存儲結構如何定義了資料庫的行為。同時，社群也對學術界提出的新結構如 Bf-tree 表達了好奇，儘管目前主流開源資料庫尚未採納，但這顯示出開發者社群對於突破 B-tree 傳統限制的持續關注。

延伸閱讀

在討論過程中，社群成員推薦了幾份深入研究資料庫內核的經典資源。首推的是 Martin Kleppmann 所著的《Designing Data Intensive Applications》（DDIA），以及 Alex Petrov 的《Database Internals》，這兩本書被公認為理解 B-tree 與 LSM-tree 權衡關係的權威著作。此外，針對 MySQL 開發者的進階學習，PlanetScale 提供的「MySQL for Developers」免費課程也獲得了高度評價。對於對新型索引結構感興趣的讀者，留言中提到的 Bf-tree 論文（VLDB 2024）則提供了學術界的最新研究方向。