B-Trees Are Back
Viktor Leis 又出招了
B+ Tree 的 lookup 為什麼快？你大概會回答：因為它的 asymptotic complexity 為 O(log N)。樹很淺，很快可以抵達 leaf node。這個答案在大多情況下正確，但 Viktor Leis 教授的新論文 B-Trees Are Back (簡稱：BAB) 挑戰我們，不盡然喔！
- 你以為 asymptotic complexity 決定效能嗎？論文試著說服我們 cache miss 的次數才是真正的成本，節點內部資料怎麼擺放比樹的結構還重要！
- 你以為更好的 asymptotic complexity 一定會贏嗎？論文展示 Wormhole 的 O(log L) 雖然比 B+ Tree 的 O(log N) 好，但精心調過的 B+ Tree 在許多 workload 上反而勝出。
- 你以為 B+ Tree 的 leaf 必須維持 key 有序、所有 leaf 都長得一樣嗎？論文說：不排序反而更快，而且同一棵樹裡的不同 leaf 應該採用不同的佈局，由樹自己在執行時決定。
接下來我們會逐一檢視 BAB 論文如何論證這些主張。
BTW，Viktor Leis 教授我們在 io_uring 單元已經看過他們出大招了，各種奇技淫巧的榨乾 SSD 效能。今天我們講的論文，以及經典的 Adaptive Radix Tree 都出於他手。
1. 對照組：Wormhole (蟲洞)
Wormhole 是 2019 年 UT Arlington 團隊提出的一個資料結構。傳統 B+ Tree 走 internal node 的成本是 O(log N)，N 是 key 總數。當 N 很大時這個 log N 不容忽視。 Wormhole 的目標是把 log N 拿掉，換成只跟 key 長度 L 有關的 O(log L)。 它的觀察是 B+ Tree 的 leaf 已經串成有序 linked list，所以其實只要找到「正確的 leaf」就行，不需要走完整棵樹。 它保留 leaf list，但把 internal node 換成 trie，再用 hash table 加速 trie traversal，最終達成 O(log L) 的 lookup。
Wormhole 有三個弱點。MetaTrieHT 是一張大 hash table，沒辦法切成固定大小的 page，所以資料一旦超過記憶體整個結構就崩潰。Leaf 內部用 pointer 串接 record，cache locality 不佳，導致 range scan 變慢。每個 record 都是單獨 malloc 出來的，memory allocator overhead 相當沉重。後面會看到 BAB 如何針對這三點逐一攻擊。
BAB 論文的 Figure 1 告訴我們，對 dense integer，優化後的 B-Tree 不只追上 Wormhole，還超越 27%。 擁有漂亮的 asymptotic complexity 的蟲洞，輸了。為什麼？我們得先回頭看 B-Tree 的 leaf 裡到底發生了什麼事。
2. B+ Tree 的 leaf
BAB 論文的 leaf 採用 slotted page 設計：key 和 value 直接內嵌在 page 裡，slot 只是個 (offset, key_len, val_len) 的 tuple。 假設你要在這個 leaf 裡找一個 key，做 binary search，每次比較 key 時要先從 slot array 讀 slot（這幾乎不會 cache miss，因為 slot 小且連續），然後透過 slot 的 offset 跳到 heap 上讀真正的 key，再做比較。 問題在第二步：heap 上的 key 是按插入順序擺放的，每次比較都會跳到 page 內隨機位置。 一個 4 KiB 的 leaf 通常裝幾十到一百多個 record，一次 binary search 大概是 6 到 7 次比較，每次比較都可能引發 cache miss。
3. 把 key 的前 4 byte 複製進 slot
論文的第一個優化稱為 heads：每個 slot 多附上 4 byte，是這個 key 的前 4 byte 的副本。Binary search 比較時，先用一個指令比較 head，只有 head 相同時才真的去 heap 比對完整 key。
你可能會覺得：複製資料是浪費空間，每個 record 多花 4 byte 意味著 leaf 能裝的 record 變少，fan-out 降低，樹變高。但論文的數據顯示這個 trade-off 划算。Figure 8 告訴我們：效果隨 key 開頭的多樣性而變化：dense integer 的 lookup 快了 49%、insert 快了 57%，Wikipedia 標題的 lookup 快了 38%，URL 只快了 16%。
對 integer 效果最好，是因為 4 byte 的 head 已經包含整個 key，比較完全在 slot array 中完成，根本不需要碰 heap。對 string 而言，head 只是個 prefix，可以快速排除不相等的 key，但 head 相同時仍然要去 heap 比對完整 key，所以效益較小。
URL 效果最不好，是因為所有 URL 都以 http 開頭，head 完全沒有區分能力。這是論文教我們的第一課：演算法做幾次比較不重要，每次比較碰幾條 cache line 才重要。
然而，heads 的優化效果非常依賴 key 的分布特性。
這招對 URL key 效果不好，因為所有 URL 都以 http 開頭，head 無法區分。對 Wikipedia 標題則還不錯，因為標題開頭多樣。
4. 再多塞 16 個 head 進 header，幾乎免費
論文更進一步提出 head 的強化版： hints array：在 header 裡擺 16 個從 slot 中均勻取樣的 head。Lookup 時先在這 16 個 hint 上做 linear search，把 binary search 的範圍縮小到大約 1/16，然後再開始正常的 binary search。
直覺上你會覺得 linear search 加 binary search 不是更慢嗎？關鍵在 16 個 hint 剛好佔一個 cache line 大小 (64 byte)。 Linear search 這 16 個 entry 幾乎完全免費，因為只有一次 cache miss 就能把整條 cache line 拉進來，但這個搜尋讓後續的 binary search 從一開始就不會碰到隨機位置。對 dense integer 的 lookup 又加快了 25%，空間開銷只有 1.5% 到 2%。BAB 論文又再次優化 cache line 的使用。
5. Leaf 不需要保持 sorted key
到目前為止的優化都還在「加速比較」。BAB 論文接下來直接問一個更根本的問題：為什麼一定要比較？ 第一個優化方向是 fingerprinting leaf：每個 key 算一個 1-byte hash（fingerprint），point lookup 時不做 binary search，直接用 SIMD 把 fingerprint 陣列掃一遍，fingerprint 有符合才去比對真 key。
最反直覺的地方是這個 leaf 不維持 sorted key。Insert 時直接 append 到尾端，要 range scan 時才 lazy sort。這對 point lookup 來說很划算：原本要 6 到 7 次 cache miss 拿不同 key 比較，現在只要 1 到 2 次 cache miss 掃完 fingerprint 陣列，期望值不到 1 次 cache miss 去比真 key。 Insert 也加速了，因為不用 binary search 找位置，更不用移動一半的 slot，直接 append。代價是 range scan 變慢，需要先排序。
B+ Tree 不是定義上要 leaf 排序好嗎？BAB論文說：除非你的 workload sequential scan 很多，否則不用排序。
6. 有些 leaf 根本不存 key
另一個蠻有巧思的優化是 dense leaves：如果一個 leaf 裡的 key 是夠密集的整數（像 ID column），那就直接把 key 當陣列 index 使用，連 key 都不需要存。具體做法稱為 frame-of-reference encoding：leaf 在 header 裡記一個 reference key，要找 key K 時計算 offset = K − reference，用 offset 直接索引陣列，bitmap 標示哪些 slot 有資料。請見 Figure 6 對 slotted page (semi-dense-leaf) 與 fully-dense leaf 的比較)
於是，Lookup 變成「算減法、查 bitmap、從陣列拿 value」，完全沒有 key 比較，完全沒有 binary search。對 100% 密集的 dense integer key，lookup 快了 71%，insert 快了 213%。
一般我們會覺得 leaf 一定要存 key，不然怎麼知道 key 存不存在呢？ 但 BAB 論文挑戰我們：如果 leaf 的 key range 已經由 fence key 定義，加上 dense 的假設，key 的存在性可以從位置直接推導出來。更聰明的地方是 dense leaves 只在「key 真的夠密」時啟用，其他情況退回一般的 leaf。
7. 同一棵樹裡的 leaf 可以長得不一樣
傳統 B+ Tree 的所有 leaf 是同一種結構，但 BAB 跟進經典的 ART 論文，挑戰這點：為什麼不能讓每個 leaf 自己決定要用哪種佈局？
Adaptive B-Tree 有三種 leaf：comparison-based（採用 heads + hints）、fingerprinting、dense。每個 leaf 在執行時自己決定要當哪一種，依照兩個依據。
第一，這個 leaf 裡的 key 長什麼樣？BAB 論文稱為 key-adaption，在 split 或 merge 時判斷：如果 key 是密集整數就用 dense leaf，如果 head 不夠 unique（相鄰 key 的 head 重複率超過 1/16）就用 fingerprinting，否則用 comparison-based。
第二，這個 leaf 主要被怎麼使用？論文稱為 operation-adaption。 每個 leaf 帶一個 1-byte saturating counter，scan 操作以 15% 機率 +1，point 操作以 5% 機率 −1。Counter 滿了就轉成 comparison-based（適合 scan），counter 空了就轉成 fingerprinting（適合 point）。 為什麼用機率而不是直接 count 呢？因為每次操作都更新 counter 會增加寫入競爭，特別在 multi-threaded 環境下。而隨機取樣讓監測本身的 overhead 降低不少。
對 URL 的 lookup workload，多數 leaf 變成 fingerprinting；對 URL 的 scan workload，多數變成 comparison-based；對 dense integer，全部變成 dense leaf。使用者不需要調參數，就可以享受到動態優化，Viktor Leis 怎麼會這麼聰明呢？
8. 這些優化在 out-of-memory 場景更重要
到這裡你可能還是覺得：B-Tree 雖然快了，但 Wormhole、ART 這些純 in-memory 資料結構也不是吃素的。
然而，這些 in-memory 資料結構在資料量超過記憶體負荷時，沒辦法 spill 到 SSD。
B-Tree 因為節點是固定大小的 page，可以透過 buffer manager（資料庫自己管理的記憶體 pool，類似 OS 的 page cache）把 cold page evict 到 SSD，但 Wormhole 的 MetaTrieHT 是一張大 hash table，ART 是 pointer-heavy 的 trie，這些結構無法對齊 4KB page，因此無法用 O_DIRECT 或 mmap 方式無法寫入 SSD。另外，因為 pointer 是 virtual memory 中的地址，這些頁面在 swap out 後若再度被載入記憶體時，virtual memory 地址會失效。
Figure 21 告訴我們，當資料量超過 buffer pool 時，單一 layout 的傳統方法 throughput 掉的遠比 adaptive 方法快，因為這時空間效率變成決定性因素。節點越省空間，buffer pool 能裝越多東西，越少 page 需要從 SSD 讀回來。BAB 提出的優化，包括：prefix truncation、dense leaves，提升了空間效率，因此在 out-of-memory 場景下繼續勝出。
從 Figure 18 可以看到，Adaptive B-Tree 在所有 dataset 上都是最省空間的。Wormhole 跟 ART 雖然索引結構本身很小，但 record 都是分散 malloc 的，memory allocator overhead 大概佔了 1/3 空間。B-Tree 把 record 直接內嵌在 page 裡，只用 16-bit offset 就能定位，根本不需要 64-bit pointer。
結論
系統問題就是這麼有趣，可以翻盤一些像是 asymptotic complexity 的理論性質，cache locality 往往更重要。但是，現代 CPU 有 hardware prefetcher 自動預載資料。為什麼 prefetcher 沒有讓 BAB 這些優化失效呢？ B-Tree binary search 的 access pattern 對 prefetcher 友不友善。