An Introduction to Bε-trees and Write-Optimization
📜 Abstract
A Bε-tree is an example of a write-optimized data structure and can be used to organize on-disk storage for an application such as a database or file system. A Bε-tree provides a key-value API, similar to a B-tree, but with better performance, particularly for inserts, range queries, and key-value updates. This article describes the Bε-tree, compares its asymptotic performance to B-trees and Log-Structured Merge trees (LSM-trees), and presents real-world performance measurements. After finishing this article, a reader should have a basic understanding of how a Bε-tree works, its performance characteristics, how it compares to other key-value stores, and how to design applications to gain the most performance from a Bε-tree.
✨ Summary
The article presents Bε-trees as write-optimized external-memory search trees that extend B-trees with message buffers in internal nodes. Inserts, deletes, and upserts are buffered near the root and flushed downward in batches, amortizing I/O costs across many updates. The parameter ε controls the trade-off between branching factor and buffer capacity: smaller ε improves update throughput, while larger ε reduces search overhead. With ε = 1/2, inserts cost approximately O(log_B N / √B), while point queries retain logarithmic complexity with only a constant-factor increase over B-trees. Range queries retain the usual logarithmic search plus scan cost, O(log_B N + k/B). The paper also explains upserts, covering and secondary indices, caching effects, node-size selection, and the differences between Bε-trees and LSM-trees. Its evaluation through the BetrFS research file system reports substantially improved small-file creation and directory-scan performance, while identifying large renames, large deletes, and large sequential writes as limitations.
Documented influence. The paper’s concepts were applied in the BetrFS in-kernel file system and were associated with the commercial TokuDB database and its fractal-tree implementation. The BetrFS project describes Bε-trees as the basis of its on-disk organization and identifies fractal trees as a specialized Bε-tree variant. (betrfs.org) A later open-source Bε-tree implementation explicitly cites this article and implements buffered message flushing, direct-to-leaf flushing heuristics, and copy-on-write support. (github.com) The article has also continued to be used as instructional material in external-memory algorithms and modern storage-systems courses. (courses.compute.dtu.dk)