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

3584 Journal of Software 软件学报 Vol.32, No.11, November 2021

条记录,并更新到上层索引中,从而完成 W i 窗口的索引构建.B+树是平衡树,更新过程会动态调整节点以保持平
衡性.上层索引中,其 key 值是窗口时间,具有线性递增的特点.若采用传统的更新方法,更新过程会导致大量的节
点分裂,且分裂后的节点由于 key 值递增的特点,后续不会再有数据写入.本文结合当前场景,针对传统更新方法
存在的存储资源浪费、性能不稳定等问题,提出一种避免节点分裂的更新方法,在保持 B+树相对平衡的前提下,
提高更新性能.
上层索引更新过程中,在 B+树中维护全局插入点,如图 7 所示.每次更新只需将新数据顺序的写入叶节点,
且更新过程不触发节点分裂,每个节点空间都能被完全利用.若全局插入点对应的叶节点空间饱和,则向上递归
查找未满父节点,再在父节点下递归创建子节点用于后续的数据写入.若所有父节点已满,则需要增加树高,创
建新的根节点作为父节点.上层索引每隔一个时间窗口更新一次,当叶节点空间饱和后,可预先创建叶节点,用
于后续更新写入.
根节点

非叶节点 非叶节点
Key ... Key ... Key ...

叶节点 叶节点 叶节点 P:全局插入节点
Key ... Key ... Key ... Key Key ...

P inner:节点内部插入点
Fig.7 Upper B+ tree updates
图 7 上层 B+树更新

上层索引详细更新过程如算法 1 所述.
算法 1. 上层索引更新.
输入:key:待更新窗口起始时间;value:待更新窗口对应的下层索引引用.
输出:root:B+树根节点.
符号说明:B 表示 B+树阶数;P 表示上层索引插入节点;P index 表示节点内部插入偏移值;n height 表示上层 B+
树树高.
1. 若上层索引为空,则初始化索引:
1.1. 申请并初始化空间为 B 的节点 N init .并将其作为根节点:root←N init .
1.2. 初始化全局插入点和节点内部插入偏移值:P←node,P index ←0.
1.3. 更新树高:n height ←1;
2. 若上层索引不为空,则更新上层索引:
2.1. 根据全局插入点 P,直接插入到相应叶节点,更新叶节点对应的 P index ;
2.2. 若更新后 P index =1,表示对应的叶子节点是新节点,则需递归的对其父节点赋键值,过程如下:
assignKey(key,curNode){
若当前节点 curNode 为根节点 Root 或 curNode 已满则返回;
否则
将键值 key 添加到 curNode;