面向数据特征的内存跳表优化技术
作者:
作者单位:

作者简介:

李梁(1992-),男,湖北黄冈人,博士,主要研究领域为内存数据库;王国仁(1966-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为不确定数据管理,数据密集型计算,可视媒体数据管理与分析,非结构化数据管理,分布式查询处理与优化技术(传感器网络和P2P对等计算),生物信息学;吴刚(1978-),男,博士,副教授,CCF专业会员,主要研究领域为内存数据库,知识图谱.

通讯作者:

王国仁,E-mail:wanggr@bit.edu.cn

中图分类号:

基金项目:

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


In-memory Skiplist Optimization Technologies Based on Data Feature
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61872072, U1811262, 61572119, 61622202, 61672145, 61732003, 61572121, 61332006, 61332014, 61328202, 61702087); Fundamental Research Funds for the Central Universities (N181605012, N171604007, N171904007); China Postdoctoral Science General Program Foundation (2018M631358)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    Skiplist is a widely used indexing technology in the database systems. The advantage is that the complexity of skiplist is O(log(n)). However, in the standard skiplist algorithm, the level of each nodes is generated by a random generator, thus, the performance of the skiplist is unstable. In extreme case, the searching complexity deceases to O(n) which is similar to the list searching time. This is because the classic skiplist do not combine data features to generate its structure. It is believed that a stable skiplist structure should fully consider the distribution characteristics of the data to determine the number of node levels. This study estimates the data cumulative distribution function based on the kernel density estimation method, and predicts the position of the data in the skiplist, determines the number of node levels. In addition, it is found that the node with a higher level has a higher probability of being accessed. This study also focuses on the access frequency and the hot data of frequent access, make sure that the upper level of the skiplist is hot data, and access the less cold data in the lower level of skiplist. Finally, a comprehensive experimental evaluation of the six kinds of skiplist algorithms is performed based on the synthesis dataset and real dataset, besides, the source code is open. The results show that the best skiplist algorithm can achieve a 60% performance improvement, which points out a authentic direction for the future researchers and system developers.

    参考文献
    相似文献
    引证文献
引用本文

李梁,吴刚,王国仁.面向数据特征的内存跳表优化技术.软件学报,2020,31(3):663-679

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2019-07-19
  • 最后修改日期:2019-11-25
  • 录用日期:
  • 在线发布日期: 2020-01-10
  • 出版日期: 2020-03-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号