arXiv CSopen access

A Pragmatic Approach to Learned Indexing in RocksDB: Targeted Optimizations with Minimal System Modification

arXiv:2605.23815v1 [cs.DB] 22 May 2026

A Pragmatic Approach to Learned Indexing in RocksDB: Targeted Optimizations with Minimal System Modification Shubham Vashisth

Olivier Michaud

McGill University Montréal, Canada [email protected]

McGill University Montréal, Canada [email protected]

Bettina Kemme

Oana Balmau

McGill University Montréal, Canada [email protected]

McGill University Montréal, Canada [email protected]

ABSTRACT Learned indexes emerged as a promising alternative to classic index structures, offering higher throughput and reduced memory footprint by approximating the cumulative key distribution function through lightweight models. Despite these advantages, learned indexes have seen limited adoption in production systems. One probable reason is that learned indexes that handle concurrent updates and persistence as effectively as, e.g., the B+ -Tree, do not yet exist. Moreover, many research prototypes introduce complex and difficult-to-maintain solutions. In this paper, we take a pragmatic approach to these issues and explore whether we can integrate off-the-shelf learned indexes into a production database system with minimal redesign of the storage system. We use RocksDB, a widely used key-value store with the popular log-structured merge (LSM) architecture, as a case study. RocksDB has a clear separation of main memory based Memtables that ingest writes, and read-only sorted files on disk. This allows us to deploy specialized indexes at each level without the need for a "can-do-all" solution. Our investigation shows that it is not enough to simply use an existing index out-of-the-box under write-heavy workloads, where the frequent replacement of Memtables goes against the learning nature of the index, which needs warm-up time to work well. We address this with an effective reuse mechanism that preserves structural knowledge across Memtable instances. At the disk-level, we replace RocksDB’s index with a learned index without any changes to the remainder of the storage layer or read path. For that, we adapt an effective in-memory read-only index to be block-aware, enabling worst-case single-I/O lookups. We incorporate these findings in an extension of RocksDB we call MountDB. Our evaluation on large-scale workloads with diverse data distributions and access patterns demonstrates that MountDB achieves up to 1.5× faster writes, and 2.1× faster reads compared to state-of-the-art systems, showing that established learned indexes can be incorporated into production systems with negligible overhead and promising results.

1

INTRODUCTION

Since the seminal paper on learned indexes appeared in 2018 [18], there has been a significant body of research on developing learned index structures. This work claims impressive improvements over classic indexes [1, 10, 11, 22, 37]. Still, nearly a decade later, learned indexes are not yet used in production systems, and the question

LSM Tree

RocksDB Memtable

Memtable

(active)

(immutable)

MountDB

Flush

SkipList

L0

SST

SST

SST

Compaction

... Ll

SST

SST

SST

Data block

Index

Bloom filter

ALEX+ (Skeletonized) Learned Index

SST

Fence Pointer Table PGM (Fence) Learned Index

Figure 1: Indexing in LSMs. RocksDB uses classic index structures while MountDB adopts optimized learned indexes.

arises whether they are missing something fundamental that makes them unsuitable for today’s data storage systems. Crucially, it is unclear whether the impressive standalone performance benefits improve end-to-end performance when integrated into a full-fledged database system. There is also the question whether integration is too complicated or too daring, given that much prior work proposes sophisticated policies for learned index integration [6], or building learned databases from the ground up [17]. This paper explores these questions, with Log-Structured Merge (LSM) key-value stores as a case-study. We take a pragmatic approach by analyzing the feasibility of learned indexing in a production environment. More precisely, we look at the integration of learned indexing into RocksDB [8], a popular key-value store (e.g., used at Meta, Uber, Airbnb, Netflix, Nutanix). RocksDB is a Log-Structured Merge (LSM) based datastore. LSM trees are also the backbone of many other storage engines such as LevelDB [13], and Cassandra [19]. LSMs follow a two-component architecture (see Figure 1) that balances write efficiency with query performance. To handle writes, LSMs maintain small sorted in-memory Memtables that ingest updates. Memtables are flushed as immutable, read-only Sorted String Table (SST) files to disk. Background compaction then merges SSTs to maintain key order and reclaim space. Reads first consult the Memtable and then search across the SSTs. To ensure acceptable read latencies, both Memtables and SSTs have their own indexes.

This two-component design of LSMs provides a compelling opportunity to integrate different specialized learned indexes across the two components, choosing for each of them an index whose characteristics fit its local requirements. For the Memtable, we need an updatable concurrent main-memory index, while we can use read-efficient static indexes for the persistent, read-only SSTs. Thus, while a holistic general-purpose learned index that can compete with B+-trees both in-memory and on disk might not yet exist, current solutions might suffice for LSMs. Prior work has integrated learned indexes into the persistence layer (SSTs) of LSMs, in systems such as Bourbon [6], Doblix [14], TridentKV [25], and LeaderKV [39]. While these solutions are promising from a performance point of view, their integration efforts are significant: they either apply complex rules to decide on index creation and management [6, 14], or they redesign the LSM storage structure to accommodate the indexes [14, 25, 39]. We believe that neither approach is appealing for production systems, as a modification to the core of the storage infrastructure would be risky to adopt. We take the opposite approach. Our guiding principle is to integrate learned indexes with as few changes as possible to the existing software stack. To find the right indexes and deploy them efficiently, we analyze the operational constraints of LSMs in-depth. We find two key challenges: one at the memory component, and one at the disk component. First, in LSMs, Memtables are fairly small. This leads to the creation and flushing of many Memtables, resetting the index – a situation that places classic updatable learned indexes at a disadvantage. Second, as noted in prior work [21, 44], special care must be taken to align learned indexes to block-level I/O when using learned indexes for on-disk data. It is a challenge to do so without changing the entire structure of the SSTs (e.g., as done by Doblix [14] and TridentKV [25]). Finally, as each Memtable and SST file needs an index, their creation must have a low overhead and not impact read/write performance. There is potential to piggyback on flushing and compaction operations, creating the indexes off the critical path. The result is MountDB, an LSM key–value store built as an extension of RocksDB. MountDB is the first LSM-based system to employ learned indexes across both memory and disk levels, in conjunction with targeted optimizations specifically designed to address LSMinherent design constraints. Importantly, MountDB introduces minimal modifications to the existing architecture as seen in Figure 1 (right), where only the index components of RocksDB are replaced, thereby preserving the proven advantages of the production system while enabling performance benefits of learned indexing. For its write-heavy Memtables, MountDB uses ALEX+ [40], an updatable learned index that efficiently supports in-place modifications and concurrent inserts. A major issue with ALEX+ and many other learned indexes, is that they have been designed for steady-state workloads and perform best when a large number of records already exist at their creation time, for initialization. However, in LSMs, whenever a new empty Memtable is created, a fresh index accompanies it. To alleviate these cold-start inefficiencies of ALEX+, MountDB introduces a skeletonization optimization that preserves the index structure across Memtable flushes. At the disk level, MountDB adopts the PGM index [10], which offers bounded and fast search capabilities for immutable data. As PGM is a main-memory index that predicts the position of a record

in an array we adjust it to instead predict the block a record resides in. At the same time, we ensure that the index itself remains small and we perform bulk I/O [44] in order to accommodate wrong predictions. MountDB takes the overhead of creating the indexes off the critical path of user requests. Together, these choices allow MountDB to integrate learned indexes across the LSM hierarchy with throughput and latency improvements across-the-board without introducing significant complexity to the workflow. In summary, the key contributions of this paper are as follows: • We present a study showing when state-of-the-art learned indexes might fail when used out of the box in LSMs. • We design and implement MountDB, an LSM system integrating learned indexes into RocksDB with minimal, targeted modifications. • We provide an extensive experimental evaluation of MountDB across six real-world datasets, examining concurrency, varied value sizes, and ablation studies of key design choices. Compared to state-of-the-art learned index solutions in LSMs - DobLIX [14], and TridentKV [25], MountDB achieves up to ∼1.5× faster writes and ∼ 2.1× faster reads, demonstrating that learned indexes can be both practical and efficient in modern LSMs.

