面向内存数据库的类字典树索引综述与性能比较
Review and Performance Comparison of Trie-like Indexes for Main-Memory Databases作者机构：中国科学技术大学计算机科学与技术学院 中国科学院电磁空间信息重点实验室
出 版 物：《计算机学报》 (Chinese Journal of Computers)
年 卷 期：2024年第47卷第9期
页 面：2009-2034页
核心收录：
学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)]
基 金：国家自然科学基金面上项目“面向异构混合内存的NVM感知索引及自适应学习方法研究”(No.62072419)的资助~~
摘 要：如何快速存取海量数据是大数据时代数据库系统面临的重大挑战.利用大内存构建内存数据库系统是实现大数据实时存取的可行途径.在此背景下,用于加速内存数据存取的内存数据库索引成为近几年国内外的研究热点.但是,内存数据库索引也面临着诸多挑战.以常见的内存B+树索引为例,第一个问题是索引的空间效率较低,这是因为内存B+树索引的节点内部存在较大的空间浪费;第二个问题是索引的查询复杂度较高,B+树的查询复杂度受限于数据规模,随着数据规模的扩张,索引的搜索效率也会下降;第三个问题是变长数据支持弱,B+树对于变长键的支持比较差,往往难以适应实际应用的需要.近年来,由于字典树具有空间代价低、查询效率与数据规模无关、支持变长键等优点,逐步成为了内存数据库索引研究中的一个主要方向.本论文围绕面向内存数据库的类字典树索引,首先介绍了字典树的概念、特点和历史,然后系统梳理和总结了类字典树索引的现状和最新进展,之后提出了一种全新的分类方法对类字典树索引进行了分类.在此基础上,论文对主流的六种类字典树索引进行了实验,在多个数据集和负载上进行了性能对比,并基于实验结果讨论了类字典树索引的设计和使用建议,最后展望了未来类字典树索引的发展方向.
维普期刊数据库
同方期刊数据库