LISK: A High-Performance In-Memory Learned Index for Variable-Length String Keys

Learned index has emerged as a new indexing technique that leverages machine learning to accelerate in-memory data processing. However, current learned indexes are primarily designed to index numeric keys and lack robust support for variable-length string keys. In this paper, we propose a novel in-memory learned index called LISK (LearnedIndex forStringKeys) to support string keys. The novelty of LISK is two-fold. First, we propose a trie-like structure to address the limitations of linear models in fitting string keys. Each trie node indexes 8-byte key slices, which are organized as learned sub-indexes or B+-trees. Second, we present a new structure for learned sub-indexes, namely TLS (Two-layerLearnedSubindex), which is tailored to handle the complex distribution of string keys. TLS utilizes three key designs to improve the overall performance: (1) a two-phase hybrid index construction, (2) a second-derivative-based data partitioning, and (3) a cachefriendly overflow node design. We conduct extensive experiments on five datasets and six workloads to compare LISK with seven existing indexes, including five trie-based indexes and the state-of-the-art learned index LITS. The experimental results show that LISK achieves an average 1.99× (up to 7.87×) higher throughput across the six workloads on real-world datasets. Specifically, compared with LITS, LISK achieves an average 1.42× (up to 1.91× ) higher throughput. The source code of LISK is available athttps://github.com/suibianll/LISK/tree/master.