Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

2. 设计阶段

(1)本阶段设计:默认分区关闭,即仅有1个分区,每一个序列有一个PISA索引 每一个序列有一个PISA索引—— 每个序列有一个索引管理器。

(2)下阶段设计:开启分区后,索引建立在分区内部,不跨分区;每一个序列,每一个分区有一个PISA索引 每一个序列,每一个分区有一个PISA索引—— 每个分区、每个序列各有一个索引管理器。

3. 设计目标

...

(1)memtable flush落盘时,触发索引的构建。每写好一个叶子节点(达到配置或计算的窗口时间长度),就将该节点交给索引管理器。

未写入该叶子结点的“尾巴数据”缓存到内存里,下一个memtable来的时候合并。未写入该叶子节点的“尾巴数据”缓存到内存里,下一个memtable来的时候合并。

(2)用户配置:用户可以配置窗口时间长度t = te - ts

...

(3)将所有的PISA索引存储到一个存储组中,便于针对索引的删除和更新的操作。

3. 构建步骤

(1)memtable flush落盘时,索引管理器根据此memtable、内存中保留的之前的memtable和用户配置,flush落盘时,索引管理器根据此memtable、内存中保留的之前的memtable的“尾巴数据”和用户配置,

计算此memtable属于的叶子结点的开始时间计算待写入的叶子节点的开始时间ts、截止时间、结束时间te,并计算数据摘要信息Sseq(2)写好一个,并计算窗口时间为[ts, te)叶子节点后,的叶子节点的数据摘要信息Sseq

(2)写好一个叶子节点后,索引管理器根据开始时间和终止时间计算窗口的叶子号LN(leaf number)和节点号NN(node number);number)

(3)计算可能的兄弟节点节点号,若兄弟节点存在于内存中,则执行合并操作,逐层向上生成父亲节点。(3)计算可能的兄弟节点的节点号NN,若兄弟节点存在于内存中,则执行合并操作,逐层向上生成父亲节点。

4. 示例

如图所示,假设LN=1,2,7的窗口没有数据,NN=6,10,12,18的节点在内存中。

服务器向索引管理器发送一个新的窗口摘要,该分区的开始时间为t7s,截止时间为t7e。服务器根据刷入的memtable写好的叶子结点开始时间为t7s,截止时间为t7e。

按照LN和NN的计算方法,计算出顺序数据窗口的叶子号LN=7,节点号NN=11。

...