2 BACKGROUND AND RELATED WORK 2.1 Log Structure Merge (LSM) Trees The high-level structure of a Log-Structured Merge Tree [29] is presented in Figure 1 (left). LSMs were introduced to efficiently handle write-intensive workloads by exploiting the advantages of both memory and disk-based structures. LSMs employ an append-only approach: updates create new record versions that are appended to an in-memory structure called a Memtable (typically between 64128 MB). When the active Memtable is full, it becomes immutable, and a new, empty Memtable is created. The default Memtable in RocksDB maintains a concurrent SkipList [30] that supports logarithmic lookup of records. Its probabilistic, linked-list-like structure allows for straightforward implementation of non-blocking concurrent operations. Its average-case look-up efficiency, compact meta-information, and simplicity make it a robust and practical index choice for the transient, in-memory component of an LSM. The disk-based component consists of multiple levels of Sorted String Tables (SST). Each of them contains a set of records sorted by key. An immutable Memtable is flushed to disk into an SST at the highest level (L0). As an upper level fills up, a background compaction process merges SSTs from this level with SSTs in the next lower level, in a merge-sort fashion, removing stale records. This hierarchically organizes data, with newer / hot data in smaller, upper levels and older / cold data in larger, lower levels. RocksDB employs a Fence pointer table as the on-disk index, storing one entry per data block in each SST. Each entry consists of the block’s first key and a pointer to its location, leading to the index growing proportionally with the number of blocks. This structure is agnostic to the underlying distribution of keys. Additionally, RocksDB uses Bloom filters to avoid accessing files that do not contain the desired key [27]. A lookup operation first queries the active Memtable, followed by any immutable Memtables, before proceeding to on-disk SST files starting with level L0. First, the Bloom filter is checked for existence,

and then the Fence pointer table is used to locate the data block containing the key-value pair. Within the data block, RocksDB performs a binary search for the record. Given the default block size of around 4 KB, binary search is efficient as these blocks usually contain relatively few records. If the key is not found at level L0, the search continues to deeper levels. This design enables high write throughput while maintaining reasonable read performance. Consequently, LSM-based key-value stores have seen widespread adoption.

2.2

Learned Indexes

Learned indexes reinterpret indexing as a machine learning regression problem: given a set of keys, the index learns the cumulative distribution function of the key distribution and uses it to typically predict the position of a key in a sorted array. A final last-mile search corrects residual errors [18]. This design shifts complexity from a conventional tree traversal to model inference and local refinement, yielding smaller indexes and faster lookups. A foundational learned index design is the Recursive Model Index (RMI) [18], which organizes a hierarchy of models. The root model predicts which sub-model to use, and this process repeats until a leaf model outputs a position. Read-optimized learned indexes have static, read-optimized designs, such as the PGM index [10]. They target immutable datasets. PGM uses piecewise linear models (PLA) to approximate the CDF with a strict error bound 𝜀. The construction minimizes the number of models (segments) needed to satisfy this error, achieving both high compression and deterministic performance: a query touches only a bounded window of ±𝜀 keys. The recursive structure of PGM extends this compression hierarchically, producing one of the most space-efficient indexes with provable guarantees [9, 10, 40]. Updatable learned indexes extend the RMI structure to support efficient insertions and updates. ALEX [7] organizes data in gapped arrays, sorted arrays with strategically placed gaps that locally absorb insertions, minimizing costly full-array shifts. Insertions leverage model-based placement, positioning keys near their predicted locations to maintain spatial locality and reduce future prediction errors. To sustain performance under updates, ALEX employs lightweight cost models that trigger adaptive structural adjustments when nodes become full. Model accuracy is preserved through selective retraining or scaling during expansions, guided by cost deviations rather than periodic reorganization. This design allowed ALEX to support updates efficiently without compromising its read performance. Prior work shows that its best performance is achieved when the model is created by inserting a bulk of data in one shot [40]. ALEX+ [40] extends ALEX by introducing concurrency. It combines fine-grained synchronization with localized updates in gapped arrays, enabling multiple threads to read and write concurrently with minimal blocking. This structure employs optimistic locking at the leaf level, with one lock per data node, and uses per-node shared-exclusive locks for internal nodes [23], allowing safe and efficient parallel operations without undermining the original performance benefits of ALEX. Persistent learned indexes are adaptations of learned indexes to disk storage. Naive adaptation of in-memory indexes to disk failed to outperform a disk-based B+Tree [20]. The performance gap was driven less by model accuracy and more by storage-layer overheads,

including I/O-heavy scans, costly structural modifications, and the maintenance of internal data structures, such as gapped arrays and insertion buffers that were poorly aligned with block-based storage [7]. To address these challenges, AULID [21] was introduced as a disk-native learned index that combined model-based inner nodes with B+Tree-inspired leaf nodes. This hybrid design reduced tree height to lower I/O while preserving the efficiency of B+Trees for leaf operations such as updates, splits, and sequential scans [20]. A complementary line of work has focused on systematically transforming in-memory learned indexes into disk-efficient counterparts. A recent study [44] proposes a set of design principles that guide this transformation, emphasizing techniques such as aligning model error bounds with block boundaries to optimize the last-mile search, prefetching candidate blocks to reduce I/O, compressing model parameters, and reliance on hybrid buffering to handle updates efficiently. These advances highlight that persistent learned indexes may be feasible, either through disk-native designs like AULID or careful transformations of existing structures. Learned indexes in LSMs were first explored in Bourbon [6], which extends WiscKey [26], an LSM system that reduces the high write costs of compactions by performing the separation of keys and values. Bourbon only uses learned indexes in the LSM read-only disk component, and for selected SSTs. Bourbon assumes that index creation is costly and might not be worth for short-lived SSTs. As such, it employs a cost–benefit analyzer that observes the read workload to decide when an index is worthwhile constructing. It then uses greedy piecewise linear regression (Greedy-PLR) [42] to approximate key distributions and speed up lookups. Its indexing method offers less predictable performance than later approaches, such as the PGM index [9], and sometimes even increases tail latency [14, 45]. Finally, its cost-benefit analyzer adds considerable complexity. Subsequent research has built upon Bourbon’s foundation, each addressing its limitations. TridentKV [25] introduces an adaptive training strategy to avoid write-path bottlenecks and redesigns the storage architecture by introducing a partitioning scheme to handle deletions more efficiently. LeaderKV [39] also takes a structural approach, co-designing a new key–value storage layout alongside a hybrid learned index with redirect mechanisms to contain misprediction costs. DobLIX [14] introduces a self-tuning framework that leverages reinforcement learning to dynamically balance index accuracy against the I/O cost. While effective, these systems deploy complex modifications to the LSM’s disk component. Moreover, they all remain focused exclusively to the disk, leaving the in-memory indexing of LSMs unexplored.

3

CHALLENGES WITH EXISTING LEARNED INDEXES

As discussed above, recent advances in learned index design have produced specialized structures for different workload characteristics [10, 28, 40]. A natural approach is therefore to directly integrate state-of-the-art learned indexes into each LSM component: an updatable and concurrent structure, such as ALEX+ [40] for Memtables, and a read-optimized one such as PGM [10] for SSTs. However, when working within a full-fledged system, a simple plug-and-play approach is insufficient. In both the in-memory and disk-resident components, the interaction between learned models

Throughput (Mop/s)

ALEX+ (~1 GB) 1.2 0.9 0.6 0.3

ALEX+ (64 MB)

Amazon Reviews

SkipList (64 MB)

OSM

flush

8.2 12.4 flush 8.9 13.1 Time Window (0.5 sec) Time Window (0.5 sec)

Figure 2: Cold-start behavior of updatable learned indexes. Throughput per interval over 10M inserts for two data distributions: Amazon Reviews (near-linear) and OSM (non-linear). ALEX+ with a large memory budget (1 GB) remains unflushed, delivering high throughput; ALEX+ with a tight budget (64 MB) is subject to frequent flushing and repeatedly incurs cold-start overheads resulting in degraded throughput.

an initial structure-adjustment phase. Under realistic memory limits, however, the Memtable is flushed roughly every ∼0.4 seconds (red dashed line), about three times more frequently than the convergence period of ALEX+. This gap widens for more complex key distributions; for example, on OSM, flushing occurs up to five times more often than convergence, amplifying cold-start overheads. Additional examples of distribution difficulty are presented in Section 5. To sum up, increasing Memtable size reduces cold-start frequency but raises flush costs and risks write stalls [2]. Consequently, addressing the problem requires improving index initialization rather than simply scaling memory. To this end, we introduce a reuse mechanism that preserves structural knowledge across Memtable instances, which we call skeletonization. This technique enables learned indexes to maintain their performance benefits despite frequent flush cycles and is described in detail in Section 4.2.

3.2 and LSM-specific access patterns introduces new challenges that limit performance and feasibility.

