Page 205 - 《软件学报》2020年第11期

3520 Journal of Software 软件学报 Vol.31, No.11, November 2020

Key words: temporal index; timing partition; quasi-order relation; high-volume data; parallelize

[1]
时间和空间是客观事物存在和发展的基本形式,所有的信息都具有相应的时态属性 .随着互联网信息技
术的高速发展,全球的信息呈现出爆炸式增长,海量的历史数据被存储供企业进行查询和分析,这些数据与时间
的联系十分密切.因此,如何对时态数据进行高效地存储与管理是时态数据库领域研究的热点.时态数据的存储
[2]
与管理要解决的其中一项关键技术就是时态索引 的构建.
针对时态索引的构建问题,研究人员提出了多种解决方案.自 20 世纪 90 年代以来,传统的时态索引以时态
[3]
[4]
数据模型 为理论基础(该模型主要包括“数据本体”和“时态信息”),一般通过结合 B+-tree(比如 MAP21 )或
[5]
[6]
R-tree(比如 4R-tree 和 GR-tree )等技术对时态数据进行处理 [7,8] .根据不同的时态数据模型,时态索引的处理有
3 种处理方式:将“数据本体”和“时态信息”依次处理 [4,5,9,10] ;将“时态信息”处理归结到非时态部分,对时态数据和
非时态数据统一进行处理 [11−13] ;将“数据本体”与“时态信息”协同处理 [14−16] .
传统的时态索引能够较好地适用于小规模数据的时态需求,然而在面对海量数据时,由于其数据类型复杂,
传统的时态索引结构存在冗余、空间开销过大、更新维护成本过高、难以支持复杂的时态查询以及复杂查询
效率低等问题因此,研究一种适用海量数据的时态索引显得很有必要.
另外一方面,支持并行、多核和大内存等的现代化硬件使用非常普遍,多核处理器已经是市场上的主流配
置.传统基于单线程的时态索引显然不能很好地利用目前计算机体系结构的优势.因此,研究如何将基于多线程
的并行化技术应用到时态索引,提出可并行化的时态索引方案,可以为时态数据的检索带来性能的提升.在这方
面,文献[17]提出了一种基于内存的索引 Timeline,结合可并行化的现代化硬件,其优化的核心主要在于减少 CPU
的计算时间.但是其对机器性能需求过高,缺乏普遍适用性.而结合多线程的并行化技术,基于外存的时态索引仍
然是一种有价值的解决方案,其优化的核心在于增加查询数据的命中率,减少 I/O.
因此,本文提出了一种基于时序分区的时态索引技术 TPindex.该索引通过时序分区和线序划分的方法将海
量的时态数据分为分区层和索引层两个部分.在用户进行时态数据查询的时候,首先通过分区层快速地定位到
目标数据对应的时序分区中,然后再通过相应时序分区中顺序结构的索引层进行目标数据的筛选,实现“一次一
顺序序列”的高效据检索方式.本文的贡献如下:
(1) 提出了一种基于时序分区的时态索引方案,适用于海量数据存储与管理的时态索引 Tpindex.
(2) 在 TPindex 的基础上了,设计了一种基于多线程技术的并行化优化方案.同时设计分文件存储线序索引
的模式将时序分区的线序索引磁盘化,减少内存中的存储压力,将时态索引外存化.
(3) 讨论了基于 PLOB 的时态数据增量式更新机制,实现了对大规模历史数据的有效动态管理.
(4) 通过多组仿真实验,实验结果表明,在海量数据的情况下,本文提出的 TPindex 索引具有一定的有效性和
实用性.
本文第 1 节介绍相关的研究工作.第 2 节给出 TPindex 索引构建的详细步骤.第 3 节描述 TPindex 索引的多
种查询模式.第 4 节讨论 TPindex 索引的动态增量式更新机制.第 5 节通过多个仿真实验进一步验证 TPindex 的
有效性与实用性.第 6 节总结全文,并提出未来的工作展望.

1 相关研究

随着信息技术的高速发展,全球的信息量正在以指数级的速度增加,其增长速度已经超过摩尔定律 [18] .现实
中的信息几乎都显示或隐式地包含时间特征,天然的具备时态属性.海量的历史数据被存储和管理,是企业分析
和决策的重要资料.这些时态数据可以看成是由“数据本体”和“时间标签”两部分组成,所以在某种程度上时态
数据存储和管理也可以看作是常规数据存储和管理的拓展.但是在传统的关系型数据库中,数据的时间属性通
常不是显式的,只保留数据的当前状态,相当于一种“快照数据”.但是当数据发生变化的时候,常规数据库会通过
覆盖原有的数据来实现数据的更新,这样就使得历史数据被“抹除”掉而导致出现历史数据丢失的问题.虽然常
规的数据库也能够存储历史数据,但是这样会导致时态数据的完整性被打破,难以重建对象数据的历史状态、