Bf-Trees: Breaking the Page Barrier
Source: Dev.to
Hello, I’m Maneshwar. I’m working on FreeDevTools – an online, open‑source hub that consolidates dev tools, cheat codes, and TLDRs in one place, making it easy for developers to find and use tools without endless searching.
The Real Problem: Pages Are Too Big
- A database page is typically 4 KB or 8 KB.
- Every update or read pulls in a lot of irrelevant data:
- A 50‑byte record update rewrites a 4 KB page.
- Caching 5 hot records also caches 200 cold ones.
- Range scans and point lookups compete for the same page‑level cache.
- Thought experiment: if the record size equaled the page size, these problems would disappear instantly.
The Core Idea Behind Bf‑Trees
Bf‑Trees break the assumption that cache pages must mirror disk pages.
Disk page != Cache pageInstead, memory holds mini‑pages: variable‑length chunks that store only what matters:
- Individual hot records
- A small key range
- Buffered recent writes
- A full page when needed for range scans
Mini‑pages grow and shrink dynamically based on workload, changing the entire performance landscape.
Comparison: Traditional B‑Tree vs. Bf‑Tree
| Aspect | Traditional B‑Tree | Bf‑Tree |
|---|---|---|
| Updates | Rewrite whole pages | Rewrite just the mini‑page |
| Cache contents | Holds cold data | Holds only hot data |
| Unit size | Fixed 4 KB units | Variable‑sized fine‑grained blocks |
| Record/cache split | Bolted on top | Mini‑pages unify cache + buffer + data |
Variable‑Length Buffer Pool
To manage mini‑pages efficiently, Bf‑Tree uses a circular buffer in memory:
- Fixed total size.
- Mini‑pages allocated by advancing the tail.
- Free space tracked in a free list.
- Growth handled by copy‑on‑write (RCU).
- When full → evict mini‑pages near the head back to disk.
This design enables concurrent allocation, resizing, and eviction without fragmentation hell.
What This Enables
- Point lookups: Fast, because mini‑pages cache only what’s hot.
- Range scans: Mini‑pages expand to full pages when needed.
- Writes: Only the mini‑page changes.
The Numbers
Evaluations show:
- 6× faster writes vs. B‑Tree.
- 2× faster point lookups vs. B‑Trees & LSMs.
- 2.5× faster scans vs. RocksDB (LSM‑Tree).
In short, Bf‑Tree beats both B‑Trees and LSM‑Trees across all workloads—a rare achievement where reads and writes both improve.
Why This Matters
Modern systems push data beyond RAM size. Bf‑Tree demonstrates that the future isn’t a binary B‑Tree vs. LSM‑Tree debate; it’s about rethinking pages.
Next Article
Coming up next, I’ll dive into three areas:
- Understanding LSM‑Tree internals and where they shine or break.
- How modern NVMe SSD behavior changes the cost model of writes.
- The architectural details behind Bf‑Tree and mini‑pages.
These topics will lay the foundation for exploring RCU growth/shrink, eviction strategy, and concurrency guarantees. Stay tuned.
👉 Check out: FreeDevTools
Any feedback or contributions are welcome! It’s online, open‑source, and ready for anyone to use.
⭐ Star it on GitHub: