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

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

DRAMA 的吞吐量会略逊于 ALEX.

4.3.2 预测误差分析
图 7 展示了在 Osmc 数据集上使用近似拟合法的误差和使用最小二乘法拟合的误差的比较. 图 7(a) 展示了批
量加载 20M 数据, 插入 80M 数据后不同预测误差范围内键的数量. 从图中可以观察到, 近似拟合的结果与最小二
乘法基本一致, 键的预测误差多数都在小误差范围 [0, 4]. 这是因为虽然使用了近似拟合的方法, 但将键插入到叶
子节点的过程以为基于模型驱动的方式进行, 保证了较低的预测误差. 图 7(b) 展示了批量加载不同比例下 (0.1 表
示批量加载 10% 的数据, 插入剩余 90% 的数据) 叶子节点模型的最大预测误差. 结果表明, 近似拟合与最小二乘
法拟合的最大节点误差基本一致, 且随着插入数据量的降低, 节点最大误差也下降, 验证了定理 2 的误差保证. 在
其他数据集上所得的结论一致.

70 1 500
59.0 61.0 近似拟合 近似拟合
60 最小二乘法拟合 1 250 最小二乘法拟合
键的数量 (M) 40 29.0 30.0 节点误差 1 000
50
750
30
500
20
10 250
3.9 4.0 4.6 2.0 1.0 1.0 0.5 0.5 0.3 0.5 0.6 0.2 0.4 0.1
0 0
[0] [1] [2] (2,4] (4,8] (8,16] (16,32] (32,64] (64,128] 0.1 0.2 0.3 批量加载比例 0.7 0.8 0.9
0.4
0.5
0.6
(a) 误差范围 (b) 节点最大误差
图 7 近似拟合算法误差分析

4.3.3 索引大小比较
表 3 列出了不同数据集上批量加载 20M 数据后, 插入不同比例剩余数据时各算法的索引内存占用. 由于 LIPP
在内部节点存储真实数据, 因此 LIPP 不在比较范围内. DIC 增量学习的方式不适合动态变化的数据, 只比较其在只
读工作负载上的索引大小. 结果表明, DRAMA 在多数情况下都有较低的内存占用, 例如在读写比例为 0 的 Wiki 数
据集上, B+Tree、PGM、ALEX 和 DIC 的内存占用最高分别是 DRAMA 的 331.21、5.21、6.86 和 231.85 倍. 这是
因为 DRAMA 根据估计的开销构建索引, 为了均衡索引性能与内存占用, 调整了模型参数. 如表 3 所示, 不同的数据
集对应的索引内存占用差异较大, 均匀分布数据集的内存占用通常小于倾斜分布的数据集. 这是因为均匀分布的数
据集使用较少的节点就可以实现较好的性能, 而对于倾斜分布的数据集通常需要更多的节点来对数据分区.

表 3 索引大小比较 (Bytes)

数据集 比例 DRAMA B+Tree PGM ALEX DIC
0 227 222 21 250 544 396 152 1 882 312 14 875 380
Osmc 0.5 835 040 87 970 240 741 936 2 284 600 －
1 234 440 90 109 792 868 944 2 354 088 －
0 2 411 968 21 250 544 696 672 5 987 752 －
Lat 0.5 8 894 432 140 251 088 1 896 536 22 875 480 －
1 2 347 513 148 751 360 1 973 704 23 820 912 －
0 8 280 21 250 544 110 096 7 232 14 875 380
Uniform 0.5 20 608 80 052 920 320 640 28 736 －
1 8 296 96 418 837 372 088 28 947 －
0 14 240 21 250 544 402 720 18 368 －
Amzn 0.5 24 970 88 190 288 975 640 26 144 －
1 18 200 90 525 136 1 055 160 26 448 －
0 64 160 21 250 544 333 976 439 904 14 875 380
Wiki 0.5 523 408 148 751 360 487 960 2 731 832 －
1 53 104 148 751 360 487 960 2 782 128 －