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

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

4.2 工作负载及基准算法
本文实验沿用一维学习型索引通用的工作负载模式. 为了更好地反映复杂的负载情况, 模拟数据更新频繁的
场景, 本文采用 6 种读写比 (插入比分别为 0, 0.2, 0.4, 0.6, 0.8, 1) 的工作负载对比不同索引的性能. 对于只读工作
负载 (插入比为 0), 评估了 20M 次读操作 (点查询); 对于读写工作负载, 评估了 200M 次的混合读/写操作, 分批次
执行 (1M 次/批). 批次内的工作负载按先读后写及该负载的读写比进行. 例如, 对插入比为 0.2 的工作负载中的每
个批次, 先执行 0.8M 次读操作, 然后执行 0.2M 次写操作.
本文将 DRAMA (除消融实验外仅使用 LLPC 压缩策略) 与传统索引 (即 B+Tree) 和 4 种代表性的学习型索引
进行比较, 包括 PGM、ALEX、LIPP 和 DIC. STX B+Tree 是一组在主存中实现 B+Tree 键/数据容器的 C++模板
类. 通过将多个键值对打包到树的每个节点中, B+Tree 减少了堆碎片化, 并更好地利用了缓存行效应. PGM 是一
种使用分段线性函数的学习型索引, 使用流式算法根据误差阈值来构建索引. ALEX 是一种可更新的自适应学习
型索引, 用于内存中的操作, 其使用间隙来实现写操作, 并使用灵活的布局来提高性能. LIPP 通过在每个节点存储
不同的数据项, 准确地预测位置并解决数据冲突. DIC 用于对比强化学习下的一维索引的性能, 由于其增量学习不
适合动态变化的数据, 因此仅用于测评点查询性能.

4.3 实验结果与分析
本节在 6 个指标上比较不同算法的性能. 整体吞吐量: 衡量不同算法每秒平均能处理的操作数, 反映了算法对
操作的响应速度. 预测误差: 反映了本文提出的近似拟合方法随着插入数据量变化模型预测误差的变化趋势. 索引
大小: 记录不同索引结构占用的内存大小. 压缩策略: 采用消融实验的形式, 反映了在本文所提结构上使用无损压
缩策略和有损压缩策略的内存占用和查询效率的影响. 查找时延: 衡量在不同工作负载和不同查询分布的情况下
执行点查询的平均执行时间, 表示算法对不同工作负载与查询分布的响应速度. 插入时延: 衡量在不同工作负载下
插入操作的平均执行时间, 表示算法对更新的响应速度.

4.3.1 整体性能比较
首先进行实验比较不同插入比例下所有算法的整体性能. 图 6 给出了处理不同工作负载时算法的整体吞吐
量. 可以发现, 几乎在所有数据集上, DRAMA 始终优于所有其他索引. 例如, 在 Osmc 数据集下, DRAMA 的整体
吞吐量分别是 ALEX、LIPP、DIC、PGM 和 B+Tree 的 1.97、2.02、3.88、5.13、5.50 和 9.30 倍. 在 Wiki 数据集
下, 它相对于 ALEX、B+Tree、PGM、LIPP 分别平均快 5.29、7.29、7.89、33.57 倍. 这个结果主要归功于
DRAMA 在处理数据插入时避免频繁在线计算, 同时在一定程度上保证了近似拟合模型的精度. 由于更新缓冲区
采用段间有序、段内无序的分段策略, 同样加速了查询过程. 这个特性允许在对每个新到达的键进行处理时, 具
有 O(H+N seg ) 时间复杂度. 相比之下, B+Tree 需要执行多次分支与比较操作处理查询; PGM 只是在缓冲区满后重
新在线执行分段策略; LIPP 则是通过分裂的方式处理冲突, 随着插入数据或插入频率增加, 树的高度随之增加进
而影响查询性能; ALEX 预留的间隙可以容纳一部分插入的数据, 但插入数据持续增多时, 仍需移动数据; DIC 虽
然使用强化学习找到现有传统有序索引结构与无序索引结构 (B-Tree 和哈希) 的近似最优组合, 但它并没有对这
两种索引结构进行优化, 仍然存在与传统索引相同的限制.

DRAMA B+Tree PGM LIPP ALEX DIC
30 40 30 60 20
吞吐量 (10 6 ops/s) 20 吞吐量 (10 6 ops/s) 30 吞吐量 (10 6 ops/s) 25 吞吐量 (10 6 ops/s) 40 吞吐量 (10 6 ops/s) 15
35
25
50
25
20
15
20
30
15
10
15
10
20
10
0 5 10 5 0 5 0 10 0 5 0
0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0
插入比例 插入比例 插入比例 插入比例 插入比例
(a) Osmc (b) Lat (c) Uniform (d) Amzn (e) Wiki
图 6 不同算法吞吐量比较

此外, 由图 6(b)、(e) 可知, 在 Lat 和 Wiki 数据集的只读工作负载下, DRAMA 的吞吐量略逊于 ALEX. 这是因
为 Lat 和 Wiki 数据集存在局部倾斜, 而 DRAMA 的开销模型与 ALEX 开销模型计算的扇出不同. DRAMA 计算
的扇出可能是一个相比于 ALEX 扇出的局部最优解. 因此在没有近似拟合等优化策略的只读倾斜工作负载下,