面向数据特征的内存跳表优化技术

作者：李梁; 吴刚; 王国仁^*

来源：软件学报, 2020, 31(03): 663-679.

DOI：10.13328/j.cnki.jos.005902

• 内存索引
• 跳表
• 机器学习
• 密度估计

跳表作为数据库中被广泛采用的索引技术,优点在于可以达到类似折半查找的复杂度O(log(n)).但是标准跳表算法中,结点的层数是通过随机算法生成的,这就导致跳表的性能是不稳定的.在极端情况下,查找复杂度会退化到O(n).这是因为经典跳表结构没有结合数据的特征.一个稳定的跳表结构应该充分考虑数据的分布特征去决定结点层数.基于核密度估计的方式估计数据累积分布函数,预测数据在跳表中的位置,进而设计用于判定结点层数的跳表算法.另外,跳表的查找过程中,结点层数越大的结点被访问的概率越高.针对历史数据的访问频次,设计一种保证频繁访问的"热"数据尽可能地在跳表的上层,而访问较少的"冷"数据在跳表的下层的跳表算法.最后,基于合成数据和真实数据对标准跳表和5种改进的跳表算法进行了全面的实验评估并开源代码.实验结果表明,优化的跳表最高可以获取60%的性能提升.这为未来的科研工作者和系统开发人员指出了一个很好的方向.

• 单位
  北京理工大学; 计算机软件新技术国家重点实验室; 东北大学; 南京大学