The Bε-tree File System, or BetrFS, is an in-kernel file system that uses Bε trees to organize on-disk storage. Bε trees are a write-optimized dictionary, and offer the same asymptotic behavior for sequential I/O and point queries as a B-tree. The advantage of a Bε tree is that it can also ingest small, random writes 1-2 orders of magnitude faster than B-trees and other standard on-disk data structures.
The goal of BetrFS is to realize performance that strictly dominates the performance of current, general-purpose file systems.
What is a Write-Optimized Dictionary?Write-Optimized Dictionaries include Bε trees, Log-Structured Merge Trees (LSM Trees), and COLAs. Speaking generally, a WOD is a hierarchical structure with logarithmic search complexity (e.g., a tree), but the upper levels of the hierarchy include a log for making small, random writes durable quickly. Unlike a purely log-structured file system, the log is merged into the tree structure in a timely and organized way; these costs are included in the asymptotic analysis, and have good upper bounds.
BetrFS is an in-kernel file system, based on the opensource fractal tree implementation from Tokutek Inc. A fractal tree is a specialized variant of a Bε tree.
Find out more on our FAQ page.
