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

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

实验结论 5. LA-tree 的树形结构均匀数据划分, 提高索引面对不同查询负载时的鲁棒性和泛化性能. LA-tree
的索引更新主要面临两方面挑战: 一是如何将更新开销控制在足够低的水平, 以避免显著增加系统负担; 二是如何
适应不断变化的数据分布与查询负载, 从而持续保持在线查询的高性能.
在表 8 所示的更新实验中, 最优结果用加粗表示. LA-tree 设置各节点自适应更新阈值 τ 为评分函数较索引构
建时升高 30%. 如表 8 所示, 与对比方法, 即定期重构方法相比, 自适应增量更新在效果和效率上均具有显著优势,
读写操作吞吐量提高 12 倍. 在索引更新效率方面, 总用时下降了约 97%. 在查询性能和索引规模方面, 自适应增量
更新同样优于其对比方法. 定期重构方法在每次更新时需将原始数据、历史查询负载与新增数据、查询合并, 导
致大量冗余, 既使索引规模迅速膨胀, 也拖累了查询性能. 而自适应增量更新通过局部重构避免了这种冗余, 从而
在平均查询用时和更新后索引大小上均表现更优. 唯一的代价在于, 自适应增量更新需维护额外的分布统计信息,
使初始索引大小增加约 8%. 但这一开销相对较小, 几乎可以忽略不计.

表 8 LA-tree 更新方法综合比较

LA-tree索引更新 读写操作吞吐量 (TPS) 索引更新总用时 (s) 初始索引大小 (MB) 更新后索引大小 (MB)
定期重新构建 11 000 261 239 409
自适应增量更新 143 000 7 259 305
提升 12倍 97% –8% 25%

实验结论 6. LA-tree 的自适应增量更新方法能够同时保持低查询延迟与高更新效率, 相比定期重构方法大幅
减少了更新开销, 从而显著提升了动态场景下的索引性能.

7 讨论: 数据库系统集成学习型多维索引
结合已有的学习型多维索引综述和实验类论文 [13,14] , 学习型多维索引, 如本文提出的 LA-tree, 可以集成进数
据库系统. 本节将讨论集成学习型多维索引所需修改的数据库组件, 以及集成后对索引性能对比实验结果的影响.
集成需在数据库系统的索引管理器、存储、查询优化器这 3 个组件上做相应修改. 具体地, 实现索引管理器
中离线构建和在线访问索引的接口, 让数据库系统可以调用 LA-tree. 存储的数据分页逻辑与学习型索引的数据划
分结合, 避免学习型索引同一单元内的数据跨越多页, 带来不必要的 I/O 开销. 查询优化器部分更换学习型或基于
多维统计信息的代价估计方法, 原因是当前数据库系统内置代价估计方法通常假设数据表各维度独立, 估算多维
查询的基数很不准确, 需要更准确的代价估计生成合理的查询计划调用索引.
从实验结果影响的角度分析, 由于更多的外存 I/O 开销, 各学习型索引性能相比内存场景会有一定下降, 但相
对传统索引的优势, 以及不同学习型索引之间性能差异的趋势基本不变. 首先, 学习型索引数据扫描比显著相比传
统索引有数量级的下降, 显然访问的数据分页数也相应下降, 这直接大幅降低了索引的 I/O 开销, 从而减少查询用
时, LA-tree 在这方面优势更加明显. 其次, 学习型索引筛选数据的算法复杂度明显低于基于数值比较的传统索引,
且避免了大量比较操作带来的分支预判错误, 大幅降低索引的 CPU 开销. 此外, 随着数据库系统的缓存机制的不
断完善, 外存场景相比内存场景对索引性能的影响将有效降低. 本文的实验结果从筛选和扫描两方面综合比较索
引性能, LA-tree 相比其他方法的领先优势将直接体现在 I/O 与 CPU 开销的减少上.

8 学习型索引相关工作

● 学习型单维索引. 在数据库系统中, 每个索引通常作用于数据表的单个属性, 即单维索引, 用不同的平衡树
数据结构 [15,16] 或哈希算法 [17,18] 等把数据映射为多个分区以加速在线查询处理. 这些传统索引方法具有明显缺陷限
制其性能进一步提升, 如基于平衡树的索引在查询时需要大量数值比较操作, 使性能较低; 基于哈希算法的索引通
常会丢失保序性, 不适用于数值型属性, 而保序哈希算法 [18] 的函数计算代价高, 额外空间消耗大, 也不适用于数据
库系统. 学习型单维索引的相关工作 [19−22] 主要基于平衡树索引的思想, 利用机器学习模型替代比较操作以进一步
减少在线查询用时. Kraska 等人 [19] 提出学习式索引 RMI, 在 B 树结构上用线性回归模型 (LM) 直接从分位值映射