摘要:大数据流的高效存储与索引是当今数据领域的一大难点.面向带有时间属性的数据流，根据其时间属性，将数据流划分为连续的时间窗口，提出了基于双层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.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/6097