...
(2)记开始时间为ts,截止时间为te ,则其窗口时间为[ts, te)。根据开始时间和终止时间计算窗口的叶子号(leaf number)和节点号(node 。
根据开始时间和终止时间计算窗口的叶子号LN(leaf number)和节点号NN(node number)
(3)计算可能的兄弟节点节点号,若兄弟节点存在于内存中,则执行合并操作,逐层向上生成父亲节点。
...
如图所示,假设LN=1,2,7的窗口没有数据,NN=6,10,12,18的节点在内存中。服务器向索引管理器发送一个新的窗口摘要,该分区的开始时间为t7s,截止时间为t7e。6,10,12,18的节点在内存中。
服务器向索引管理器发送一个新的窗口摘要,该分区的开始时间为t7s,截止时间为t7e。
按照LN和NN的计算方法,计算出顺序数据窗口的叶子号LN=7,节点号NN=11。
...
最终存在于内存中的节点为NN=6,14,18的三个节点。
三、乱序数据处理
四、基于PISA的查询流程
1. 查询请求的处理步骤
(1)首先根据查询请求中的时间段计算出需要查询的节点和原始数据段,将查询划分为三部分;
(2)找出所对应的需要计算的节点(包括内存中的根节点和磁盘中的一些节点),加入候选节点集合Cs;
(3)根据根节点判断当前生效的PISA段可以得出乱序时间段,计算相关聚合值;
(4)将Cs中的聚合值和乱序时间段的聚合值合并。
2. 示例
如图所示,内存中有NN=6,10,12,18的节点,标记为乱序状态的节点为NN=11,13,14的节点。
当进行查询(t3e < qs < t4s, t9e < qe < t10s)时,首先确定需要查询的原始数据段;
对于t4s~t9e,按以下步骤A~F找出所对应的需要计算的节点:
A:t9e对应节点NN=16,其前继节点NN=12,将NN=12加入;
B:NN=12前继节点NN=11,但不存在于磁盘中,该段为乱序数据段;
C:NN=11前继节点NN=9;
D:NN=9找出NN=10,将NN=10加入Cs;
E:NN=10的节点可以覆盖到NN=8,NN=9;
F:NN=8前继节点NN=5,将NN=5加入Cs。
最终Cs={5, 10, 12, 16},计算中各个节点的其聚合值;计算[t7s, t7e)乱序数据段为的聚合值;将Cs中的聚合值和乱序时间段的聚合值合并。