3.1

Cold-Start Problem in Memtables

We first explore an out-of-the-box replacement of RocksDB’s SkipList Memtable with ALEX+. Figure 2 compares the throughput of ALEX+ and SkipList in a write-only workload on two data distributions. The experimental setup is the same as described in Section 5. We consider two memory configurations for ALEX+. In the first, ALEX+ is given a 1 GB memory budget, to emulate conditions similar to those used in prior learned index studies [16, 18, 40]. In the second, we constrain ALEX+ to 64 MB, a typical Memtable size in production systems [3, 32]. Whenever the Memtable reaches its capacity, it is discarded and replaced with a new empty instance, emulating the standard LSM flush behavior. The SkipList size is set at 64 MB With a large memory budget, ALEX+ achieves up to ∼3× higher average write throughput than SkipList, consistent with prior work [12]. However, when deployed under realistic LSM constraints, endto-end performance becomes comparable to or worse than SkipList. This degradation stems from the fact that each new ALEX+ instance starts uninitialized and must undergo costly structural adaptations before reaching steady-state efficiency to absorb writes. Unlike common learned-index benchmarks [16, 35], Memtables are much smaller (typically 64-128 MB [8, 29]) and are short-lived. Once full, they are flushed to disk and replaced, leading to frequent rebuilds. These characteristics conflict with the assumptions of many updatable learned indexes, which incur significant initialization overhead and often rely on bulk-loading phases in which a significant fraction of the key space (e.g., up to 50%) is inserted upfront for write-dominant workloads [40]. As a result, a learned index used as a Memtable repeatedly experiences cold starts, rebuilding its internal structure from scratch after each flush. Learned indexes such as ALEX [7], LIPP [41], APEX [23], and XIndex [37] can outperform SkipList in steady-state write-heavy workloads [12], but most assume such bulk-loaded initialization [40]. This is illustrated by the 1GB ALEX+, which quickly converges to high throughput as it learns the key distribution, after

Challenges in Learning Disk-Resident Data

Predicting record positions vs. blocks. Out-of-the-box in-memory learned indexes such as PGM predict the position of a record in a logical contiguous array. In contrast, data on stable storage resides in files that are organized and transferred in units of data blocks or pages. Still, the same indexing principles can be applied to such disk-resident data as long as every data block has the same number 𝑛 of records. In this case, we simply calculate the offset of the block in the file via (𝑏𝑙𝑜𝑐𝑘_𝑠𝑖𝑧𝑒 ∗ 𝑟𝑒𝑐𝑜𝑟𝑑_𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛)/𝑛. However, the true position of a record can differ as defined by the error bounds, and therefore could be in adjacent blocks. If the record is not in the predicted block, neighboring blocks need to be retrieved. This additional I/O cost can be avoided if all blocks within the error bound are retrieved in one I/O [44]. As these blocks are contiguous, I/O will only be slightly more costly, in particular when error bounds are tight. In fact, PGM can work with a very small error bound of 𝜀 = 1, which makes bulk I/O an attractive option. Another option is to use block-aligned variants of PGM [44] so that records are guaranteed to reside in the predicted block. Supporting variable record and block sizes . The challenge is that RocksDB (and other popular LSM implementations such as LevelDB [13], SpeedDB [34], and CockroachDB [36]) does not meet the assumptions required for these techniques: it stores variable-sized records, resulting in a variable number of entries per block, and its block sizes may themselves vary, especially under per-block compression. As a result, indexes such as PGM cannot be used directly, even with the optimizations above. What is required instead is an index that predicts the block of a record without relying on record sizes, block sizes, or intra-block offsets. Several LSM-based designs move in this direction. Systems such as Bourbon [6], LeaderKV [39], TridentKV [25], and DobLIX [14] all train their models to predict the correct block. However, each comes with limitations that make them unsuitable for our goals. Bourbon depends on WiscKey [26], which separates fixed-length keys from values and therefore assumes predictable offsets in a key file. LeaderKV replaces SSTs entirely with a new storage format, while TridentKV introduces its own partitioning scheme. TridentKV and DobLIX both design a custom data block format. Moreover, they often rely on large blocks to reduce the likelihood of prediction

1 1

2b 2

C0: Memory

3b Flush

3

L0 SST1

L0 SSTN1

2a C1: Secondary Storage

4 Compaction L1 SST1

L1 SSTNn

3a ...

Figure 3: MountDB’s operational flow. The read and writes paths are virtually identical to those of RocksDB. MountDB pushes the complexity of learned index maintenance into the LSM housekeeping tasks, flushing and compaction. errors, but such oversized blocks can lead to lengthy I/O operations and memory contention. In short, all of these systems modify the SST or block layout, whereas our objective is to keep RocksDB’s SST format and block serialization unchanged. We seek only to replace the Fence Pointer index with a learned alternative. We therefore introduce PGM (Fence), a block-aligned variant of PGM that preserves the advantages of the original model while guaranteeing block-level predictions. PGM (Fence) is highly compact because it trains on only one key per block—an idea inspired by Aulid [21], a hybrid learned index for traditional RDBMSs (see Section 2). PGM (Fence) ensures worst-case single-I/O lookup, supports variable-sized records and compressed blocks, and operates directly on unmodified RocksDB SSTs and data block layouts. Section §4.3 details its design and integration into MountDB.

4

MOUNTDB DESIGN & OPTIMIZATIONS

This section describes how MountDB serves write and read operations, with minimal modifications to the classic LSM workflow.

4.1

MountDB Operation Flow

While MountDB is generally compatible with LSM key-value stores, we illustrate our techniques in an implementation extending RocksDB. The write and read paths in MountDB largely follow the conventional LSM workflow, reusing most of the RocksDB logic. Figure 3 illustrates these operations across the LSM hierarchy. Write path. In RocksDB, writes insert a new key–value pair into the Memtable ①. The underlying memory for key–value storage is managed by the arena allocator, which allocates contiguous chunks, and keys are appended sequentially in insertion order. Additional meta-information builds a SkipList that connects records according to their keys. This SkipList is traversed to quickly find records with specific key values. In MountDB, we replace this meta-information with an ALEX+ index where the leaf nodes, instead of storing full key-value pairs, maintain pointers to the actual records.

Read path. The read path in MountDB is identical to that of RocksDB, with the exception that the RocksDB SST Fence Pointer Table index is replaced with a PGM (Fence) index. Like in RocksDB, lookup requests traverse the LSM hierarchy top-down. The search begins with probing the active ALEX+ Memtable, followed by the immutable Memtable ①. If the key is not found in memory, the search proceeds to 𝐿0 . Bloom filters quickly eliminate irrelevant files ②𝑎 . If a Bloom filter indicates presence, the corresponding SST index is loaded into the OS page cache and used to determine the target data block, which is then also loaded into memory, and a binary search is performed to locate the key ②𝑏 . For subsequent requests, the index remains cached in the OS page cache. For deeper levels (L1 , L2 , . . . ), the same process is repeated: ③𝑎 Bloom filters are checked, and ③𝑏 the SST index guides access to the target block. Background operations: flushing and compaction. A key feature of MountDB’s design is pushing the complexity of learned index creation and maintenance off the critical path, in the LSM housekeeping operations. During flushing in RocksDB, when the active Memtable reaches its memory budget, it is marked immutable, and a new Memtable is created ②. In MountDB, we additionally apply skeletonization to initialize the new Memtable using the structure of the previous immutable instance, mitigating cold-start inefficiencies (see Section 4.2). Note that we perform skeletonization only periodically, reusing the same skeleton for several new Memtables to reduce overhead. Next, the immutable Memtable is flushed to disk, producing the SST’s data blocks. Once the data portion of the SST is materialized, instead of creating the conventional RocksDB Fence Pointer Table, MountDB constructs the PGM (Fence) index over the SST’s fence keys (see Section 4.3). Because the keys are already sorted, index construction is efficient. The PGM (Fence) index and the existing Bloom filter from RocksDB are then appended as metadata, finalizing the SST, which is persisted to disk ③.

Compaction follows the same principle as in RocksDB. When SSTs at 𝐿0 are merged, their key ranges are combined to produce the data blocks of a new SST. Once the merged data is materialized, MountDB constructs a new PGM (Fence) index over the resulting fence keys. The index is then appended to the SST as metadata, and the finalized file is persisted to disk ④. In this work, we focus on numeric keys. Learned indexing techniques for strings have been proposed in prior work [14, 25, 33, 38, 39, 43, 46]. However, they are often specifically designed for strings [14, 33, 38, 43, 46] and thus, are orthogonal to learned indexes for numeric keys, or require changing the storage format of the records [25]. Therefore, integrating these approaches with MountDB’s architecture is a promising direction that we leave to future work.

