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

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

综上所述, 现有的一维学习型索引尚未效解决由于数据频繁更新导致的模型重新训练问题, 且没有针对学习
型索引的无损压缩方法来减小内存占用. 本文提出了以下解决方案. 首先, 利用数据的更新分布优化索引结构从而
提升后续的查询性能. 但数据通常是随机插入或删除, 无法提前得到其更新分布信息, 因此本文借鉴 LSM-Tree 延
迟更新的思想, 将随机插入数据存储在更新缓冲区中, 达到一定数量后才学习数据的更新分布并近似拟合
(approximate fitting, AFit) 更新分布模型, 然后执行原数据分布模型与更新分布模型的快速合并操作, 根据合并后
的模型重新设置叶子节点. 同时, 为了均衡查询与更新性能, 提出了一种缓冲区分段策略. 其次, 由于大多情况下每
个节点的扇出不同, 为了加速索引构建, 基于开销模型启发式选择扇出参数, 用以离散化连续的扇出值. 此外, 索引
结构是区间分割树型的层级结构, 且根节点的扇出值远大于其他节点. 基于结构的特性, 提出了混合参数压缩
(hybrid parameter compression, HPC) 策略, 以降低模型参数的内存占用.
本文主要贡献如下.
(1) 设计了一种随机插入环境下感知更新分布与压缩内存占用的学习型索引结构 DRAMA, 实现了更高的插
入性能与较低的内存占用.
(2) 基于区间分割树的特性, 提出了一种无损压缩策略来降低索引内部节点的内存占用; 在叶子节点中采用有
损压缩策略, 通过调节压缩系数, 可实现查询效率和内存空间占用的折中.
(3) 提出了一种加速更新的策略, 利用近似拟合的思想, 用局部数据模型合并代替在线的模型重训练过程.
(4) 在合成和真实数据集上与典型索引结构进行大量实验对比, 验证了卓越的性能.
本文第 1 节介绍典型学习型索引的相关方法和研究现状. 第 2 节介绍本文构建的索引结构, 包括索引构建、
近似拟合以及混合参数压缩策略. 第 3 节介绍基于本文构建的索引结构的查询处理过程. 第 4 节通过对比实验验
证所提索引结构与优化策略的有效性. 最后总结全文.

1 相关工作
一些传统索引结构的研究工作 [20,21] 通过捕获数据分布等信息, 充分利用统计学方法进行启发式的优化索引结
构, 为学习型索引的产生奠定了理论基础, 也为机器学习更广泛地应用于数据库的索引和查询优化提供了启发性
思想. RMI [22] 是学习型索引的先驱, 首次将索引视为模型, 其利用训练好的模型来预测输入键的位置, 并根据数据
的累积分布函数 (cumulative distribution function, CDF) 来学习数据分布. 其内部节点用于分区, 叶子节点预测输入
键的位置, 最快可以在 O(1) 时间内完成查询. 由于 RMI 利用了数据分布, 且不涉及传统索引中大量的比较操作,
因此它显著提高了索引的性能. 此外, 由于 RMI 仅存储斜率和截距参数也显著减少了索引的空间开销. 然而, 由于
数据在内存中以升序的方式存储在一个紧密数组中, 因而无法很好地处理数据更新.
本文仅关注支持数据更新的一维学习型索引, 与目前相关研究工作的解决数据更新策略有所不同. 表 1 对比
了 B+Tree (传统索引结构代表) 和一维支持更新的学习型索引 (*标识的将在后面的实验中进行对比) 的结构、查
询与插入策略的异同点.

表 1 支持更新的一维学习型索引策略比较

索引 结构 搜索策略 二次搜索方式 插入策略 插入优化策略
*B+Tree 树形结构 自上而下遍历 二分搜索 就地插入 扩展与分裂
*DIC 树形结构 自上而下遍历 二分搜索/哈希 就地插入 扩展与分裂
FITing-Tree 树形结构 分段线性模型预测 二分搜索 额外缓冲区插入 重训练
ASLM, Dabble 单层结构 神经网络模型预测 二分搜索 额外缓冲区插入 重训练
*PGM 树形结构 分段线性模型预测 二分搜索 额外缓冲区插入 重训练
RUSLI 分段结构 基数表+插值函数 二分搜索 额外缓冲区插入 重训练
Pluggable 框架 － － 预留间隙+链接数组 －
*ALEX 树形结构 线性回归模型预测 指数搜索 预留间隙就地插入 扩展、分裂与重训练
*LIPP 树形结构 核化模型预测 － 分裂后就地插入 向下分裂、向上合并
TALI 树形结构 线性回归模型预测 指数搜索 预留间隙就地插入 扩展、分裂与重训练