面向大数据流的分布式索引构建
作者:
作者单位:

作者简介:

杨良怀(1967-),男,博士,教授,CCF专业会员,主要研究领域为数据库系统,大数据处理.
朱镇洋(1994-),男,硕士,主要研究领域为自然语言处理.
卢晨曦(1994-),男,硕士,主要研究领域为数据流存储.
潘建(1976-),男,博士,副教授,CCF专业会员,主要研究领域为智能信息处理,物联网技术.
范玉雷(1984-),男,博士,讲师,CCF专业会员,主要研究领域为数据库系统,数据流,数据挖掘.

通讯作者:

范玉雷,E-mail:fyl815@zjut.edu.cn

中图分类号:

TP311

基金项目:

国家重点研发计划(2020YFB1707700)


Distributed Index Construction for Big Data Streams
Author:
Affiliation:

Fund Project:

National Key Research and Development Program of China (2020YFB1707700)

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

    大数据流的高效存储与索引是当今数据领域的一大难点.面向带有时间属性的数据流,根据其时间属性,将数据流划分为连续的时间窗口,提出了基于双层B+树的分布式索引结构WB-Index.下层B+树索引基于窗口内流数据构建,索引构建过程结合基于排序的批量构建技术,进一步对时间窗口分片,将数据流接收、分片数据排序以及B+树构建并行化,提高了构建性能.上层B+树索引基于各时间窗口构建,结合时间窗口时间戳的递增性和无限性,提出了避免节点分裂的构建方法,减少了B+树分裂移动开销,提高了空间利用率和更新效率.WB-Index架构中,将流数据和索引分离,同时利用内存缓存尽可能多的双层B+索引和热点数据来提高查询性能.理论和实验结果表明,该分布式索引架构能够支持高效的实时数据流写入以及流数据查询,能够很好地应用于具有时间属性的数据流场景.

    Abstract:

    Efficient storage and indexing of big data streams are challenging issues in the database field. By segmenting the temporal data stream into continuous time windows, a distributed master-slave index structure is proposed based on double-layer B+ tree called WB-Index. Lower B+ tree index is built on stream tuples in each time window. Upper B+ tree index is built on each successive time window. Lower B+ tree index is constructed by combining both batch loading and parallel sorting techniques. The core idea of the construction method is to slice the time window and isolate the parallelable operations from others in the time window. Sorting and data stream receiving between slices work in parallel, while the B+ tree skeleton (a B+ tree without value) construction for the time window and the merge-sorting operation are parallelized as well. These techniques effectively expedite the B+ tree construction. Due to the monotonous increasement of timestamps of time windows, a split-less method for upper B+ tree index construction is adopted to avoid the node splitting and memory movement overhead, and improve the space utilization and update efficiency. In WB-Index, data stream tuples and index are separated, and index and hotspot data are cached as much as possible to improve query efficiency. Finally, theoretic analysis and experiments have both demonstrated that WB-Index can support efficient real-time data stream writing and stream data querying.

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

杨良怀,卢晨曦,范玉雷,朱镇洋,潘建.面向大数据流的分布式索引构建.软件学报,2021,32(11):3576-3595

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

京公网安备 11040202500063号