An Introduction to Bε-trees and Write-Optimization

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.