B-Trees Are Back

B+Tree 的 lookup 為什麼快？大多數人會答 O(log N) 樹很淺。2025 年的 "B-Trees Are Back" (BAB) 論文挑戰這個直覺：真正的成本是 cache miss 次數，節點內部資料怎麼擺放比樹的結構還重要。 我們將透過 heads、hints、fingerprinting leaf、dense leaves 等 node 層次的 layout 優化，看現代 B+Tree 如何在許多 workload 反過來贏過 Wormhole；並透過 Adaptive B-Tree 看為什麼同一棵樹裡的 leaf 應該長得不一樣；最後看 B-Tree 在 data > memory 時的 spillability 為什麼勝過純 in-memory 結構。

💲大抄

Key Concepts

我理解現代 in-memory index 的 cache miss 次數如何影響效能

我能說出 BAB 在 node 層的四個 layout 優化：heads、hints、fingerprinting leaf、dense leaves

我理解 Adaptive B-Tree 如何讓同一棵樹裡不同 leaf 採用不同 layout 的設計，以及 key-adaption 與 operation-adaption 如何在執行時決定每個 leaf 的型態

Recommended Resources