基于路径预取的树型索引查询优化

来源：计算机应用研究杂志2024年第10期北京时间：

作者：来逸瑞,李永坤,许胤龙,

单位：中国科学技术大学计算机科学与技术学院,合肥230027；

摘要：在树型内存索引的研究过程中，由于传统的片上预取不能适应索引的局部性，导致访存成为该类型内存索引的性能瓶颈。提出了一种基于软件层面的路径预取算法，使用预取加速内存索引的访问，并使得该算法可以快速部署到现实机器上。该算法基于对树型索引访存流程的分析，通过预取表保存键与索引访问路径的关系，通过基于键切片哈希的匹配算法对预取表中的数据进行匹配，显著提高了索引性能。在当前较为先进的树型内存索引上实现了该算法并进行了实验评估，结果表明该算法在不同数据量和读写混合负载下提升了索引器的访问性能。因此，基于路径预取的算法可以有效加速树型内存索引的访存速度，提升索引器性能。

关键词：内存索引,预取,缓存,内存层次结构,