How Does Updatable Learned Index Perform on Non-Volatile Main Memory?
Leying Chen, Shimin Chen · 2021
Recent work on learned index opens a new research direction for index structures. By exploiting the data distribution, a read-only learned index can achieve much better time and space performance than B+-Trees. A number of recent studies propose enhanced learned index structures that provide various levels of support for insertions and deletions. Among them, ALEX, an updatable adaptive learned index, provides the most comprehensive support, allowing on-the-fly insertions and dynamically adjusting the index structure similar to the B+-Tree. In this paper, we study learned index from a new perspective, trying to understand how ALEX performs on Non-Volatile Main Memory (NVM). We analyze the insertion behaviors of ALEX and experimentally evaluate its performance on a real machine equipped with Intel Optane DC Persistent Memory. We find that learning data distributions in learned index makes it feasible to create very large leaf nodes, and reduce the tree height drastically for better search performance. However, this design choice causes a large number of NVM writes for insertion operations, even for the well optimized ALEX design.