An Introduction to Bε-trees and Write-Optimization

# An Introduction to Bε-trees and Write-Optimization Source: [https://www.usenix.org/publications/login/oct15/bender](https://www.usenix.org/publications/login/oct15/bender) Author\(s\): Michael A\. Bender, Martin Farach\-Colton, William Jannen, Rob Johnson, Bradley C\. Kuszmaul, Donald E\. Porter, Jun Yuan, and Yang Zhan 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\.