Page 345 - 《软件学报》2026年第5期

2224 软件学报 2026 年第 37 卷第 5 期

表 3 轨迹数据集属性表

数据集 时间范围 轨迹条数 轨迹点数 采样频率 (s) 网格密度标准差
深圳市 2013年10月22日0–24时 562 917 006 30 2.4
柏林市 2003年11月20 日6–9时 302 51 544 120 0.5
随机 2008年2月2日15时–8日15时 3 203 5 222 752 300 1.2

经典 RMI 结构采用两层模型, 第 1 层为 1 个前馈神经网络, 第 2 层为依据数据集划分数据生成的若干个前馈
神经网络, 神经网络中的隐藏层均为 2 层, 激活函数为 ReLU, 神经元数量固定为 100. RMI 在查询过程中体现出学
习索引的典型特点, 即索引输入为 1 个查询键, 经第 1 层神经网络预测后, 得到第 2 层模型的编号, 进入预测指定
的第 2 层神经网络, 随后再次经过神经网络预测, 得到预测的查询值位置, 在数据存储列表中的误差范围内开展遍
历查询. 但是, RMI 结构并未设置支持动态更新的模型扩展及分裂机制, 仅存在模型中固定大小的缓冲空间, 插入
此结构的数据和键值不能自由选择位置只能插入指定的缓冲空间, 会影响后续对该查询键的位置预测准确性, 同
时, 因为缺乏扩展分裂机制, 在缓冲空间被填满后, 该模型需要重新进行训练, 对新的数据集排序划分子集后, 再次
循环若干子模型, 构造出新的 RMI 结构.
ALEX 作为可更新自适应学习索引, 通过融合学习索引的分布感知能力与传统 B+树的结构优势, 在动态工作
负载场景中实现了性能突破. 首先, 采用模型导向的插入策略, 基于线性回归模型预测数据分布, 通过贪心插入算
法优化键值存储位置; 其次, 设计自适应节点扩展机制, 根据数据增长模式动态选择节点分裂或就地扩展策略, 结
合间隙预留技术平衡空间利用率与更新效率; 最后, 构建混合存储布局, 在内部节点集成数组存储与间隙控制. 但
索引性能对数据分布平稳性具有较强依赖性, 在面对非平稳数据流时需引入在线模型重训练机制, 带来额外计算
开销, 在强实时更新系统中仍需权衡性能与维护成本.
6.2 非均匀网格索引实验
NUGC_LI 索引构建结构及所用函数在上述部分已有说明, 误差值 err 为 10, 误差区间 ErrINR 为 20, 根节点
中线性模型的斜率为 1.0/(key max −key min ), 截距为 −key min /(key max −key min ), 根节点与中间节点的线性模型输出均为
CDF 函数, 输出值为 [0, 1] 之间的概率值, 由概率值对应归一化后的模型编号或数据位置, 就能确定下一阶段应选
节点, 各节点最大容纳空间为 16 MB, 根据键值大小 (64 KB), 理论最大扇出数为 256.
6.2.1 学习索引节点阈值对比
NUGC_LI 索引节点中设置有节点阈值 NodeTHR 为后续判断节点是否需要扩展或分裂提供参考, 对 NodeTHR
参数的不同选择对索引性能的影响设置了对比实验, NodeTHR 的计算公式在定义 11 中已作详细说明, 易知公式 (16)
中 X 的设置直接决定了 NodeTHR, 因此下列对 X 的不同取值下索引的性能进行了实验分析, 对 X 进行 50%–90%
区间内的不同取值, 实验结果如图 8 所示.

构建时间代价 查询时间代价 时间代价

1.4
1.2 0.95
构建/查询时间代价 (s) 0.8 0.90 时间代价 (s)
1.0

0.6
0.4
0.2
0 0.85
50 60 70 80 90
X (%)
图 8 不同节点阈值性能对比图