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

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

1.1 就地插入结构
Pluggable [23] 提出了一种可以用在多数学习型索引上的“数据适配模型”策略框架, 利用采样与模型驱动方式组
织数据, 即将数据存储在通过采样得到的模型指示的位置处. 这种先有模型后存储数据的思想, 既提高了模型的准
确率又预留了少许空间, 从而在一定程度上降低了因新数据到达而导致的位置冲突概率, 减少了数据移动代价, 但
对其于频繁的数据更新作用并不明显.
ALEX 是一种自适应的学习型索引, 能够有效处理数据更新并适应不同的数据分布. 其采用预留间隙的方式
来处理更新, 在插入一个键时, 首先执行点查询找到插入位置, 如果插入位置是一个间隙, 则可以直接插入键, 否则
通过移动数据创建一个间隙来完成插入. 然而, 当数据频繁更新时, ALEX 需要移动大量数据, 导致性能显著下降.
LIPP 是一种树形结构的学习型索引, 用节点分裂的方式处理数据冲突以支持精确查询, 将计算冲突度作为训练模
型的目标. 然而, LIPP 在处理大数据量时, 其性能受到树高的影响, 且偏斜的数据更新分布会导致极度不平衡的树
形结构. TALI [24] 在已知数据更新分布的情况下, 利用数据更新特征优化索引的更新性能. 但现实环境下数据更新
分布通常未知, 因此 TALI 无法有效解决无规律的数据更新问题, 也无法有效处理频繁且偏斜的数据更新.

1.2 异地插入结构

FITing-Tree [25] 结构类似于 B+Tree [26] , 使用分段线性函数来拟合数据分布, 并在每个段中预留一个固定大小的
缓冲区来处理数据更新. 一旦缓冲区满, 缓冲区数据将与段数据合并, 并重新执行分段算法和重训练模型. PGM 也
采用 LSM-Tree 的策略维护数据, 每个层级都维护一个学习型索引, 并在触发合并时重新训练更新相应的模型. 为
了减少空间占用, PGM 提出了一种模型参数的有损压缩存储结构.
ASLM [27] 、Dabble [28] 是单层索引, 在使用更少量模型的情况下即可快速完成读写操作. 为了支持更新操作,
ASLM 为每个子模型维护一个缓冲区, 用缓冲区中数据的平均误差来决定是否需要重新训练对应的子模型. 在处
理插入时, Dabble 模型利用 LSM-Tree 延迟的思想来实现数据写入. 将新数据放入 B-Tree 结构的缓冲区中. 当缓
存数据达到一定阈值时, 将缓存中的数据一次性归并到相应的数据分区中. 由于缓冲区的结构特性且没有一种快
速的合并策略, 因此这两种索引实时性会受归并数据和重训练的影响.
RUSLI [29] 在 RadixSpline 基础上增加了溢出数组来临时存储新数据, 用于支持低频少量的数据更新. 虽然考虑
到不同的数据段使用不同的溢出数组, 用并发查询来提高查询性能, 但由于底层数据的存储形式和 RMI 一样, 都
是将数据存储在密集数组中, 因此它在处理数据更新方面效率不高.

1.3 最优构建行为的学习

随着强化学习的发展和应用, DIC 引入了一个 NIS (neural index search) 的框架, 其兼顾传统索引的稳定性和
强化学习的强大决策能力, 在索引构建过程中充分利用了数据集的数据分布和查询分布, 找到传统有序索引结构
与无序索引结构 (B-Tree 和哈希) 的近似最优组合. RLR 利用强化学习强大的决策能力对 R-Tree 的构建过程进行
调优, 并基于强化学习模型决策待插入的子树以及节点的最优分裂. Waffle 将强化学习用在处理移动对象查询的
索引更新问题上, 自动进行参数选择和调优. WISK [30] 基于机器学习技术启发式地解决 R-Tree 的最优划分问题, 并
将自下而上逐级打包节点的索引构建过程视为一个序列决策过程, 进而基于强化学习构建索引结构. ACR-Tree [31]
提出了一种基于深度强化学习的 R-Tree 构建算法, 设计了一个深度神经网络模型来捕获空间数据分布, 有效地解
决了现有 R-Tree 批构建算法中贪心策略和全打包约束的限制. 尽管它们都利用强化学习来增强传统索引性能, 但
它仍存在与传统索引相同的限制, 且强化学习调优的研究目标是构建静态更优的索引结构从而减缓由于数据不断
更新导致的频繁重构. 本文的研究目标是加速局部数据模型更新, 用一种模型合并策略代替在线的局部模型重训练.

2 DRAMA 的构建与更新

本文提出的索引结构核心优化体现在 3 个方面: 索引构建、参数压缩及更新分布的近似拟合. 图 2 提供了索引
结构的概览. 首先基于开销模型启发式地确定索引结构. 为了处理随机插入并学习更新分布, 每个叶子节点设置了
一个带间隙的叶数组和一个更新缓冲区. 在实例化每个叶子节点时, 计算叶子节点模型参数与其置信区间 (定义 4),