软件学报

作者：李梁,吴刚,王国仁

单位：李梁，东北大学 计算机科学与工程学院, 辽宁 沈阳 11016911,吴刚，东北大学 计算机科学与工程学院, 辽宁 沈阳 110169;计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21009302,王国仁，北京理工大学 计算机学院, 北京 10008103

关键词：内存索引;跳表;机器学习;密度估计

基金：国家自然科学基金（61872072，U1811262，61572119，61622202，61672145，61732003，61572121，61332006，61332014，61328202，61702087）；中央高校基本科研业务费专项资金（N181605012，N171604007，N171904007）；中国博士后科学基金（2018M631358）

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

来源：2020年第3期

《软件学报》期刊编辑部

查看软件学报杂志2020年第3期