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

杨佐希 等:基于时序分区的时态索引与查询 3535

Fig.9 Comparison of time overhead of Fig.10 Space overhead and number of PLOBs of
index building index building
图 9 索引构建的时间开销对比 图 10 构建索引的空间开销和 PLOB 数量

5.2 TPindex时态查询
综上所述,TPindex 支持时态查询操作包括快照查询(snapshot query)、跨度查询(interval query)、时态投影
(projection query)和时态选择(selection query)等,现对 4 种查询分别进行实验评测:实验数据从 20w 到 240w 逐渐
递增,随机数据量从 20w 到 400w 逐渐递增,依次随机生成 100 个时间版本的快照;随机生成 100 个时间跨度 T;
随机做 100 次投影操作;随机生成 100 次查询窗口 Q,分别进行 4 次实验,实验结果如图 11 所示.可以看出,随着数
据量的增加,快照查询和时态投影操作的时间开销曲线近似成直线,说明快照查询和时态投影运算的查询性能
都较稳定;但跨度查询和时态选择操作的时间开销出现很大的波动,这与查询区间跨度的不确定性有关.因此,接
下来的实验中将探究不同时间跨度对时态查询的性能影响.

Fig.11 Comparison of the performances for TPindex on different temporal query operations
图 11 TPindex 时态查询的性能比较
不同的 Q 跨度对于时态查询性能的影响不同,本组实验将 TPindex 与 TDindex 索引通过对照进行说明.在
TDindex 索引的时态查询中,主要选取了 TDindex 的遍历查询(TDindex traveral)与内部二分查找(TDindex binary
search)的查询算法.实验数据量为 600w,随机生成跨度分别为 10%T,20%T,30%T,40%T,50%T 和 60%T 的 100 组
查询窗口,计算最终的平均时间开销.实验结果如图 12 所示.结果表明,随着 Q 跨度的增大,TDindex 和 TPindex
的时间开销都在逐渐减少,在 60%T 时达到最佳结果,并最后都趋向于稳定.但是无论在哪一个 Q 跨度下的查
询,TPindex 的性能都优于 TDindex.
TPindex 特有的上层“分区层”可以快速地定位到目标数据所在的时序分区,再由二分优化查找算法在分区
内部的顺序结构进行数据的筛选.通过“数据定位”与“过滤”,相对于 TDindex 一层的数据“过滤”,TPindex 可以实
现更加高效的查询性能.本组实验中选取上述实验中最佳的时间跨度 60%T,数据量由 100w 到 600w 依次递增,