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

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

范围. 通过这种方式, LA-tree 在保持筛选精度的同时, 避免了传统方法中低效的频繁数值比较, 将数据筛选转化为
学习模型“输入查询边界、输出数据位置”的快速计算问题.
例如, 图 2(a) 中根节点的模型能够根据查询 q 的范围 X ∈ [7,10] 定位到第 1 个子节点 X ⩽ 17, 其他中间节点以
此类推. 而左起第 7 个叶子节点的模型则可根据查询范围边界缩小候选扫描集, 对应图 2(b) 的 T 7 区域里浅蓝色阴
影覆盖的区域, 从而避免扫描大量查询范围之外的数据.
然而, 上述方法面临两个挑战: 一方面, 学习模型本身具有预测误差, 而索引必须保证结果的完整性, 即模型筛
选不能遗漏任何满足条件的数据. 另一方面, 常见模型推理耗时较长, 若直接使用反而降低索引性能.
针对上述挑战, 本文提出基于学习模型的高效在线筛选方法. 首先, 为了确保索引筛选结果的完整性, 提出了
误差界限约束, 利用保序模型的性质在学习数据分布时计算边界, 保证查询都不遗漏正确结果. 进一步地, 本文设
计了中间节点的线性回归模型 (linear model, LM) 与叶子节点分段线性回归模型 (piece-wise linear model, PLM) 相
结合的学习型空间划分多叉树结构, 使每个节点都能够在保证正确性的同时快速完成筛选. 有关该方法的技术细
节, 详见第 4 节.
2.4 LA-tree 的索引更新

在动态场景下, 面对数据与查询负载的变化, LA-tree 能够相应地更新索引结构, 从而保持索引的准确性和高
效性, 而无需整体重建. 具体包括两个方面: (1) 增量更新, 将新数据实时插入到叶子单元中排序后的正确位置, 实
现高效维护; (2) 自适应更新, 当检测到局部的数据划分出现不均匀或不再适应查询负载的情况时, 执行局部数据
重划分. 例如, 图 2(a) 中的 LA-tree, 利用增量进行更新, 一条更新数据 X = 10,Y = 70 会被准确地插入数据子集 T 7 .
利用自适应更新, 假设有大量 X ⩽ 17,Y > 61 范围内的数据更新使局部数据维度 X 和维度 Y 的相关性明显提高, 或
涉及该数据范围的大量新查询的谓词仅包含维度 X, 这棵子树都将以新数据子集与查询负载子集重构.
针对这两点, 本文提出自适应增量式的索引更新方法. 将更新的数据视作点查询, 自顶向下利用节点模型准确
定位数据位置. 同时, 将数据分布变化和查询负载变化对子树数据划分的影响统一到扫描量即扫描比, 实时比较新
查询在更新后数据上的扫描比和访问节点的评分函数值, 找到扫描比大幅增加的节点, 重构相应子树. 有关该方法
的技术细节请参见第 5 节.
3 离线索引构建: 多层次查询感知的数据划分方法

本文将查询负载感知的数据划分过程建模为一个优化问题: 在每个中间节点选择合适的划分维度, 以最小化
负载中所有查询的扫描比之和. 为解决这一优化问题, 第 3.1、3.2 节将分别探讨两个关键挑战, 即如何在不实际执
行查询的情况下估计单节点的扫描比, 以及如何在多层节点上高效选择划分维度.
3.1 单节点划分维度选择

单节点划分维度选择的目标是最小化 Q 中所有查询在数据表 T 上扫描比之和. 根据公式 (3) 定义, 扫描比的
分母总是确定的, 最小化扫描比之和等价于最小化扫描量, 即根据公式 (4), 优化目标为:

∑

min I (q) (6)
′
∈A q∈Q N k T N k
a N k
由于索引离线构建阶段不执行查询, 节点不同划分维度带来的扫描比变化无法直接衡量. 考虑中间节点结果
公式 (5), 我们提出优化比 OPR T,Q (a), 通过数据总量与按某维度划分查询负载所有查询需访问的子节点覆盖数据
量之和的比, 估计扫描比之和的上界, 如下:

1 ∑ ∑
a
minOPR T,Q (a) = min |T c | S (q,T ) (7)
c
a∈A a∈A |T||Q|
1⩽c⩽b q∈Q
a
其中, S (q,T ) 是一个 0-1 取值的函数, 表示经过节点维度 a 的划分, 查询 q 在数据子集 T c 关于维度 a 的值域上有
c
无交集. 进一步地, 在 (a): 以 1:1 N k 的
LA-tree 自顶向下构造树的过程中定义评分函数
OPRS T,Q,N k 的权重混合节点
所有祖先节点中维度为 a 的数量占比以及公式 (7) 中的 OPR T,Q (a). 我们的目标是选取使 OPRS T,Q,N k (a) 最小化的维