ALT-index+: An Efficient Hybrid Learned Index for Concurrent Memory Systems

The learned index technique has been widely explored as a strong competitor to traditional indexes. However, frequent retraining is required when it comes to insertion scenarios, and the read-write performance of the learned index still falls short of expectations, especially in concurrent conditions. In this paper, we first propose a novel hybrid index scheme that combines a read-efficient learned index with an insert-efficient Adaptive Radix Tree (ART) to realize high read-write performance. However, it is not trivial due to expensive model prediction errors, complicated retraining process, redundant node traversals, and slow bulkload speed. Therefore, we introduce ALT-index, an efficient hybrid learned index structure with a delicate two-tier architecture, a compact pointer buffer, and an efficient segment algorithm to address these issues. Nevertheless, its performance is still limited by blocking retraining process, and the bulkload time cannot exploit multithreading. To address these limitations, we present ALT-index+ with two major extensions. First, we develop a stepped lazy eviction scheme to support a non-blocking retraining process. Second, a parallel recursive construction scheme is designed to accelerate bulkloading in both layers. Experimental results show that ALT-index+ achieves 1.4x–2.5x throughput improvement in read-write-balanced scenarios, with a maximum 80.2% reduction in bulkload time compared to state-of-the-art learned indexes.