一种大数据流内存B+树构建方法

摘要

面向具有时间维度的大数据流,基于二级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 sce-narios with real-time query requirements,which separates as many parallelizing operations as possible.This paper paral-lelized 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.