4.2

Solving the Cold-Start Problem with Skeletonization

To make ALEX+ effective as a short-lived Memtable, MountDB introduces a novel skeletonization mechanism that reuses the structure of previous Memtables. As mentioned in Section 3, one of the assumptions when using learned indexes is that their initialization cost would be amortized over a long usage period. On a high level, skeletonization effectively freezes the internal structure of the learned index, assuming that the key distribution patterns evolve slower than the rate of flushing of the Memtable. Algorithm 1 describes how MountDB applies skeletonization to ALEX+ Memtables. Initially, the first two Memtables are created from scratch and are empty. Once the first Memtable reaches its budget and is marked as immutable, it is flushed to disk while a new active Memtable begins absorbing inserts. In the background, MountDB invokes the standard bulk-load operation of ALEX+ on the immutable Memtable’s sorted keys (line 22) to construct an optimized ALEX+ instance. From this bulk-loaded instance, MountDB extracts a skeleton that retains only the structural components defining the index layout. This is achieved through a selective deep copy of the bulkloaded ALEX+ instance (see lines 34-35). The skeleton preserves the following: 1) a complete hierarchy of model and data nodes, 2) all parent–child relationships, 3) inter-node links that connect adjacent data nodes (used for leaf-level iteration), and 4) key-placement metadata such as the keys and gaps in the gapped arrays. Importantly, for gapped arrays, MountDB maintains the exact spatial pattern of gaps by preserving the bitmap representation that marks occupied versus free slots within each array. Consequently, the model and data nodes preserve the learned key distribution from the previous workload, while the preserved gaps capture the fine-grained insertion topology that emerged from prior Memtable creation. In contrast, all data-dependent elements, such as payloads, statistical counters for number of inserts, lookups, key shifts and node resizes, along-with lock states, are reset (described in lines 25-31), delivering a clean skeleton for reuse. Effectively, the skeleton preserves the expensive structural foundation of the previous Memtable. When a new Memtable is created, it is initialized from this skeleton, allowing new insertions to immediately leverage the optimized index layout. During insertion, if the target key position in the gapped array already contains an

Algorithm 1 Skeletonization of ALEX+ Memtables Input: 𝜙: skeletonization frequency, Memtablesize : memory budget Initialize: S: global skeleton (S ← NULL), 𝑐: flush counter (𝑐 ← 0) 1: 𝑀active ← ALEX+() ⊲ initialize first Memtable from scratch 2: for each write operation do 3: 𝑀active .Insert(𝑘, 𝑣) 4: if 𝑀active .Size( ) ≥ Memtablesize then 5: 𝑀immutable ← 𝑀active ⊲ read-only 6: 𝑀active ← CreateNewMemtable( S) 7: 𝑐 ←𝑐 +1 8: if 𝑐 mod 𝜙 = 0 then ⊲ create skeleton in background 9: ScheduleBackgroundTask(CreateSkeleton,

𝑀immutable ) 10: end if 11: end if 12: end for 13: function CreateNewMemtable(S) 14: if S = NULL then ⊲ no skeleton available (initial case) 15: return ALEX+( ) 16: else 17: return ALEX+( ).CopySkeleton( S) 18: end if 19: end function 20: procedure CreateSkeleton(𝑀) 21: 𝐾sorted ← 𝑀 .GetSortedKeys( ) ⊲ extract sorted keys 22: 𝑀temp ← ALEX+( ).BulkLoad(𝐾sorted ) ⊲ build optimal structure 23: for each dataNode 𝑑 in 𝑀temp .DataNodes( ) do 24: for 𝑖 ← 0 to 𝑑.dataCapacity do 25: 𝑑.payloadSlots[𝑖 ] ← nullptr ⊲ clear payloads 26: end for 27: 𝑑.𝑛𝑢𝑚𝐼𝑛𝑠𝑒𝑟𝑡𝑠 ← 0 ⊲ reset stats 28: 𝑑.𝑛𝑢𝑚𝐿𝑜𝑜𝑘𝑢𝑝𝑠 ← 0 29: 𝑑.𝑛𝑢𝑚𝑆ℎ𝑖 𝑓 𝑡𝑠 ← 0 30: 𝑑.𝑛𝑢𝑚𝑅𝑒𝑠𝑖𝑧𝑒𝑠 ← 0 31: 𝑑.ResetLock( ) 32: end for 33: 𝑀temp .RemovePayloads( ) 34: S ← 𝑀temp .CopyModelNodes( ) ⊲ includes models and links 35: S ← 𝑀temp .CopyDataNodes( ) ⊲ includes gapped arrays & keys 36: end procedure

existing key, MountDB inspects its corresponding payload pointer. A nullptr indicates that the slot is free, the existing key can be overwritten with the new key, and the payload pointer is updated to reference the new value. This reuse of pre-allocated gaps and key slots enables efficient inserts without triggering structural modifications or reorganization. As a result, MountDB achieves efficient writes while preserving the learned model hierarchy and spatial layout of previous Memtables. MountDB does not create a new skeleton after each Memtable flush but instead reuses the same skeleton for consecutive Memtables. To adapt to shifting key distributions, MountDB introduces a parameter 𝜙 that determines how frequently (in terms of number of flushes) the skeletons are refreshed. Based on empirical evaluation, we set 𝜙 = 10. All skeleton creation and maintenance are performed

kq

Algorithm 2 PGM (Fence) Index: Construction and Lookup

PGM (? = 1) pos prefetch of f s et s [ pos - 1, pos +1]

SST

... search (pos, pos- 1, pos+1)

(a)

(b)

Figure 4: (a) Fence-Key Modeling & (b) Lookup in PGM (Fence)

during the flush operation, off the critical path, ensuring that foreground write throughput remains unaffected. The overhead introduced by skeletonization is minimal, discussed in Experiment 5.5, accounting for only ∼2.1% of the time of an average flush operation.

4.3

PGM (Fence): Maintaining a Single I/O per Lookup with Variable Size Records

As explained in Section 3, our objective is to integrate a learned index at the disk-level with minimal modification to the existing LSM storage structure. In particular, MountDB only replaces the fence pointer table in each SST while keeping the data block structure unchanged, reusing RocksDB’s efficient binary search on variable length records inside the block. Given a query key, the learned index needs to find the offset of the block in the SST that contains the corresponding record. A crucial concept in our approach is that we do not train the index over all keys in the SST but only over the key of the first record of each block [21]. Whether a query requests this first record or any other record in a block 𝑏, the index will estimate 𝑏’s offset or the offset of one of 𝑏’s adjacent blocks. This reduction in training records reduces not only learning time but also index size. Our index PGM (Fence) is a block-aware adaptation of the PGM index. Algorithm 2 illustrates the construction and lookup procedure. After an SST is materialized, MountDB performs a single pass over the block metadata to extract from each data block (line 3): (i) the key of the first record in the block, which we refer to as fence key, and (ii) the byte offset of the block. The fence keys are stored in a temporary array 𝑓 , which is discarded at the end of the learning process. The offsets are stored in an offsets array 𝑜. Both are illustrated in Figure 4(a). Note that both arrays are of same length, with 𝑓 [𝑖] storing the first key of block 𝑖 and 𝑜 [𝑖] the offset of block 𝑖. We then train a PGM solely on the ordered fence-key sequence 𝑓 , i.e., PGM will learn the position of each fence key in 𝑓 . The PGM model is trained with the tightest error bound 𝜀 = 1 (line 7), enabling the index to exploit the model’s error guarantees and limit the lookup window to at most 3 positions (blocks). After training, the temporary fence-key array is discarded, and only the learned model, together with the offsets array, is stored alongside the SST. At lookup time, the PGM model predicts the position 𝑝 of the query key 𝑘𝑞 within the fence-key sequence 𝑓 (line 12). Since each

Input: S: SST with sorted sequence of blocks {𝐵 1, 𝐵 2, . . . , 𝐵 𝑁 }, 𝑘𝑞 : lookup key Initialize: Pfence : PGM (Fence) Index (Pfence ← NULL), 𝑜: offsets array (𝑜 ← ∅) 1: function Train(S) 2: 𝑓 : fence-keys array (𝑓 ← ∅) 3: for block ∈ S do 4: 𝑓 [𝑖 ] ← block.firstKey 5: 𝑜 [𝑖 ] ← block.blockOffset 6: end for 7: Pfence ← TrainPGM( 𝑓 , 𝜀 = 1) 8: 𝑓 ←∅ 9: return Pfence 10: end function

