BLI: A High-performance Bucket-based Learned Index with Concurrency Support

Huibing Dong, Wenlong Wang, Chun Liu, David Du · 2025

Read BLI: A High-performance Bucket-based Learned Index with Concurrency Support by Huibing Dong, Wenlong Wang, Chun Liu, David Du (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-10597.txt.

Introduction

Huibing Dong, Wenlong Wang, Chun Liu, and David Du present a bucket-based learned index in a 2025 paper. Learned indexes use machine learning models to predict where a key sits in a sorted array, promising faster lookups than trees. Strict sorting makes insertion expensive, blocks lock-free concurrency, and punishes model inaccuracy.

Their index, BLI, is globally sorted but locally unsorted inside buckets. That relaxation eases updates and lets lookups and inserts run concurrently inside a node despite imperfect predictions. An updatable, concurrent learned index is what real database systems actually need.

Catalog record

CREATORHuibing Dong, Wenlong Wang, Chun Liu, David Du
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-10597

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

BLI: A High-performance Bucket-based Learned Index with Concurrency Support Huibing Dong, Wenlong Wang, Chun Liu, David Du Abstract . Learned indexes are promising to replace traditional tree-based indexes. They typically employ machine learning models to efficiently predict target positions in strictly sorted linear arrays. However, the strict sorted order 1) significantly increases insertion overhead, 2) makes it challenging to support lock-free concurrency, and 3) harms in-node lookup/insertion efficiency due to model inaccuracy. In this paper, we introduce a Bucket-based Learned Index (BLI) , which is an updatable in-memory learned index that adopts a "globally sorted, locally unsorted" approach by replacing linear sorted arrays with Buckets . BLI optimizes the insertion throughput by only sorting Buckets, not the key-value pairs within a Bucket. BLI strategically balances three critical performance metrics: tree fanouts, lookup/insert latency for inner nodes, lookup/insert latency for leaf nodes, and memory consumption. To minimize maintenance costs, BLI performs lightweight bulk loading, insert, node scaling, node split, model retraining, and node merging adaptively. BLI supports lock-free concurrency thanks to the unsorted design with Buckets. Our results show that BLI achieves up to 2.21x better throughput than state-of-the-art learned indexes, with up to 3.91x gains under multi-threaded conditions. † † authors: . PVLDB Reference Format: PVLDB, 14(1): XXX-XXX, 2025. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/gdymind/Buck-Learned-Indexandhttps://github.com/wwl2755/GRE_buck_index . 1. Introduction In-memory key-value stores are widely used across various data-centric applications, as evidenced by the key-value store deployment at Meta ( Nishtala et al., 2013 ) , Twitter ( Yang et al., 2021 ) , and other companies. While tree-based indexes, such as B+-trees, have traditionally dominated the indexing of key-value stores which support range queries, recent advancements have introduced learned indexes (e.g., RMI ( Kraska et al., 2018 ) , ALEX ( Ding et al., 2020 ) and LIPP ( Wu et al., 2021 ) ) as superior alternatives due to their enhanced or comparable lookup performance ( Wu et al., 2021 ; Kraska et al., 2018 ; Wang and Du, 2024 ) . Learned indexes use machine learning models to predict the approximate position of a lookup key in a strictly sorted array of key-value pairs. Trained on the mapping from keys to their positions in the array, these models aim for fast and accurate prediction, outperforming traditional tree-based index searches. For simplicity, we refer to the distribution of all (key, position) pairs as the key distribution hereafter. If the exact key-value pair is not found at the predicted position, a last-mile search is performed in nearby positions of the linear array. The key-value pairs are strictly sorted in the array , and the learned models act as monotonic functions of the key-position mapping. The first proposed learned index, the Recursive Model Index (RMI) ( Kraska et al., 2018 ) , employs a hierarchy of models for enhanced accuracy. The root model spans the entire key range, branching into child models, each dedicated to a sub-key range. This branching process concludes after multiple iterations, forming multiple levels of models. After that, the last-level models (or the leaf models) predict the location of a specific key-value pair within its key range. However, key-value pairs in RMI are tightly packed into a dense array, which precludes accommodating new insertions within the array. Therefore, various updatable learned indexes have been developed to support insertions of key-value pairs, and the number of models can be dynamically increased accordingly. Thanks to the "sufficiently accurate" model predictions, the throughput of existing updatable learned indexes can outperform traditional indexes by over 80%, according to a benchmarking paper called GRE ( Wongkham et al., 2022 ) . These updatable learned indexes typically utilize one of three structures to facilitate insertions: merge trees, delta buffers, or gapped arrays. During insertion, the merge tree method merges multiple read-only sub-indexes with newly inserted key-value pairs. In the delta-buffer approach, new insertions are temporarily held in a buffer area, which will be periodically merged into the main index. The gapped-array strategy employs pre-allocated spaces (i.e., empty positions in the linear array) to accommodate new key-value pairs in place. We refer to gapped-array-based learned indexes as in-place updatable learned indexes . Notably, according to GRE, two state-of-the-art (SOTA) in-place updatable learned indexes, ALEX ( Ding et al., 2020 ) and LIPP ( Wu et al., 2021 ) , generally outperform other learned indexes. ALEX supports insertions by shifting neighboring key-value pairs within a leaf model’s key range. GRE’s analysis reveals that, during insertion, ALEX spends an average of 58.60% of its time on shifting operations after the lookup process, while LIPP spends 32.24% on chaining operations. These findings motivate us to further improve performance by eliminating strict-order-preserving operations such as shifting and chaining. We introduce a new in-place updatable learned index, the Bucket-Based Learned Index (BLI) , which operates without strict ordering. Before diving into the specifics of BLI, we will introduce some key performance metrics to quantify potential optimizations. 1.1. Performance metrics As aforementioned, learned indexes generally use a hierarchy of machine learning models. A non-leaf model holds an array of child models, while a leaf model holds an array of key-value pairs within its key range. The overall lookup and insertion performance is influenced by both the efficiency of individual models and the number of models that need to be accessed during these operations. We have defined four key metrics that impact the overall performance: 1) Model Fanout ( N ) . The Model Fanout refers to the number of child models in a non-leaf model or the number of key-value pairs in a leaf model. Given the same dataset, the lookup traversal path (i.e., the sequence of all models from the root to the leaf) can be shortened if larger model fanouts are accommodated. 2) Lookup Efficiency ( E_{\text{lookup}} ). For an individual model, given t_{\text{lookup}_{i}} representing the lookup latency when searching for the i th child model or key-value pair in the model’s array, lookup efficiency E_{\text{lookup}} can be defined as the reciprocal of the average lookup latency of the entries (i.e., key-value pairs or child models) corresponding to the model, expressed as E_{\text{lookup}}=\frac{N}{\sum_{i=1}^{N}(t_{\text{lookup}_{i}})} . E_{\text{lookup}} is determined by all lookup latencies t_{\text{lookup}_{i}} with i from 1 to N , and these latencies are mainly determined by the model prediction error. Balancing the tradeoff between minimizing prediction error in E_{\text{lookup}} and maintaining an optimal N is crucial. While a low prediction error improves E_{\text{lookup}} , excessively reducing the error tolerance can decrease N , which is detrimental. 3) Insert Efficiency ( E_{\text{insert}} ). Before performing insertions, a lookup is required to determine the appropriate insertion position, after which insertions can be executed correctly. To exclude the effect of lookup efficiency, we define E_{\text{insert}} as \frac{N}{\sum_{i=1}^{N}(t_{\text{insert}_{i}}-t_{\text{lookup}_{i}})} , where t_{\text{insert}_{i}} represents the total latency during insertion. 4) Memory

Read the complete text