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

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

lightweight linear model and piecewise linear model are introduced to transform traditional numerical comparisons to fast mapping
computations, thereby reducing filtering latency while ensuring the completeness of query results. In dynamic settings, an adaptive
incremental update mechanism based on scan volume monitoring is proposed to efficiently adapt to changes in data and query workloads
via local subtree reconstruction, thereby avoiding the high cost of rebuilding the entire index. Experimental results demonstrate that LA-
tree outperforms existing methods on multiple real-world and benchmark datasets. In static settings, the query time is reduced by an
average of 52% compared with the optimal benchmark method, while in dynamic settings, the update costs are reduced by 97% compared
with the reconstruction methods. Additionally, low query latency and lightweight index scale are maintained.
Key words: learned multi-dimensional index; query-aware; index update

索引结构对数据库查询性能至关重要. 随着数据维度的增加, 数据库查询通常在多个属性上包含等值或范围
谓词, 单维索引难以同时利用多维条件, 导致大量无效扫描. 相比之下, 多维索引能够在多个维度上联合组织和过滤
数据, 从而显著减少冗余访问并提升查询效率. 因此, 高效的多维索引已成为支持现代数据管理与分析的关键技术.
[3]
[1]
[2]
[5]
现有多维数据索引方法, 如 KD-tree 、Octree 、Qd-tree 、Flood 和 [4] Tsunami , 普遍采用空间划分的方式
来提升多维查询性能. 在离线阶段, 这类方法将数据映射到多维空间并划分为若干单元 (cell); 在在线查询阶段, 采
用一种“先筛选、后扫描”的框架, 即首先通过多维索引筛选出与查询范围有交集的单元, 再扫描单元内的数据以
生成查询结果. 通过在筛选阶段排除大量位于查询范围之外的数据, 这一框架可以有效减少数据扫描量, 从而提升
查询效率. 具体而言, 根据拟合数据分布的方法, 现有方法可以分为两类.
[6]
● 学习型多维索引 Flood 和 Tsunami 通过网格 (grid) 结构拟合多维数据分布. Flood 直接通过学习型网格沿
各维度独立地对数据进行划分, 从而建立多维索引. 为了解决多维数据普遍存在的维度间相关性, 需要引入条件分
布增强网格以拟合数据的多维联合分布, 然而时间与空间开销关于相关维度数量呈指数级增长. Tsunami 通过
Grid-Tree 结构根据查询负载将数据划分为多个子集, 分别用网格拟合数据分布, 同样无法克服网格拟合多维相关
性的弱点. 因此该类方法仅适用于低维数据场景, 在维度较高 (如 10 维以上) 的场景下效率不高.
● 树形多维索引结构 (如 KD-tree、Octree、Qd-tree 等) 通过递归划分数据空间拟合多维数据分布, 将数据组
织为层次化的树结构, 不仅能够自适应数据的多维联合分布, 还支持高效的层次化剪枝策略, 因此可以快速排除与
查询条件无关的单元. 与基于网格的索引相比, 树形索引在维度的可扩展性和空间利用率上更具潜在优势.
基于此, 本文重点研究基于树形结构的学习型多维索引. 现有研究 [3−5] 表明, 当前多维索引在查询过程中仍存
在大量查询范围之外的数据未能在筛选阶段被有效排除, 从而导致扫描量大、扫描时间长, 成为影响查询效率的
核心瓶颈. 因此, 本文聚焦优化多维索引的筛选问题, 具体而言: 一方面在离线索引构建阶段优化数据划分, 另一方

面在在线查询中提升筛选效率, 最终提升多维索引的整体性能.
[1]
然而, 现有的树形多维索引在筛选效果上仍存在局限性. 传统多维索引结构 KD-tree 采用递归的空间均匀划
分, 能够在叶子节点上保持数据量基本平衡. 但其划分策略完全独立于查询负载. 然而, 真实情况下, 查询负载并不
[1]
随机, 而是具有一定的查询模式 (query pattern), 即在多维数据的不同属性维度和范围上冷热不均, KD-tree 难以
[3]
针对查询负载对数据划分进行优化, 导致查询需访问过多单元 (即索引的叶子节点). 与此相对, Qd-tree 通过学习
查询负载, 在高频查询边界处划分数据, 从而可以避免查询访问过多的单元. 然而, 由于划分仅依赖于查询模式, 而
不考虑数据分布, 单元间数据量往往极不均衡, 部分单元可能包含大量数据, 依然增加了数据扫描量. 由此可见, 现
有树形多维索引方法难以兼顾“均匀划分”与“查询感知”.
针对上述问题, 本文提出了一种新型的学习型多维索引 LA-tree, 在均匀划分的基础上引入查询感知优化, 从
而兼顾了数据分布平衡与查询模式适应性. 图 1 给出了 LA-tree 与现有树形多维索引方法的对比示意: 下层 3 幅
图展示了在给定多维数据 (灰色散点) 与查询负载训练集 (绿色方框) 上的离线数据划分结果; 上层 3 幅图则对比
了在线查询阶段的筛选效果. 结果显示, KD-tree (图 1(a)) 因缺乏查询感知, 筛选不充分, 需扫描的大量灰色区域导
致扫描量偏高; Qd-tree (图 1(b)) 虽能针对查询模式优化, 但划分极不均匀. 尽管查询需要访问的单元个数减少, 但
需在包含大量蓝色散点的单元中扫描, 依然导致较大的扫描量; 而本文提出的 LA-tree (图 1(c)) 在保持均匀划分的
同时融入查询感知优化, 有效减少了需扫描的单元与数据量, 显著提升了查询效率.