⊲ deallocate fence-key array

11: function Lookup(𝑘𝑞 ) 12: 𝑝 ← Pfence .predict(𝑘𝑞 ) ⊲ position in 𝑓 (search window = 2𝜀 + 1) 13: 𝑖𝑑𝑥 start ← max(0, 𝑝 − 1) 14: 𝑖𝑑𝑥 end ← min(𝑜.length − 1, 𝑝 + 1) 15: bytestart ← 𝑜 [𝑖𝑑𝑥 start ] 16: byteend ← (𝑖𝑑𝑥 end + 1 < 𝑜.length) ? 𝑜 [𝑖𝑑𝑥 end + 1] : EOF 17: Bmem ← Prefetch( K, bytestart , byteend ) ⊲ single I/O 18: for block ∈ Bmem [𝑝, 𝑝 − 1, 𝑝 + 1] do ⊲ prioritize block order 19: (Found, record) ← binarysearch(block, 𝑘𝑞 ) 20: if Found then 21: return record 22: end if 23: end for 24: return NotFound 25: end function

fence key uniquely represents a block boundary, the predicted position 𝑝 directly maps to the same position 𝑝 in the corresponding offsets array 𝑜, which will give us the Byte offset of the estimated block for 𝑘𝑞 . Since the error bound 𝜀 = 1, the record will be in the estimated block or its left resp. right neighbor block (lines 1314). Therefore, only a small window of candidate blocks needs to be examined, which is three in this case, as shown in Figure 4(b). The corresponding byte ranges are then prefetched in a single request using RocksDB’s FilePrefetchBuffer (line 17), preserving RocksDB’s default block-oriented access pattern without modifying the storage layout. Typically, LSM datastores have the block size configured to a multiple of 4KB, to take advantage of the access granularity of SSDs. To avoid I/O amplification caused by retrieving 3 blocks instead of a single block, MountDB configures the default maximum block size of the LSM datastore to a third of its default. Within the prefetched region, the final key lookup is performed using RocksDB’s existing binary search inside each block. The predicted (middle) block is binary-searched first, followed by the left and right neighbors if necessary (lines 18–22 in Algorithm 2). Our empirical observations show that approximately 78% of positive lookups are resolved in the predicted block, with 14% and 8% in the left and right neighbors, respectively, making this search ordering effective in minimizing lookup latency. A final advantage of indexing on the block start as opposed to over the entire key range is the significant reduction in index size. The learned PGM model together with the offsets array take

0.4 0.0 0.8 0.4 0.0 2.4 1.2 0.0

Latency (µs)

0.8

TridentKV YCSB 70

Latency (µs)

YCSB

MountDB DobLIX Covid Facebook Genome OSM

70

Latency (µs)

Write Only Balanced Read Only

Throughput (Mop/s) Throughput (Mop/s) Throughput (Mop/s)

Figure 5: Cumulative distribution function (CDFs) of real-world datasets, ordered by increasing indexing difficulty (left to right)

RocksDB Covid Facebook Genome OSM

50 30

50 30 45 30 15

(a) Average Throughput

(b) 90p and 99p Latency

Figure 6: Large-Scale Workloads. (a) Average throughput and (b) 90th and 99th percentile latencies across five datasets, each ∼55 GB, with 16 application threads. Results are shown for write-only (top), balanced (50% reads / 50% writes, middle), and read-only (bottom) workloads under a uniform access pattern. less than 172KB per SST even under the most challenging key distributions we evaluated. While this is not significant inside each SST (as their default size is in the order of tens of MBs, e.g., 64MB), we show that the small PGM size provides an advantage in readintensive workloads. As the index is small, more records can be cached within the same memory budget, leading to higher read throughput.

5

EVALUATION

We structure our evaluation around four main questions: • What is MountDB’s end-to-end performance with different readto-write ratios and key distributions? (Section 5.2) • Can MountDB adapt to changing key distributions over time, especially on the write path? (Section 5.3) • Do MountDB’s indexes provide a latency advantage on the read path, especially for disk-resident data? (Section 5.4)

• How much overhead do learned indexes introduce in LSMs, particularly to flush and compaction operations? (Section 5.5)

5.1

Experimental Setup

Hardware. All experiments were conducted on a machine running Ubuntu 22.04.5 LTS, equipped with two Intel Xeon E5-2690 v4 CPUs, each with 14 cores running at 2.60 GHz, 126 GB of RAM, and a 500 GB NVMe SSD for storage. Baselines. We compare MountDB against three LSM-based baselines: two state-of-the-art learned indexing systems1 , DobLIX and TridentKV, and a production-grade LSM, RocksDB (v8.10.0). All 1 The publicly available code for DobLIX [15] and TridentKV [24] uses older versions

of RocksDB (5.1.2 and 5.4.10, respectively from 2017). For fairness, we ported both systems to RocksDB v8.10.0. Additionally, the DobLIX repository does not include the RL-based tuner described in the paper.

MountDB

DobLIX TridentKV (a) Zipfian Distribution

Throughput (Mop/s)

3.0

RocksDB

1.5 0.0

(b) Uniform Distribution

3.0 1.5

no me OS M

B

Ge

E (W:5 SC:95)

YC S

B no me OS M Ge

D (W:5 R:95)

YC S

B no me OS M

C (W:0 R:100)

Ge

YC S

B no me OS M

YC S

B no me OS M

YC S

B (W:5 R:95)

Ge

A (W:50 R:50)

Ge

Ge

YC S

B no me OS M

0.0 F (W:50 RMW:50)

Figure 7: Throughput comparison across the six YCSB workloads (A–F) and three datasets (YCSB, Genome, OSM) under (a) Zipfian and (b) Uniform access distribution. baselines are configured identically to MountDB in terms of Memtable size, cache allocation, and compaction resources. All experiments are run through the standard benchmarking tool db_bench. Bourbon [6], the first system to add learned indexes into an LSM, is omitted as prior work [14] shows that DobLIX and TridentKV outperform it. Additionally, LeaderKV [39] is not open source. Datasets. We use six datasets with diverse real-world key distributions. Figure 5 shows the datasets ordered by increasing indexing difficulty [40]. Amazon Reviews contains 21.9M unique keys, while each of the other datasets contains 200M unique keys. Facebook and OSM appeared in the SOSD benchmark [16], YCSB in ALEX+’s evaluation [5, 7], Amazon Reviews in Bourbon’s evaluation [6], Covid and Genome appear in the GRE benchmark [40]. For read:write ratios we use the YCSB [5] benchmark suite with the 6 default access patterns. System configuration. Unless otherwise specified, we use default RocksDB configuration with two 64 MB Memtables (one active and one immutable) and a 32 MB block cache, reserved exclusively for data blocks. For large-scale experiments we use a 2 GB block cache. Compactions are executed with 8 worker threads. Compression is disabled. We run all workloads with 16 client threads. For all experiments except those that analyze the impact of value size and test performance under variable KV pairs, records consist of 8-byte keys and 100-byte values. Each experiment is repeated three times, and we report the average across runs.

5.2

End-to-end Results

Varying key distribution. Figure 6 reports the average throughput (Figure 6(a)) and tail latencies (Figure 6(b)) across write-only,

balanced (1:1 read–write ratio), and read-only workloads on multiple datasets with different key access patterns. Each dataset is approximately 55 GB in size, and each run executes 500M operations. For write-only workloads (top row), MountDB achieves up to 1.3× higher throughput against SkipList, which is used by all other baselines. Even on the most challenging dataset (OSM), the throughput improves by around 1.2×. Since write-heavy workloads primarily stress the in-memory components of the LSM, these improvements stem from the optimized Memtable index and the use of skeletonization to mitigate cold-start overheads in updatable learned structures. In contrast, the other baselines retain the default SkipList-based Memtable implementation and therefore exhibit performance comparable to RocksDB, as they do not modify or optimize the in-memory indexing layer. The balanced workload (middle row) shows consistent throughput improvements across datasets, reaching up to 1.3× over DobLIX, 1.4× over TridentKV, and 1.44× over RocksDB. These gains arise from the combined effect of the in-memory ALEX+ index and the disk-resident PGM (Fence) index. Because lookups first probe the Memtables, ALEX+ improves both update efficiency and the latency of recent reads, while PGM (Fence) accelerates access to keys that are not resident in memory by narrowing the block search space. Read-only workloads exhibit the largest relative improvements, with throughput gains of up to 1.29× compared to DobLIX, 1.58× compared to TridentKV, and 1.77× compared to RocksDB. Latency reductions at the 90th and 99th percentiles are consistent with the throughput improvements. For write-only workloads, MountDB reduces tail latencies by 1.3× on YCSB and achieves smaller but consistent reductions on harder datasets (1.1×). Balanced and read-only workloads exhibit a similar ordering across systems, with MountDB and DobLIX consistently showing lower tail latencies. This behavior stems from the use of learned indexing, which reduces lookup variability by narrowing the search space and, in most cases, limiting the lookup path to a single disk I/O.

