学习型字符串键索引：优化性能与 O(N) 空间成本

《ACM Transactions on Database Systems》：Learned Indices for String Keys with Optimized Performance and O(N) Space Cost

　　

摘要AI 摘要

要查看此 AI 生成的摘要，您必须拥有高级访问权限。

了解更多登录

摘要

摘要

索引是数据库系统中的重要组成部分。研究表明，对于固定大小的整数或浮点数键，学习型索引能够超越传统的基于树的索引结构。然而，学习型索引在变长字符串键上的应用研究尚不充分。我们的实验表明，现有的字符串学习型索引无法超越传统的字符串索引，如 HOT 和 ART。字符串键长度较长且大小可变，并且通常包含倾斜的前缀，这使得最后一步搜索开销昂贵，并且对学习型索引模型捕捉字符串键倾斜分布的能力产生不利影响。

本文提出了一种新颖的字符串键学习型索引 LITS（Learned Index with Hash-enhanced Prefix Table and Sub-tries，即带有哈希增强前缀表和子树的学习型索引）。我们设计了一种优化的学习型模型，将全局哈希增强前缀表（HPT）与每个节点的局部线性模型相结合，以更好地区分字符串键。此外，我们利用了两种技术——动态比例因子和基于单元格的根节点——来提高空间效率。我们证明了所设计的方案保证具有 O(N) 的空间开销。此外，我们利用紧凑的叶节点和结合 PMSS 模型的混合结构来支持高效的点查询和范围查询。在十一个字符串数据集上的实验结果表明，在点操作上，LITS 相比 HOT 和 ART 分别实现了高达 2.19 倍和 1.85 倍的性能提升，同时具有相当的扫描性能和空间开销。

AI 摘要

AI 生成的摘要（实验性）

本摘要由自动化工具生成，并非由文章作者撰写或审阅。它旨在支持文献发现，帮助读者评估相关性，并帮助来自相邻研究领域的读者理解该工作。它是对作者提供的摘要的补充，作者提供的摘要仍然是该论文的主要摘要。全文仍然是权威版本的记录。点击此处了解更多。

点击此处对本摘要的准确性、清晰度和实用性进行评论。您的反馈将有助于改进和未来的重新生成版本。

要查看此 AI 生成的通俗语言摘要，您必须拥有高级访问权限。