LIFM: A Persistent Learned Index for Flash Memory
Shuhao Song, Peiquan Jin, Zhaole Chu, Yongping Luo, Shouhong Wan · 2023
Learned Indexes aim to use machine-learning models to predict the target addresses of requested data, which have been demonstrated efficient for in-memory data accesses. However, modern database systems mainly use flash-memory-based solid-state drives (SSDs) as storage devices, and current learned indexes fail to work on SSD-based databases. In this paper, we propose LIFM (Learned Index for Flash Memory), a new persistent and updatable learned index for flash-memory-based SSDs. Unlike existing learned indexes that aim to reduce memory access, LIFM is designed to reduce I/O costs. The novelty of LIFM lies in three aspects. First, LIFM proposes a hierarchical tree structure that combines the advantages of traditional B+-tree and in-memory learned indexes. Second, LIFM employs a model-based data placement scheme to reduce the page reads or writes. Third, LIFM uses a flash-memory-friendly storage layout to reduce additional access to flash memory. We conduct experiments on a real SSD and compare LIFM with B+-tree and two recently proposed learned indexes, ALEX and FITing-tree. The results suggest the efficiency of LIFM.