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

• 作者: 吴刚 李梁 王国仁
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 内存索引 跳表 机器学习 密度估计
• 年，卷（期）: 2020,（3）
• 页码范围: 663-679
• 页数: 17页
• 分类号: TP18
• 字数: 10423字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005902

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王国仁	北京理工大学计算机学院	18	29	3.0	5.0
2	李梁	东北大学计算机科学与工程学院	2	2	1.0	1.0