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

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

r≤|PLOP(PГmin(L i (PГmax)))|),该层节点为 PLOP(PГmin(L i (PГmax)))中 L i (PГmin(L i (PГmax))).
(5) 叶节点层(PLOB):本层节点为 L i (PГmin(L i (PГmax)))对应元素 PLOB.
可以看出,通过线序划分算法,我们得到了一种具有拟序关系的“树形”结构 TPindex,在该“树形”结构(即
TPindex)中,时态分区层属于上层分区结构,时态分区根节点层到 PLOP(PГmin)层属于 TPindex 的“索引层”,叶节
点层(PLOB)属于 TPindex 的元素层.下面我们给出 TPindex 一般的分区索引结构,如图 2 所示.

Fig.2 Partition index structure of TPindex
图 2 TPindex 的分区索引结构
3 TPindex 索引查询

在本节,我们将讨论时态索引 TPindex 的查询算法,包括基于 PLOB 的内部二分优化查询、基于 PLOB 的多
线程查询以及基于外存的文件模式查询,以适用于支持多核、并行化等优势的现代化硬件,并给出相应的算法.
3.1 基于PLOB的内部二分优化查询

基于上述的 TPindex 索引结构,结合 PLOP 和 PLOB 对于时态数据的有效过滤,我们提出了基于 PLOB 的内
部二分优化查询.在对 TPindex 进行时态数据二分优化查询的时候,我们首先要对查询窗口与 H(PГ)进行时序分
区点进行比较,为后面的数据查询缩小“范围”,减少不必要的时间开销.在本文的时态查询,是指在平面集 H(Г)中
找到包含查询窗口 Q 区间的所有时态数据.假设存在这样的数据{[1,10],[1,9],[2,8],[3,6],[4,6]},给定查询窗口
Q=[2,7],则满足查询要求的序列集合为{[1,0],[1,9],[2,8]}.
定义 7(分区点与查询窗口的关系比较). 不妨设查询窗口为 Q<vts 0 ,vte 0 >,有 n 个待查询分区 H(PГ),即有 n–1
个时序分区点 P k <vts k ,vte k >(1≤k≤n–1),则对于 Q 与 P k 的关系有以下几种情形.
(1) 若 vts 0 >vts k ,则称 P k 在 Q 的右边,符合查询条件的分区是 P 1 ,P 2 ,…,P k+1 ,记 P k >Q.
(2) 若 vts 0 =vts k && vte 0 >vte k ,则称 P k 在 Q 的上边,符合查询条件的分区是 P 1 ,P 2 ,…,P k+1 ,也记作 P k >Q.
(3) 若 vts 0 =vts k && vte 0 <vte k ,则称 P k 在 Q 的下边,符合查询条件的分区是 P 1 ,P 2 ,…,P k ,记 P k <Q.
(4) 若 vts 0 <vts k ,则称 P k 在 Q 的左边,符合查询条件的分区是 P 1 ,P 2 ,…,P k ,也记作 P k <Q.
综上所述,若 P k >Q,则符合查询条件的分区是 P 1 ,P 2 ,…,P k+1 ;若 P k <Q,则符合查询条件的分区是 P 1 ,P 2 ,…,P k .
在对相关的时序分区进行筛选之后,由定义 4,我们得到了 VTs(PLOB)的单增性和 VTe(PLOB)的单减性,不妨
设 PLs i 为当前 PLOB 的 VTs(PLOB)序列,i(max≤i≤min),PLe j 为当前 PLOB 的 VTe(PLOB)序列,j(max≤j≤min),
则针对基于拟序的时态索引,本文给出了以下算法进行时态数据查询操作,如算法 2 所示.
算法 2. 基于 PLOB 的内部二分优化查询算法.
输入:查询窗口 Q.