DIndex: an Efficient on-Disk Learned Index for Memory-Constrained Environments

B+trees, the de facto standard for on-disk database indexing, exhibit significant performance degradation in memoryconstrained environments due to frequent disk I/O that accesses out-of-cache index nodes during tree traversal. The recent proposal of in-memory learned indexes promises substantial reductions in index footprint by replacing traditional hierarchical structures with compact learned models. However, they require sorted data layouts for accurate lookups, which are costly to maintain on disks, especially in the presence of writes. So far, attempts to adapt learned indexes for on-disk use have yet to fully realize the performance benefits of learned models: they either incur massive disruptive data movement to maintain data layout or introduce significant metadata overhead that negates the space advantage of learned models. We present DIndex, a new on-disk learned index tailored for memory-constrained environments. DIndex efficiently supports write operations while maintaining high read performance and low index size. Key to DIndex's design is the decoupling of logical ordering from physical data layout and a set of techniques that realize this decoupling with small metadata overhead. Specifically, DIndex proposes to maintain model-compressed pivot keys to guide error correction and a mapping table that associates data blocks' physical locations using an adaptive, variable-span mapping scheme. Experiments show that DIndex outperforms B+tree and other learned indexes by up to 28× in throughput and reduces index size by up to 99%.