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

郭娜 等: DRAMA: 更新分布感知的学习型索引 3777

  2
1 n ∑  
n ∑ 

l yy =   − y i   (8)
y i
 n 
i=1 i=1

√
l yy − slope·l xy
σ = (9)
n−2

t = t α (n−2) (10)
2
其中, l x 由公式 (2) 计算得出. 得到中间变量后, 根据公式 (3) 计算叶数组对应的模型斜率 slope 与截距 ic. 根据中
y
间变量以及叶数组模型参数, 可得叶数组模型参数的置信区间 (亦为更新缓冲区模型参数的范围) 如下:

[ ]
t ·σ t ·σ
bu f_s ∈ slope− √ , slope+ √ (11)
l xx l xx

 √ √ 
 2 2 
 1 ¯ x 1 ¯ x 
   
ic
buf_ic ∈  −t ·σ· + ,ic+t ·σ· +   (12)
 n n 
 l xx l xx 
由公式 (11)、(12) 可知, 近似拟合模型与真实模型的斜率之间、近似拟合模型与真实模型的截距之间的最大
√ √
t ·σ 1 x 2 t ·σ 1 x

2

差值分别为 √ 与 t ·σ· n + l . 最大预测误差 Errmax = x √ +t ·σ· + . 由于 t 值与 x 值可正可负, 去
l xx xx l xx n l
xx
除绝对值符号即得公式 (7). 证毕.
由于高频插入时会导致模型重训练, 由图 1 可知, 模型重训练过程会严重影响插入操作的性能. 此外, 利
用更新数据的分布可以预测后续插入的分布, 进而提高后续插入的性能. 为了尽可能地减少模型重训练对插
入性能的影响并利用更新数据的分布加速查询与插入性能, 在读写工作负载下, 利用近似拟合方法处理更新.
随着数据插入频率的增加, 更新缓冲区内的数据量随之增加. 当更新缓冲区的大小达到合并阈值时, 必须进行
合并操作. 通过增量学习更新数据的分布, 可以有效减少合并操作的时间, 同时可以加速模型重训练过程并利
用更新数据的分布调整索引结构. 因此, 本文引入了一种近似拟合方法 AFit, 以增量学习更新缓冲区的数据
分布.
根据定理 2 以及公式 (7)–(12), 在批量加载过程中计算了每个叶模型参数的有最大误差保证的置信区间. 因
此, 当插入的数据量达到一定阈值并需要进行合并时, 无须在线学习缓冲区的数据分布. 首先, 在预先计算的参数
置信区间内随机选择一组斜率和截距值作为更新分布模型的参数; 之后, 将原数据分布模型的斜率和截距与更新
分布模型的斜率和截距分别相加作为合并后叶子节点的模型参数; 然后, 统计合并后叶子节点的数据量并根据初
始密度确定该叶子节点的容量; 最后, 在合并后叶子节点的模型参数及其容量确定后, 使用模型驱动的方式将原数
据和更新数据插入到合并后叶子节点并更新该叶子节点更新缓冲区的大小. 这种近似拟合方法还避免了在线学习
缓冲区数据分布时对缓冲区数据进行排序的开销. 虽然近似拟合更新缓冲区模型并将其与叶数组模型合并的方法
可能会在一定程度上增加合并后模型的预测误差, 但随着插入数据增多会执行模型合并和分裂操作, 近似拟合引
起的预测误差将被消除. 例 5 展示了一个近似拟合的详细例子.
例 5: 如图 5 所示, 在前面例子的基础上, 插入键 3, 8. 此时段 S 1 不再有空余位置, 从而触发叶数组与更新缓冲
区合并操作. 由例 1 可知, 叶数组模型未扩展前的斜率和截距分别为 0.463, −0.315, 当显著性水平 α=0.05 时, 根据
公式 (11)、(12) 计算叶数组模型参数的置信区间: [0.258, 0.668] 与 [−0.837, 0.207]. 假设近似拟合的更新分布模型
斜率和截距分别为 buf sp =0.568, buf ic =−0.834. 此时模型合并后叶数组斜率、截距分别为 sp'=1.031, ic'=−1.149. 根
据容量缩放后叶数组的最终模型为 y=1.405x−1.566, 此时, 键全部存储在新的叶数组中. 后续的实验数据也验证了
近似拟合的结果与最小二乘法拟合的结果差距并不显著.

2.2.2 插入过程
若给定待插入键 k, 将其插入到索引的执行过程如算法 1 所示. 插入时可能涉及数据的合并和节点的扩展或
分裂, 算法执行完毕返回是否插入成功.