B+Tree

B+Tree 是資料庫最經典的索引結構，幾乎所有關聯式資料庫都以它作為主要的 on-disk index。我們學習 B+Tree 是因為它的高 fan-out 特性讓樹的高度極低，大幅減少磁碟 I/O 次數，這對理解儲存系統的效能瓶頸至關重要。在這個單元中，我們會介紹 B+Tree 的結構：inner node 只負責 routing，所有資料都存放在 leaf node 並以 linked list 串接，方便 range query。我們也會深入討論 search、insert、delete 操作，以及當 node 滿了或太空時觸發的 split 與 merge，還有 prefix truncation 等優化技巧如何進一步提高 fan-out。

Key Concepts

我理解 B+Tree 的基本結構：inner node 只存放 routing key 用於導引搜尋方向，所有實際資料都儲存在 leaf node 中

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

我理解高 fan-out 如何讓 B+Tree 的高度維持極低，從而減少每次查詢所需的 disk I/O 次數

我理解 search、insert、delete 操作的流程，以及 insert 時 node 滿了會觸發 split、delete 時 node 太空會觸發 merge

我理解 prefix truncation 優化如何透過縮短 inner node 中的 key 來提高 fan-out，進一步降低樹的高度

我了解為什麼 B+Tree 特別適合 disk-based 儲存系統：其結構天然對應 page-oriented 的磁碟存取模式，每個 node 對應一個 disk page

Recommended Resources