Performance under Varying and Mixed Value Sizes. LSM systems are notorious for not being able to handle small value sizes well, with special LSM systems being proposed to mitigate this problem (such as PebblesDB [31]). We show that using learned indexes can offer an elegant solution to this problem. We first study the impact of value size on system performance, shown in Figure 8(a). The key size is fixed at 8 bytes, while value size is reduced from 512 to 16 bytes. Memtable capacity remains fixed at 64 MB, meaning smaller values allow each Memtable to hold proportionally more records. For writes, the SkipList implementation used by the baselines exhibits nearly constant throughput across all value sizes on both datasets. This stability follows from its O (log 𝑛) insertion complexity, which is largely insensitive to the number of stored key–value pairs [30]. In contrast, MountDB shows steadily increasing throughput as value size decreases. With smaller values, ALEX+ stores more records within the same Memtable capacity, providing additional training data for model refinement. This improves the

RocksDB

Amazon Reviews

OSM

51 2 25 6 12 8 64 32 16

MountDB - PGM (Fence) Only DobLIX TridentKV

51 2 25 6 12 8 64 32 16

Read

Write

Throughput (Mop/s) Throughput (Mop/s)

MountDB 1.2 1.0 0.8 0.6 9.0 6.0 3.0 0.0

Value Size (B)

Value Size (B)

(a) Scaling Value Size

Read

Throughput (Mop/s)

In contrast, TridentKV exhibits a wider tail distribution, due to variability in its block sizes and longer last-mile searches. These trends remain consistent even on more challenging datasets such as Genome and OSM, where the performance gap between MountDB and DobLIX becomes more pronounced, with MountDB exhibiting consistently smaller tail latencies. Varying read-write patterns. The goal of this experiment is to evaluate performance across a wide range of workload mixes and access patterns using the YCSB benchmark suite. We consider three datasets with distinct key distributions (YCSB–easy, Genome– medium difficulty, and OSM–hard) and the six YCSB workloads: A (update-heavy), B (read-mostly), C (read-only), D (read-latest), E (scan-heavy), and F (read-modify-write). Following the standard YCSB setup, each workload is evaluated under both Zipfian and uniform access distributions. Figure 7 reports the average throughput across these settings. Across all workloads and datasets, MountDB consistently achieves the highest throughput. In update-heavy workloads (A and F), throughput improvements reach up to 1.2–1.3× over DobLIX, 1.3– 1.4× over TridentKV, and around 1.4× over RocksDB, reflecting the efficiency of the optimized write path of MountDB. For read-dominant workloads (B, C, and D), MountDB maintains clear performance advantages, with throughput gains typically in the range of 1.17–1.3× over DobLIX and 1.2–1.4× over TridentKV. These improvements arise from the combined effect of skeletonized ALEX+ and PGM (Fence), which together reduce lookup overhead across both hot and cold data. In the scan-heavy workload (E), MountDB continues to outperform all baselines, with gains of up to 1.25× , demonstrating that narrowing the search space at the block level also benefits workloads that access contiguous key ranges. Access distribution influences performance trends but does not change the relative ordering. Under Zipfian access patterns (Figure 7, top-row), the performance gap widens slightly due to improved cache locality and faster adaptation of learned indexes. Across datasets, smoother key distributions (e.g., YCSB) yield larger improvements, while more irregular distributions such as OSM narrow the margins but still show consistent gains, highlighting MountDB’s robustness across diverse data distributions.

4 2 0

UDB

ZippyDB

UP2X

(b) Mixed Value Size

Figure 8: Impact of variable and mixed value size. (a) Write (top) and read (bottom) throughput as value size decreases. (b) Performance under mixed value size workloads (UDB, ZippyDB, UP2X).

model-to-data ratio, allowing each learned model to predict positions for a larger set of keys and thereby reducing lookup and update overheads. Consequently, write throughput improves as value size decreases showing up to 1.5× throughput improvements. For reads, throughput increases for all systems as value size decreases due to reduced I/O and improved cache residency. MountDB benefits additionally from the combined effect of ALEX+ and the PGM (Fence) index. As a result, MountDB achieves up to 2.8× higher read throughput compared to RocksDB, and up to 2.1× compared to DobLIX for the smallest value sizes. We also evaluate performance under mixed value size workloads derived from real-world RocksDB deployments: UDB (avg value = 126.7 B, 𝜎 = 22.1 B), ZippyDB (avg value = 42.9 B, 𝜎 = 26.1 B), and UP2X (avg value = 46.8 B, 𝜎 = 11.6 B) [4]. Across all workloads, MountDB consistently achieves the highest read throughput (see Figure 8(b)). It outperforms DobLIX by 1.2–1.4× across workloads and exceeds RocksDB by 1.3–1.6×, with the largest gains observed in UP2X. The PGM (Fence)-only configuration also improves throughput relative to the baselines, but the end-to-end MountDB design consistently delivers larger improvements, reflecting the advantages of full-stack learned indexing.

Write Throughput (Mop/s)

1.2 0.9 0.6 0.3

MountDB ( = 10)

YCSB

MountDB (Single Skeleton)

Amazon Reviews

Covid

MountDB (no Skeletonization)

Facebook

Genome

RocksDB

OSM

Figure 9: Microbench - Varying Key Distribution. Write throughput of 1) MountDB (𝜙=10) - a new skeleton created every 10 flushes, 2) MountDB - single skeleton, 3) MountDB without skeletonization, and 4) RocksDB SkipList. The key distribution changes every ∼16.7M operations to cycle through different dataset key distributions. Completion time: MountDB (𝜙=10) = 98 sec, MountDB (Single Skeleton) = 127 sec, MountDB (no Skeletonization) = 146 sec, and RocksDB = 161 sec.

5.3

Adapting to Workload Shifts

In this section, we provide a detailed analysis of MountDB’s skeletonization optimization. We study the impact of skeletonization under fluctuating key distributions. This experiment shows a writeonly workload that cycles through all six datasets shown in Figure 5, issuing approximately 16.7M inserts per dataset for a total of 100M inserts. For each dataset interval, we observe roughly 35 Memtable flushes, during which the systems are subjected to different key distributions. In all settings, 16 workers issue writes concurrently. We compare four configurations: 1) MountDB (𝜙=10) uses skeletonization with periodic refresh. In this setting, the ALEX+ index of the Memtable is recreated from scratch based on the data of the previous immutable Memtable every 10 flushes. All other times, the skeleton is reused. 2) MountDB (Single Skeleton) reuses the same (i.e., first) skeleton after each Memtable flush. 3) MountDB (no Skeletonization), where the learned index is rebuilt from scratch for every Memtable. 4) RocksDB’s SkipList, as a baseline. Figure 9 shows the measured write throughput as a function of write operations completed. MountDB (𝜙=10) maintains a steady throughput across all six datasets, sustaining around 0.95–1.05 Mops/s throughout the 100M inserts. The periodic skeleton refresh prevents costly full reconstructions, while allowing MountDB to adapt to rapidly shifting key distributions without throughput penalties. The single-skeleton variant performs well for the first, simpler distributions (e.g., YCSB and Amazon Reviews), but begins to struggle as the workload transitions to more challenging distributions such as Covid, Facebook, Genome, and OSM. In these phases, throughput drops noticeably, showing that relying on a fixed skeleton limits adaptability to large CDF shifts. The skeleton created when the distribution was simple cannot provide adequate performance for more complex distributions. The no Skeletonization configuration exhibits cold-start inefficiencies throughout the experiment, as pointed out in Section 3. Lastly, RocksDB’s SkipList remains stable and insensitive to changing distributions but maintains a lower steady-state throughput of 0.6–0.7 Mops/s, falling below all other configurations.

