One-Shot Traversal for Low-Latency SSD-based Tree Index
作者: Yiheng Tong, Minhui Xie, Yuanhui Luo, Jing Liu, Ran Shu, Yongqiang Xiong, Yunpeng Chai
2026-03摘要: SSD-based tree indexes (e.g., B+tree) have been widely adoptted in storage and database systems. Driven by modern high-performance SSDs, much prior work has focused on improving their overall throughput. However, when it comes to latency, such approaches still suffer from the inherent bottleneck of pointer chasing during index traversals, so query latency does not benefit directly from faster SSDs. In this paper, we propose Shortcut, a lightweight solution that transforms the conventional wisdom of inherent access dependency into one-shot traversal, thereby achieving low query latency. Our key idea is to exploit intra-query parallelism by training per-level learned indexes as B+tree companion to predict the traversal path in advance, and issuing multiple concurrent I/O requests to prefetch all target nodes in a one-shot manner. The main challenge we deal with is the excessive memory overhead of the additional learned index, which originates not from the machine learning (ML) models, but from two essential structures in it: the key array (for last-mile search) and the value array (termed “mapping array”, for mapping model predictions to arbitrary node locations in the file). Shortcut eliminates two arrays through two techniques: Keyless Learning Method and Phantom Mapping Mechanism, and achieves nearly-zero memory overhead (∼0.6%). Evaluations on YCSB and TPC-C show that Shortcut can reduce end-toend query latency by 26.2% to 64.8%.