杨良怀,项俊腱,徐卫,范玉雷.一种大数据流内存B+树构建方法[J].计算机科学,2018,45(3):171-177, 212
一种大数据流内存B+树构建方法
In-memory B+tree Construction Methodology for Big Data Stream
投稿时间:2017-01-20  修订日期:2017-04-15
DOI:10.11896/j.issn.1002-137X.2018.03.027
中文关键词:  B+树,数据流,内存索引,大数据
英文关键词:B+tree,Data stream,In-memory index,Big data
基金项目:本文受浙江省基金项目(LY14F020017,LQ15F020007),国家基金项目(61070042)资助
作者单位E-mail
杨良怀 浙江工业大学计算机科学与技术学院 杭州310023 yanglh@zjut.edu.cn 
项俊腱 浙江工业大学计算机科学与技术学院 杭州310023  
徐卫 浙江工业大学计算机科学与技术学院 杭州310023  
范玉雷 浙江工业大学计算机科学与技术学院 杭州310023  
摘要点击次数: 637
全文下载次数: 408
中文摘要:
      面向具有时间维度的大数据流,基于二级B+树索引结构,提出了一种高效的面向时间窗口、采用批量装载技术的内存B+树构建方法。该方法对时间窗口进行分片,通过分离出可以并行处理的操作来加速构建过程,将排序操作与数据流接收并行,B+树骨架的构建与排序并行;采用基于排序的批量装载技术以及优化 的构建顺序,能够避免多线程之间不必要的加锁、同步开销,有效提高构建效率。提出的多次微批量排序单次批量装载(MBSortSBLoad)B+树构建方法的构建速度快,能承载的最大流速大。实验验证了所提方法的有效性。
英文摘要:
      This paper investigated into the issues of indexing on data stream with time dimension in near real-time.By resorting to 2-tier B+tree index,this paper invented a highly effective in-memory B+tree construction method for scenarios with real-time query requirements,which separates as many parallelizing operations as possible.This paper parallelized the operations of sorting and data receiving by dividing the time-window into equal-duration slice,and parallelized the construction of B+tree skeleton with sorting.This paper avoided unnecessary locking and synchronizing cost by adopting sorting-based bulk loading techniques and optimized constructing sequence.The proposed in-memory B+tree construction algorithm called MBSortSBLoad can build B+tree quickly and accept higher data arriving rates.Extensive experiments demonstrate the effectiveness of the proposed methods.
查看全文  查看/发表评论  下载PDF阅读器