5.4

Read Performance Analysis

Next, we analyze the read path to understand the sources of performance improvements and isolate the contributions of in-memory and on-disk indexing. Figure 10 reports read throughput under

different caching regimes (a–c), along with the impact on SST size (d) and a latency breakdown of the read path (e). We first consider a scenario where the entire working set is cached. In this case, MountDB achieves the highest throughput, outperforming the baselines by approximately 1.34–1.52× across datasets. Importantly, even the PGM (Fence)-only configuration delivers a considerable improvement, exceeding DobLIX by 1.16–1.22× with the gap more pronounced on the harder OSM distribution. In this setting, performance is strongly influenced by index size , where PGM (Fence) is roughly an order of magnitude smaller than DobLIX, resulting in more efficient in-memory lookups and more substantial gains relative to the other baselines. We next evaluate a partially cached scenario where only 10% of the working set fits in memory (Figure 10(b)). MountDB maintains consistent advantages, with throughput improvements of roughly 1.2–1.3× across datasets. Compared to the fully cached scenario, the gap narrows as disk access begins to dominate. For the PGM (Fence)-only configuration, the gains relative to DobLIX remain in the range of 8–12%, with larger improvements again observed on the harder distribution. To isolate the impact of disk access, we further evaluate an I/Obound configuration (Figure 10(c)) where each lookup that is not served from the Memtable results in a storage access. To simulate this setting, we enable the use_direct_reads flag in db_bench, bypassing the page cache and forcing I/O on every SST access. In this case, throughput across systems becomes virtually the same, as disk latency dominates the overall cost. MountDB still shows slight improvements due to a fraction of lookups being satisfied directly from the Memtable; however, since most requests incur I/O, the overall gains remain modest. Figure 10(d) examines the relative impact of index structures on SST size. Across all systems, the index constitutes only a small fraction of the total SST footprint. Specifically, TridentKV has the smallest relative overhead at approximately 0.025% (16 KB) of the SST size (64 MB), followed by MountDB’s PGM (Fence) at 0.26% (172 KB), and RocksDB’s fence pointer table at 0.45% (296 KB). DobLIX incurs the largest index overhead, reaching up to 2.42% (1.55 MB), which is about ∼ 9× bigger than PGM (Fence). Finally, Figure 10(e) shows a breakdown of the average read latency for the balanced workload presented in Figure 6 (middle row), comparing MountDB and DobLIX. On average, the latency

8x 9x 7%

11%

Time (ms)

Figure 10: Read Performance Analysis. Workload with (a) All data cached (fits in memory), (b) 10% Data cached, (c) I/O-bound with page cache bypassed, (d) Impact on SST size, and (e) Read latency breakdown on a balanced workload showing contributions from in-memory and on-disk index.

800 400 0

MountDB Doblix (a) Flush 1.7%

TridentKV (b) Compaction

RocksDB

2.1%

Amazon Reviews OSM

Amazon Reviews OSM

Figure 11: Overhead of Learned Index Techniques on Background Operations.

improvement is primarily driven by faster disk-level lookup, where PGM (Fence) provides approximately 7–11% faster block localization than DobLIX. Although Memtable lookup in MountDB is 8–9× faster than the SkipList, the absolute latency of this stage is small; therefore, its contribution to end-to-end latency is less pronounced once I/O becomes part of the critical path.

5.5

Overhead of Learned Index Creation

Lastly, we evaluate the runtime overhead introduced by learned indexing during background operations. Figure 11 reports the time spent in flush and compaction phases, isolating the cost of index construction. During a flush, MountDB performs skeletonization to initialize the Memtable (ALEX+) for future instances. To quantify its cost, we measure flush time with and without this step. As shown in Figure 11(a), the additional overhead remains small, increasing flush latency by only 1.7% on Amazon Reviews and 2.1% on OSM. This demonstrates that preserving structural knowledge across Memtables incurs negligible runtime cost while enabling faster steady-state performance. During compaction, all systems construct their on-disk index structures. Figure 11(b) shows that MountDB, DobLIX, and RocksDB exhibit nearly identical compaction times across both datasets, indicating that building learned index structures introduces no additional overhead. Overall, compaction latency remains within a narrow range across systems, confirming that learned index construction does not meaningfully affect background operations.

6

CONCLUSION

We introduced MountDB, the first LSM-based key-value store to integrate learned indexes across both in-memory and disk levels. By combining ALEX+ with skeletonization for Memtables and PGM (Fence) for SSTs, MountDB improves read and write performance on various real-world data distributions and workloads. MountDB is a step towards motivating learned index adoption in production environments by emphasizing simplicity of integration.

REFERENCES [1] Abdullah Al-Mamun, Hao Wu, Qiyang He, Jianguo Wang, and Walid G. Aref. 2025. A Survey of Learned Indexes for the Multi-dimensional Space. ACM Comput. Surv. (2025). https://doi.org/10.1145/3768575 [2] Oana Balmau, Florin Dinu, Willy Zwaenepoel, Karan Gupta, Ravishankar Chandhiramoorthi, and Diego Didona. 2019. SILK: Preventing latency spikes in LogStructured merge Key-Value stores. In USENIX Annual Technical Conference. [3] Oana Balmau, Rachid Guerraoui, Vasileios Trigonakis, and Igor Zablotchi. 2017. FloDB: Unlocking Memory in Persistent Key-Value Stores. In Proceedings of the 12th European Conference on Computer Systems, EuroSys. [4] Zhichao Cao, Siying Dong, Sagar Vemuri, and David H. C. Du. 2020. Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook. In 18th USENIX Conference on File and Storage Technologies, FAST 2020, Santa Clara, CA, USA, February 24-27, 2020, Sam H. Noh and Brent Welch (Eds.). USENIX Association, 209–223. https://www.usenix.org/conference/fast20/ presentation/cao-zhichao [5] Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking cloud serving systems with YCSB. In Proceedings of the 1st ACM symposium on Cloud computing. [6] Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2020. From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI). https: //www.usenix.org/conference/osdi20/presentation/dai [7] Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David B. Lomet, and Tim Kraska. 2020. ALEX: An Updatable Adaptive Learned Index. In Proceedings of the International Conference on Management of Data (SIGMOD). https://doi.org/10.1145/3318464.3389711 [8] Siying Dong, Mark Callaghan, Leonidas Galanis, Dhruba Borthakur, Tony Savor, and Michael Strum. 2017. Optimizing Space Amplification in RocksDB. In 8th Biennial Conference on Innovative Data Systems Research (CIDR). https:// cidrdb.org/cidr2017/papers/p82-dong-cidr17.pdf [9] Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra. 2020. Why Are Learned Indexes So Effective?. In Proceedings of the 37th International Conference on Machine Learning (ICML), Vol. 119. https://proceedings.mlr.press/v119/ ferragina20a.html [10] Paolo Ferragina and Giorgio Vinciguerra. 2020. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds. Proc. VLDB Endow. 13, 8 (2020). https://doi.org/10.14778/3389133.3389135 [11] Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. 2019. FITing-Tree: A Data-aware Index Structure. In Proceedings of the International Conference on Management of Data (SIGMOD). https: //doi.org/10.1145/3299869.3319860

