From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees

2020/05/28 by Yifan Dai, Yien Xu, Dai, Yifan +11 · 1 citation
Computer Science · Decision Sciences · #Data Mining Algorithms and Applications #Data Quality and Management #Databases (cs.DB) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Time Series Analysis and Forecasting

paper · pdf · doi:10.48550/arxiv.2005.14213

openalex publication_date 2020/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce BOURBON, a log-structured merge (LSM) tree that utilizes machine learning to provide fast lookups. We base the design and implementation of BOURBON on empirically-grounded principles that we derive through careful analysis of LSM design. BOURBON employs greedy piecewise linear regression to learn key distributions, enabling fast lookup with minimal computation, and applies a cost-benefit strategy to decide when learning will be worthwhile. Through a series of experiments on both synthetic and real-world datasets, we show that BOURBON improves lookup performance by 1.23x-1.78x as compared to state-of-the-art production LSMs.

Citations

• The log-structured merge-tree (LSM-tree)
• ImageNet classification with deep convolutional neural networks
• End to End Learning for Self-Driving Cars
• Fast Algorithms for Segmented Regression
• RadixSpline: A Single-Pass Learned Index

Cited by

• [Technical Report] ArceKV: Towards Workload-driven LSM-compactions for Key-Value Store Under Dynamic Workloads

Related

• DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees
• Learned LSM-trees: Two Approaches Using Learned Bloom Filters
• Evaluating Learned Indexes in LSM-tree Systems: Benchmarks,Insights and Design Choices
• LearnedKV: Integrating LSM and Learned Index for Superior Performance on Storage
• CAMAL: Optimizing LSM-trees via Active Learning