Page 357 - 《软件学报》2026年第2期

836 软件学报 2026 年第 37 卷第 2 期

对于范围查询, 往往需要先通过点查询预测两个端点位置, 然后扫描两个端点位置范围内的数据返回满足范围查
询的键值.

查找
f 0,0 (k)
插入
f 1,0 (k) f 1,1 (k) f 1,2 (k)

f 2,0 (k) …n−2… f 2,n−1 (k)
原地插入
缓冲区
位置搜索 插入
E of f 2,0
Insert buffer Insert buffer
图 7 一维学习型索引标准化架构

表 5 一维学习索引

查找 插入/删除
索引方法 模型 块加载
节点设置 位置搜索 策略 数据结构
RMI [159] 简单神经网络/线性回归 无特殊设置 二分查找 无 无 从上到下
[160]
XIndex RMI/分段线性回归 无 二分查找 插入缓冲区 基于误差的节点分裂 从下到上均匀划分
SIMD指令
[161]
FINEdex 分段线性回归 无 插入缓冲区 缓冲区满训练合并 从下到上, 贪心策略
优化的搜索
[162]
SIndex 线性回归 无 二分查找 插入缓冲区 缓冲区合并 从下到上, 贪心策略
[163] 间隙数组原 基于代价的节点合并/
ALEX 线性模型 间隙数组 指数搜索 基于代价, 从上到下
地插入 分裂
MADEX [164] 线性插值 元数据 CDF模型+ 原地插入 缓冲区满节点分裂 从下到上, 贪心策略
矫正模型
缓冲区满或冲突, 子树
[165]
LIPP 非线性模型 条目及位向量 精确位置 原地插入 基于冲突分裂从上到下
重建

对应上述查询的 3 个阶段, 影响查询效率的关键因素主要有以下 3 方面, 分别是层次结构本身、节点模型和
搜索算法. 首先, 层次结构本身也就是学习索引的结构框架, 包括层级结构设计、节点的设计和额外信息的存储设
计. 如 ALEX [163] 区分了数据节点和内部节点, 同时在内部节点使用了额外空间存储其子节点信息. 节点模型包括
线性模型与非线性模型, 线性模型往往能获得更快的查询速度, 但是查询精度较差, 非线性模型往往具有较好的查
询精度, 但是计算代价更高, 非线性模型主要有多项式拟合模型和神经网络模型两种. 非线性模型的另一个优点是
支持比线性模型更多的键, 因此单个节点包含更多数据且树的深度小. 除此之外一些方法尝试混合使用线性模型
和非线性模型, 例如, XIndex [160] 采用两层分层结构, 其中第 1 层使用 RMI [159] 模型 (因为第 1 层包含许多键值), 第
2 层节点使用分段线性模型. 一些方法预测完全准确, 无需重新调整预测结果, 如 LIPP [165] . 另外一些方法, 仅在叶
节点存在预测误差如 RMI、ALEX, 因此只需要在叶节点模型误差边界范围内搜索. 如果叶节点和内部节点均存
在错误, 则需要在叶节点和内部节点均进行修正. 针对不同的误差大小, 搜索算法也不尽相同. 如果搜索误差较小,
线性搜索更为高效, 如果搜索误差较大, 可以使用二分查找的方法, 或者二分查找的变体, 如指数搜索、插值搜索等方法.
插入就是将新的键值插入正确的位置. 由于学习索引需要维护数据有序性, 所以键值插入往往比传统索引更
为复杂. 插入新的键值可能会改变索引的部分结构, 或者导致节点模型的重新训练. 一般来说有两种不同的方案支
持键值插入, 分别是原地插入和临时缓冲区. 原地插入方法, 如 ALEX [163] 、MADEX [164] 、LIPP [165] 就是找到新插入
键值的正确位置, 然后直接将数据进行插入并根据情况判断是否需要对索引结构进行调整. 基于临时缓冲区的插
入方法, 如 XIndex [160] 、FINEdex [161] 、SIndex [162] 就是增加一个临时缓冲区, 当缓冲区满就将缓冲区中的数据统一