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

Zhaole Chu

doi:10.1109/tc.2026.3679553

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

2026-07-01

0

PRE

AI

DOI：10.1109/tc.2026.3679553

原文链接

原文求助

摘要

En 中文

基于学习的索引作为一种新兴的索引技术，利用机器学习加速内存数据处理。然而，当前的基于学习的索引主要设计用于索引数值键，缺乏对变长字符串键的强健支持。本文提出了一种新颖的内存基于学习的索引LISK（字符串键的基于学习的索引）以支持字符串键。LISK的创新性体现在两个方面。首先，我们提出了一种类似Trie的结构来解决线性模型在拟合字符串键方面的局限性。每个Trie节点索引8字节键切片，这些切片被组织为基于学习的子索引或B+树。其次，我们提出了一种新的基于学习的子索引结构，即TLS（两层基于学习的子索引），该结构专门用于处理字符串键的复杂分布。TLS利用三种关键设计来提升整体性能：(1) 两阶段混合索引构建，(2) 基于二阶导数的数据分区，(3) 友好缓存的溢出节点设计。我们在五个数据集和六个工作负载上进行了广泛实验，将LISK与七种现有索引（包括五种基于Trie的索引和最先进的基于学习的索引LITS）进行比较。实验结果表明，LISK在真实世界数据集的六个工作负载上平均实现了1.99倍（最高7.87倍）更高的吞吐量。具体而言，与LITS相比，LISK平均实现了1.42倍（最高1.91倍）更高的吞吐量。LISK的源代码可在https://github.com/suibianll/LISK/tree/master获取。

Keyword:

Central Processing Unit

Electronic circuits

Field programmable gate arrays

Electronic mail

Radio access networks

Regional area networks

Communication systems

Computer networks

Wide area networks

Learning (artificial intelligence)

Index

learned index

string keys

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

摘要

期刊

机构

引用论文