[12] Jiake Ge, Boyu Shi, Yanfeng Chai, Yuanhui Luo, Yunda Guo, Yinxuan He, and Yunpeng Chai. 2023. Cutting Learned Index into Pieces: An In-depth Inquiry into Updatable Learned Indexes. In 39th IEEE International Conference on Data Engineering (ICDE). https://doi.org/10.1109/ICDE55515.2023.00031 [13] Sanjay Ghemawhat, Jeff Dean, Chris Mumford, David Grogan, and Victor Costan. 2011. LevelDB. https://github.com/google/leveldb [14] Alireza Heidari, Amirhossein Ahmadi, and Wei Zhang. 2025. DobLIX: A DualObjective Learned Index for Log-Structured Merge Trees. Proc. VLDB Endow. 18, 11 (2025). https://doi.org/10.14778/3749646.3749667 [15] Alireza Heidari, Amirhossein Ahmadi, and Wei Zhang. 2025. DobLIX: A DualObjective Learned Index for Log-Structured Merge Trees. https://github.com/ ah89/DobLIX [16] Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. 2019. SOSD: A Benchmark for Learned Indexes. NeurIPS Workshop on Machine Learning for Systems (2019). https: //doi.org/10.48550/arXiv.1911.13014 [17] Tim Kraska, Mohammad Alizadeh, Alex Beutel, Ed H Chi, Jialin Ding, Ani Kristo, Guillaume Leclerc, Samuel Madden, Hongzi Mao, and Vikram Nathan. 2021. Sagedb: A learned database system. (2021). [18] Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The Case for Learned Index Structures. In Proceedings of the International Conference on Management of Data (SIGMOD). https://doi.org/10.1145/3183713. 3196909 [19] Avinash Lakshman and Prashant Malik. 2010. Cassandra: a decentralized structured storage system. ACM SIGOPS Oper. Syst. Rev. 44, 2 (2010). https: //doi.org/10.1145/1773912.1773922 [20] Hai Lan, Zhifeng Bao, J. Shane Culpepper, and Renata Borovica-Gajic. 2023. Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices. Proc. ACM Manag. Data 1, 2 (2023). https://doi.org/10.1145/ 3589284 [21] Hai Lan, Zhifeng Bao, J. Shane Culpepper, Renata Borovica-Gajic, and Yu Dong. 2024. A Fully On-Disk Updatable Learned Index. In 40th IEEE International Conference on Data Engineering (ICDE). https://doi.org/10.1109/ICDE60146. 2024.00369 [22] Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. The adaptive radix tree: ARTful indexing for main-memory databases. In 29th IEEE International Conference on Data Engineering (ICDE). https://doi.org/10.1109/ICDE.2013. 6544812 [23] Baotong Lu, Jialin Ding, Eric Lo, Umar Farooq Minhas, and Tianzheng Wang. 2021. APEX: A High-Performance Learned Index on Persistent Memory. Proc. VLDB Endow. 15, 3 (2021). https://www.vldb.org/pvldb/vol15/p597-lu.pdf [24] Kai Lu. 2022. TridentKV: A Read-Optimized LSM-Tree Based KV Store via Adaptive Indexing and Space-Efficient Partitioning. https://github.com/emperorlu/ Learned-RocksDB [25] Kai Lu, Nannan Zhao, Jiguang Wan, Changhong Fei, Wei Zhao, and Tongliang Deng. 2022. TridentKV: A Read-Optimized LSM-Tree Based KV Store via Adaptive Indexing and Space-Efficient Partitioning. IEEE Trans. Parallel Distributed Syst. 33, 8 (2022). https://doi.org/10.1109/TPDS.2021.3118599 [26] Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Hariharan Gopalakrishnan, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2017. WiscKey: Separating Keys from Values in SSD-Conscious Storage. ACM Trans. Storage 13, 1 (2017). https://doi.org/10.1145/3033273 [27] Lailong Luo, Deke Guo, Richard T. B. Ma, Ori Rottenstreich, and Xueshan Luo. 2019. Optimizing Bloom Filter: Challenges, Solutions, and Comparisons. IEEE Commun. Surv. Tutorials 21, 2 (2019). https://doi.org/10.1109/COMST.2018. 2889329 [28] Yuxuan Mo and Yu Hua. 2025. LOFT: A Lock-free and Adaptive Learned Index with High Scalability for Dynamic Workloads. In Proceedings of the 20th European Conference on Computer Systems, EuroSys. https://doi.org/10.1145/ 3689031.3717458 [29] Patrick E. O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth J. O’Neil. 1996. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica 33, 4 (1996). https: //doi.org/10.1007/s002360050048 [30] William W. Pugh. 1990. Skip Lists: A Probabilistic Alternative to Balanced Trees. Commun. ACM 33, 6 (1990). https://doi.org/10.1145/78973.78977 [31] Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham. 2017. PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP). https://doi.org/10.1145/3132747.3132765 [32] Subhadeep Sarkar, Dimitris Staratzis, Zichen Zhu, and Manos Athanassoulis. 2021. Constructing and Analyzing the LSM Compaction Design Space. Proc. VLDB Endow. 14, 11 (2021), 2216–2229. https://doi.org/10.14778/3476249.3476274 [33] Benjamin Spector, Andreas Kipf, Kapil Vaidya, Chi Wang, Umar Farooq Minhas, and Tim Kraska. 2021. Bounding the Last Mile: Efficient Learned String Indexing. CoRR abs/2111.14905 (2021). arXiv:2111.14905 https://arxiv.org/abs/2111.14905 [34] Speedb, Inc. 2022. Speedb: RocksDB-compatible high-performance storage engine. https://github.com/speedb-io/speedb

[35] Zhaoyan Sun, Xuanhe Zhou, and Guoliang Li. 2023. Learned index: A comprehensive experimental evaluation. Proc. VLDB Endow. 16, 8 (2023). [36] Rebecca Taft, Irfan Sharif, Andrei Matei, Nathan VanBenschoten, Jordan Lewis, Tobias Grieger, Kai Niemi, Andy Woods, Anne Birzin, Raphael Poss, Paul Bardea, Amruta Ranade, Ben Darnell, Bram Gruneir, Justin Jaffray, Lucy Zhang, and Peter Mattis. 2020. CockroachDB: The Resilient Geo-Distributed SQL Database. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, David Maier, Rachel Pottinger, AnHai Doan, Wang-Chiew Tan, Abdussalam Alawini, and Hung Q. Ngo (Eds.). ACM, 1493–1509. https://doi.org/10.1145/ 3318464.3386134 [37] Chuzhe Tang, Youyun Wang, Zhiyuan Dong, Gansen Hu, Zhaoguo Wang, Minjie Wang, and Haibo Chen. 2020. XIndex: a scalable learned index for multicore data storage. In PPoPP ’20: 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. https://doi.org/10.1145/3332466.3374547 [38] Youyun Wang, Chuzhe Tang, Zhaoguo Wang, and Haibo Chen. 2020. SIndex: a scalable learned index for string keys. In APSys ’20: 11th ACM SIGOPS Asia-Pacific Workshop on Systems, Tsukuba, Japan, August 24-25, 2020, Taesoo Kim and Patrick P. C. Lee (Eds.). ACM, 17–24. https://doi.org/10.1145/3409963. 3410496 [39] Yi Wang, Jianan Yuan, Shangyu Wu, Huan Liu, Jiaxian Chen, Chenlin Ma, and Jianbin Qin. 2024. LeaderKV: Improving Read Performance of KV Stores via Learned Index and Decoupled KV Table. In 40th IEEE International Conference on Data Engineering (ICDE). https://doi.org/10.1109/ICDE60146.2024.00010 [40] Chaichon Wongkham, Baotong Lu, Chris Liu, Zhicong Zhong, Eric Lo, and Tianzheng Wang. 2022. Are Updatable Learned Indexes Ready? Proc. VLDB Endow. 15, 11 (2022). https://doi.org/10.14778/3551793.3551848 [41] Jiacheng Wu, Yong Zhang, Shimin Chen, Yu Chen, Jin Wang, and Chunxiao Xing. 2021. Updatable Learned Index with Precise Positions. Proc. VLDB Endow. 14, 8 (2021). https://doi.org/10.14778/3457390.3457393 [42] Qing Xie, Chaoyi Pang, Xiaofang Zhou, Xiangliang Zhang, and Ke Deng. 2014. Maximum error-bounded Piecewise Linear Representation for online stream approximation. VLDB J. 23, 6 (2014). https://doi.org/10.1007/s00778-014-0355-0 [43] Yifan Yang and Shimin Chen. 2024. LITS: An Optimized Learned Index for Strings. Proc. VLDB Endow. 17, 11 (2024), 3415–3427. https://doi.org/10.14778/ 3681954.3682010 [44] Jiaoyi Zhang, Kai Su, and Huanchen Zhang. 2024. Making In-Memory Learned Indexes Efficient on Disk. Proc. ACM Manag. Data 2, 3 (2024). https://doi.org/ 10.1145/3654954 [45] Yong Zhang, Xinran Xiong, and Oana Balmau. 2022. TONE: cutting taillatency in learned indexes. In CHEOPS@EuroSys: Proceedings of the Workshop on Challenges and Opportunities of Efficient and Performant Storage Systems. https://doi.org/10.1145/3503646.3524295 [46] Weihong Zhou and Shiyu Yang. 2024. SLIPP: A Space-Efficient Learned Index for String Keys. In Proceedings of the 6th International Conference on Big-data Service and Intelligent Computation, BDSIC 2024, Hong Kong, Hong Kong, May 29-31, 2024. ACM, 69–77. https://doi.org/10.1145/3686540.3686550