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

刘佳伟 等: LA-tree: 查询感知的自适应学习型多维索引 487

为实现高效的多维数据查询, 本文围绕 LA-tree 索引面临的 3 个关键技术挑战进行研究.
挑战 1: 离线索引构建. 在树形索引递归划分多维数据时, 需要同时保证划分的均匀性与查询感知, 这一过程
因数据分布与查询负载的复杂性而极具挑战. 为此, 本文将问题建模为节点划分维度选择优化, 提出多层次查询感
知的数据划分方法: 通过高效估计不同维度对查询扫描比的影响, 并结合多级搜索贪心算法, 自顶向下地生成树形
划分结构, 从而在保证均匀性的同时提升查询性能.
挑战 2: 在线查询处理. 在线查询阶段的核心在于快速且准确地定位与查询范围相交的单元, 并高效完成筛选.
然而, 树结构往往包含大量节点, 叶子节点对应的单元也存储多条数据, 传统依赖数值比较的方法会导致计算开销
过大. 为此, 本文提出基于学习模型的高效在线筛选方法: 在中间节点与叶子节点分别引入轻量化模型, 实现查询
边界到数据位置的快速映射, 从而有效减少扫描量并避免频繁的数值比较. 同时, 通过误差界限约束保证模型筛选
的正确性, 确保筛选与扫描结果的完整性.
挑战 3: 动态更新. 在动态场景下, 数据更新会破坏索引划分的均匀性, 而查询负载的变化也可能使原有的查
询感知划分失效. 直接重建索引虽能恢复性能, 但开销过高, 不适合频繁更新. 为此, 本文提出自适应增量更新方
法: 通过轻量化模型快速定位更新数据的位置, 实现低开销的增量更新. 同时, 实时监控数据分布和查询负载变化
对扫描量的影响, 自动触发局部子树重构, 从而在无需整体重建的情况下持续保持低查询延迟.

100 100 100
80 80 80
60 60 60
Y Y Y
40 40 40
20 20 20
0 0 0
0 10 20 30 40 50 0 10 20 30 40 50 0 10 20 30 40 50
X X X

100 100 100
80 80 80
60 60 60
Y Y Y
40 40 40
20 20 20
0 0 0
0 10 20 30 40 50 0 10 20 30 40 50 0 10 20 30 40 50
X X X
(a) KD-tree (b) Qd-tree (c) LA-tree
图 1 多维索引不同的数据划分方式对查询性能的影响

总结起来, 本文的主要贡献如下.
(1) 提出 LA-tree 索引结构. 设计了一种基于学习型空间划分多叉树结构的多维索引 LA-tree, 在同一框架下实
现了“均匀划分”与“查询感知”, 解决了传统 KD-tree 与 Qd-tree 在数据划分上的局限性.
(2) 针对 LA-tree 设计了高效的算法. 分别设计了多层次查询感知的数据划分方法、基于学习模型的高效在线
筛选方法, 以及自适应增量更新方法, 有效地解决了离线索引构建、在线查询处理和动态更新这 3 大挑战.
(3) 在多种数据集和查询负载下进行了充分的实验. 在权威的基准数据集上, LA-tree 在静态场景下平均查询
用时相比已有最佳方法减少约 52%, 且在高维查询下优势更加显著. 在动态场景中, 自适应增量更新方法使索引更
新用时相比定期重构减少 97%, 同时保持低查询延迟和较小的索引规模, 验证了 LA-tree 在性能上的优势.