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

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

和 86.39%. 这是由于 DRAMA 极少在线调整索引结构, 且叶子数组使用间隙方式存储数据, 在多数情况下无须指
数搜索即可完成对叶数组的查找. 相反, ALEX 对数据插入频率敏感, 随着插入数据的增多可能导致大量数据移
动, 因此导致二次搜索时间更长. PGM 没有采用间隙插入与缓冲区分段策略, 因此其查找时间明显高于其他索引.
类似地, B+Tree 和 LIPP 也对数据插入频率敏感, 因为更高的插入频率通常会导致更高的树高, 导致它们在不同场
景下的查询时间显著增加. 例如, 在 0.2 插入频率下, 它们的查询时间都显著增加. 此外, 这些算法需要频繁调整结
构以适应数据分布的变化.

DRAMA B+Tree PGM LIPP ALEX
400 750 300 600
600
查询时延 (ns) 400 查询时延 (ns) 300 查询时延 (ns) 500 查询时延 (ns) 200 查询时延 (ns) 400
200
200
100 250 100 200
0
0 0.2 0.4 0.6 0.8 0 0.2 0.4 0.6 0.8 0 0.2 0.4 0.6 0.8 0 0.2 0.4 0.6 0.8 0 0.2 0.4 0.6 0.8
插入比例 插入比例 插入比例 插入比例 插入比例
(a) Osmc (b) Lat (c) Uniform (d) Amzn (e) Wiki
200 200
查询时延 (ns) 150 查询时延 (ns) 200 查询时延 (ns) 150 查询时延 (ns) 200 查询时延 (ns) 200
100
100
100
50 100 50 100
0 10 20 30 40 0 10 20 30 40 0 10 20 30 40 0 10 20 30 40 0 10 20 30 40
倾斜系数 α 倾斜系数 α 倾斜系数 α 倾斜系数 α 倾斜系数 α
(f) Osmc (g) Lat (h) Uniform (i) Amzn (j) Wiki
图 9 查询负载与查询分布对查询时延的影响

图 9(f)–(j) 展示了在相同工作负载下, 查询分布对查询时延的影响. 结果表明, 随着查询分布的倾斜系数增大,
DRAMA 的查询时延显著降低. 这是由于在实际查询过程中, 常使用缓存机制来提高查询效率. 当一个键被查询到
时, 它有可能被缓存在内存中, 以便下次快速提取. 对于倾斜系数高的查询分布, 高频项缓存命中率更高; 在倾斜系
数低的分布下 (倾斜系数等于 0), 每个键的缓存命中概率都相等, 无法利用缓存来提高查询效率.

4.3.6 插入时延比较
通过图 10(a)–(e) 可知, 在不同的数据集与工作负载下, DRAMA 的平均插入时延始终低于其他所有的索引.
例如, 在 Wiki 数据集下, DRAMA 的插入性能分别比 ALEX、LIPP、PGM 和 B+Tree 提高了 3.20、4.37、3.88 和
8.27 倍. 这个结果主要归功于 DRAMA 采用了缓冲区更新的方式, 只需要 O(H+N seg ) 的时间复杂度即可完成插入
操作. 相比于同样采用缓冲区更新的 PGM, DRAMA 采用基于 LSM-Tree 延迟更新的方式来延迟学习数据的更新
分布, 利用近似拟合的方式快速拟合出缓冲区模型, 并使用快速模型合并的方式加速重训练. 模型合并后, DRAMA
利用学习到的数据更新分布分配更新缓冲区容量. PGM 只是通过重新执行分段处理原数组与缓冲区的合并, 并没
有利用数据的更新分布来提高后续插入操作的性能, 也没有基于一定策略加速模型重训练. LIPP 则只能通过向下
分裂处理冲突, 而树的高度显著影响了索引性能. ALEX 移位处理插入的方式也会随着插入数据量的增长导致模
型精度下降或失效, 同样面临着重训练的问题.

DRAMA B+Tree PGM LIPP ALEX
400 300 400 400 400
插入时延 (ns) 300 插入时延 (ns) 200 插入时延 (ns) 300 插入时延 (ns) 200 插入时延 (ns) 300
200
200
200
100 100 100 100
0
0.2 0.4 0.6 0.8 1.0 0.2 0.4 0.6 0.8 1.0 0.2 0.4 0.6 0.8 1.0 0.2 0.4 0.6 0.8 1.0 0.2 0.4 0.6 0.8 1.0
插入比例 插入比例 插入比例 插入比例 插入比例
(a) Osmc (b) Lat (c) Uniform (d) Amzn (e) Wiki
图 10 不同算法插入时延比较

5 结 论
本文针对由于频繁数据更新导致的模型重训练问题, 提出了一种随机插入环境下的带有无损参数压缩的感知