软件学报

作者：陈井爽，陈珂，寿黎但，江大伟，陈刚

单位：陈井爽，浙江大学 计算机科学与技术学院, 浙江 杭州 310027;浙江省大数据智能计算重点实验室(浙江大学), 浙江 杭州 31002711,陈珂，浙江大学 计算机科学与技术学院, 浙江 杭州 310027;浙江省大数据智能计算重点实验室(浙江大学), 浙江 杭州 31002702,寿黎但，浙江大学 计算机科学与技术学院, 浙江 杭州 310027;浙江省大数据智能计算重点实验室(浙江大学), 浙江 杭州 31002703,江大伟，浙江大学 计算机科学与技术学院, 浙江 杭州 310027;浙江省大数据智能计算重点实验室(浙江大学), 浙江 杭州 31002704,陈刚，浙江大学 计算机科学与技术学院, 浙江 杭州 310027;浙江省大数据智能计算重点实验室(浙江大学), 浙江 杭州 31002705

关键词：学习型索引;自适应索引;机器学习;数据库

基金：浙江省重点研发计划（2021C01009）；国家自然科学基金（62050099）；浙江省自然科学基金（LY18F020005）

学习型索引通过学习数据分布可以准确地预测数据存取的位置，在保持高效稳定的查询下，显著降低索引的内存占用.现有的学习型索引主要针对只读查询进行优化，而对插入和更新支持不足.针对上述挑战，设计了一种基于Radix Tree的工作负载自适应学习型索引ALERT.ALERT使用Radix Tree来管理不定长的分段，段内采用具有最大误差界的线性插值模型进行预测.同时，ALERT使用一种高效的插入缓冲来降低数据插入更新的代价.针对点查询和范围查询提出两种自适应重组优化方法，通过对工作负载进行感知，动态地调整插入缓冲的组织结构.经实验验证，ALERT与业界流行的学习型索引相比，构建时间平均降低了81%，内存占用平均降低了75%，在保持了优秀读性能的同时，使插入延迟平均降低了50%；此外，ALERT使用自适应重组优化能有效感知查询工作负载特征，与不使用自适应重组优化相比，查询延迟平均降低了15%.

来源：2022年第12期

《软件学报》期刊编辑部

查看软件学报杂志2022年第12期