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

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

更新往往存在一定的规律和特征. 因此, 如何及时响应这些频繁的数据查询和更新操作是研究的关键.
索引在数据库中扮演着至关重要的角色, 主要用来提高查询效率. 索引的性能在一定程度上决定着数据库的
查询性能. 索引结构需要牺牲额外内存空间, 用以存储数据库表中 1 列或多列的属性值 (key) 的排序结果, 以及表
中对应数据在物理标识数据页中的逻辑指针列表. 由于高内存开销, 传统的索引结构难以处理爆炸式增长的数据,
随着数据量大规模增加, 数据关系更加复杂, 传统索引占有的存储空间也随之增加, 查询速度变得越来越慢. 为了
解决这些问题, 学习型索引概念进而被提出, 已成为当今数据库领域的研究热点 [1−2] .
早期的学习型索引使用机器学习模型取代传统的索引结构 (树形结构、网格结构等), 模型在存储和使用方面
[3]
[4]
都有显著的优势. RadixSpline 针对一维数据优化分段策略, 用线性插值模型适应不同段内数据的分布. LISA 、
[5]
[6]
[7]
Flood 、Tsunami 、LMSFC 将类似策略运用于高维数据中, 先将高维数据降维到一维或用空间插值函数, 找到
key 与顺序存储位置的映射模型. 但这些高维学习型索引存在频繁更新困难这一致命的缺陷. 因为索引中的模型
是通过对原始数据和记录位置之间的关系进行学习和分析得到, 在插入新数据时, 会破坏原始的数据分布, 旧的模
[9]
[8]
型偏离原始数据分布, 在大量更新后, 不得不进行在线重新训练. LIFOSS 、FLIRT 考虑流数据场景下的索引, 虽
然数据频繁更新, 但数据规模限制在一个滑动窗口内, 解决方案完全不同.
一些研究如 DIC [10] 、RLR [11] 另辟蹊径, 依靠强化学习的强大决策能力, 在索引构建过程中充分考虑了数据集
的数据分布和查询分布, 找到现有传统有序索引结构与无序索引结构 (B-Tree [12] 和哈希 [13] ) 的近似最优组合, 构建
出最理想的结构. 尽管它利用强化学习来增强传统索引性能, 但它仍存在与传统索引相同的缺陷. 并且随着数据的
不断更新, 索引会逐渐“偏离最优结构”, 除非定期在线重新训练, 性能依旧不理想. 如图 1 所示, 重训练的代价是无
法容忍的查询时延. 因此, 如何避免或延缓重新训练, 已成为学习型索引可持续发展的挑战.

1E6 1E5 重训练时间
插入时延 (ns) 2 1 时间 (ns) 5 插入时间

0
0 0.5 1.0 0 1 2 3 4 5 6 7 8
插入数据量 1E5 重新练次数
(a) 插入 0.1 M 键每次的插入时延 (b) 重训练时间与插入时间的比较
图 1 模型重训练对索引性能的影响

在目前一维学习型索引的研究中, 大多通过存储机器学习得到的模型 (如线性回归模型) 来表达数据的存储
分布, 辅助或取代传统的索引结构, 从而实现更低的内存占用和更高的查询性能. 面对数据更新, 其处理方案分为
以下 3 类. (1) 预留间隙处理更新. 例如 ALEX [14] 根据一定密度在每个叶子节点预留间隙, 在最初插入时只需移动
少量键甚至不移动即可完成数据的插入. 然而, 随着插入数量逐渐增多, ALEX 会因为空隙区域变满、空闲空间变
少, 使冲突随之增加, 因而需要移动大量键来处理插入操作. (2) 额外的缓冲区加速更新. 例如 PGM [15] 等, 通过为每
个段添加额外的缓冲区来处理更新操作. 当缓冲区满时, 需要重新执行分段, 即重新训练模型. (3) 分裂处理冲突.
例如 LIPP [16] 通过向下分裂创建新节点来处理插入导致的冲突. 但数据更新会影响当前数据的分布, 随着模型的逐
渐失效, 这些工作需要频繁改变自身结构, 甚至是定期在线重新训练来处理数据更新, 从而使其性能受到影响. 上
述工作在处理数据更新时, 几乎都会增加额外的内存消耗. PGM 提出了一种有损压缩方法来降低内存占用, 但这
种有损参数压缩方式影响索引查询性能.
Waffle [17] 首次将强化学习用在处理移动目标查询的索引更新问题上, 其底层的网格结构支持并发进行索引的
访问和索引结构的更新调整, 避免了因为重构索引而导致的查询暂停. 线程中的强化学习持续进行, 代替“阻塞式”
的重新训练, 动态的二维网格结构可以不断地适应频繁变化的数据. 移动目标场景下的数据变化特征 (key 的总量
基本不变, 但分布实时变化) 与通用场景下的一维数据的随机更新明显不同, Waffle 的相关策略和算法并不能直接
应用到对一维索引结构的更新中. LSM RUM-Tree [18] 利用 LSM-Tree [19] 思想优化传统高维索引 R-Tree 的更新策略,
但不能直接用于一维学习型索引的更新优化.