Page 355 - 《软件学报》2025年第8期

3778 软件学报 2025 年第 36 卷第 8 期

AFit:
y=0.463x−0.315 buf s =random(s)=0.568
buf ic =random(ic)=−0.834 y=1.405x−1.566 叶数组
模型合并后
y=0.568x−0.834 再缩放
更新缓冲区
y=1.031x−1.149
s∈[0.258, 0.668]
s∈[−0.837, 0.207] 段

Insert 3, 8 1 2 5 7 10 S 1 Full 1 2 3 4 5 6 7 8 9 10 12
− −
4 6 3 − 9 12 8 −
图 5 模型合并过程的示例

算法 1. 插入过程.

输入: 插入键 k;
输出: 插入是否成功.
1. leaf←find_leaf (k); /* 自上而下找键 k 所属叶节点 */
2. foreach lea f B S.point do
3. S i ← (leaf → find_segment(k,k_point)); /* 查找键 k 所属的段 */
4. if S i is full or lea f num_keys ≥BOUND 1 then
B
5. leaf ← merge_expand(leaf); /* 合并数据与模型并扩展节点 */
6. elif leaf num_keys ≥ BOUND 2 then
B
7. leaf ← merge_split_update(leaf); /* 合并数据, 执行分裂并定位新叶子节点 */
8. pos ← (leaf → insert(k)); /* 插入位置 */
9. if pos≥0 then
10. return true;
11. else
12. return false;

(1) 定位插入键所属段 (第 1–3 行). 执行一次插入操作, 首先需要执行点查询确定插入键 k 所属的叶子节点
leaf. 一旦找到一个叶子节点 leaf, 需要在缓冲区中定位键 k 所属的段 S i . 叶子节点 leaf 对应的更新缓冲区存储每个
段的段点, 通过比较插入键 k 与段点 lea f S.point , 从而定位到目标段 S i . 这个过程确保了键 k 被插入到缓冲区的正确
B
位置, 并保持了段间的有序性, 从而确保了将来点查询的高效性. 若插入键 k 所属叶子节点的更新缓冲区数据量
leaf num_keys 既未超过扩展阈值 BOUND 1 , 也未超过分裂阈值 BOUND 2 , 且键 k 所属的段 S i 未满, 则直接插入到所属
B
段的末尾位置 pos, 返回插入成功标志 true.
(2) 合并叶数组与更新缓冲区 (第 4、5 行). 若无法直接插入键 k, 首先检查段 S i 是否已满, 以及更新缓冲区
leaf B 中的数据量 lea f num_keys 是否超过了合并阈值 BOUND 1 . 如果键的数量超过了合并阈值 BOUND 1 , 在叶数组模
B
型的置信区间内随机选择一组斜率和截距来近似拟合更新缓冲区模型. 在这个过程中, 显著性水平 α 为 0.05. 这种
方法可以高效地合并缓冲区中的段, 并确保缓冲区模型的误差保持在可接受的范围内. 完成扩展操作后, 重新执行
插入操作直至插入成功.
(3) 合并叶数组与更新缓冲区并分裂 (第 9–12 行). 若更新缓冲区 leaf B 中的数据量 leaf num_keys 超过了分裂阈
B
值 BOUND 2 . 首先需要将叶数组和更新缓冲区数据合并后排序. 此时根据第 2.1.1 节基于开销模型的方式确定合并
排序后的节点扇出, 并根据扇出确定新内部节点模型参数; 之后根据新模型分配每个叶子节点的数据, 并基于该数