Page 259 - 《软件学报》2021年第11期

杨良怀 等:面向大数据流的分布式索引构建 3585

curNode←curNode.parent;
assignKey(key,curNode);
}
2.3. 若更新后的 P index =B,则表示节点已满,异步调用 expandSpace(P),开辟新的节点空间;
2.4. 完成更新.
异步任务:expandSpace(P) //P:当前已满节点
1. 以 P 为起点,递归向上搜索首个未满父节点,暂存其引用值 P expand ,过程如下:
findNotFullParent(P){
若 P 为根节点且已满,则
创建新节点作为新根节点;
P 的键值传播到新根节点,并把 P 作为其首个子节点;
返回 root 节点;
若 P 未满,则 P insert ←P 并返回 P;
若 P 已满,则递归查找,返回 findNotFullParent(P.parent)的结果
}
2. 以 P expand 为起点,向下递归创建子节点.从而保持索引相对平衡,过程如下:
createChildNode(P insert ){
若 P insert 已为叶节点,则结束;
否则执行:
创建容量为 B 的新节点 tmp;
设置新节点树高:当前树高−1;
把 tmp 添加到 P insert 的子节点中;
递归调用 createChildNode(tmp),向下创建节点
}
上层索引更新过程中,若插入点为非空节点,索引更新时间复杂度为 O(1);若插入点是空节点,需额外初始
化所有父节点 key 值,时间复杂度为 O(n height ).B+树树高很低,O(n height )可近似为 O(1).因此可得:本文所提更新方
法在数据流场景下能保持稳定高效的更新效率,远优于传统的 B+树更新方法.
随着系统的运行,上层索引不断增大.对于历史数据,查询次数少,可对其归档存储.本文采用分段存储的策
略,每过一个时间周期,就生成一个全新的上层索引,用于后续的更新写入,如图 8 所示;并将上层索引和周期信
息的对应关系存储在协调节点上,查询时,可利用对应关系选取相应的上层索引.此外,对于老旧的索引分段,可
将其存储在磁盘中,减少内存存储开销.

Fig.8 Upper B+ tree index segmentation
图 8 上层 B+树索引分段

4 索引构建性能评估

本节对 WB-Index 索引构建性能做量化评估,表 2 为涉及的相关参数,其中,涉及时间相关的参数单位为 s.