第5章 B樹家族#

B 樹家族是磁碟時代最重要的資料結構：檔案系統的目錄索引、資料庫的主鍵索引、乃至現代鍵值儲存的底層，幾乎都是 B-tree 或 B+tree 的變體。它解決的問題很單純——二元搜尋樹在磁碟上每層要一次 I/O，一百萬筆資料就要 20 次 I/O，太慢了。B 樹把每個節點放大成一個分頁，塞進數十到數百個鍵，讓樹高壓到 3~4 層，也就是每次查詢只要 3~4 次 I/O。

本章從二元樹出發推導出多路搜尋樹的設計邏輯，實作 B-tree 的插入、刪除、分裂與合併，最後介紹資料庫真正使用的 B+tree：為什麼所有資料要搬到葉節點、為什麼葉節點要串成鏈結串列，以及範圍掃描如何因此受益。