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

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

元范围, 这是由于 LA-tree 最后一层叶子节点将单元内数据子集根据累积分布函数 (cumulative distribution function,
CDF) 进行排序, 以进一步提高筛选效果.
以图 2(a) 中紫色框内的 4 个节点构成的子树为例展开分析. 首先, 根节点选择了维度 X, 并据此将数据均匀划
分为 3 份, 得到分位点 17 和 37. 随后, 根节点的第 1 个子节点在其对应 X ⩽ 17 的数据子集上选择 Y 维度将其对应
的数据集均匀划分为 3 份, 得到分位点 30 和 61. 需要指出的是, 根节点的其他子节点可以选择不同的维度进行数
据划分. 按照上述方式, 数据划分过程自顶向下递归进行, 直至达到叶子节点. 每个叶子节点对应一个单元 (cell),
存储一个数据记录的集合, 如图 2(b) 中数据子集 T 1 和T 2 所示. 基于上述 LA-tree 结构, 在给定在线查询 q 时, 索引
先自顶向下逐层筛选与查询范围 X ∈ [7,10]∧Y ∈ [45,82] 有交集的节点 (图 2(a) 中标为浅蓝色); 随后扫描所有标
蓝叶子节点对应的单元得到局部查询结果; 最后将这些局部结果合并, 返回最终的查询答案.
LA-tree 各节点维度是查询感知选择的, 以降低查询负载扫描的数据量. 以图 2(a) 紫框内的划分为例, 考虑图 2(b)
紫框内的查询, 可见查询基本聚成维度 Y 查询范围在 60 以上和 40 以下两簇, 因此首先按维度 Y 均匀划分数据. 接
下来, 上方的查询维度 X 选择度普遍很低, 因此这部分数据按维度 X 均匀划分. 而下方的查询中, 与数据范围
Y ∈ [30,40] 部分有交集的查询维度 X 选择度较高, 因此这部分数据按维度 Y 均匀划分, 而 Y ∈ [0,30] 部分数据则按
维度 X 均匀划分.
[3]
尽管都采取了自顶向下的空间划分思路, LA-tree 与现有树形多维索引 (如 KD-tree 和 [1] Qd-tree ) 仍存在显著
区别. 与 KD-tree 相比, LA-tree 在保证数据均匀划分的同时, 通过结合查询负载选择划分维度, 引入了查询感知能力,
从而提高了筛选效果. 如图 2(b) 所示, 查询负载中大部分查询都能被单个或少数个单元覆盖, 且每个单元里在查询
负载范围以外的数据点很少, 令在线查询扫描比较低, 查询用时短. 而按照图 1(a) 中 KD-tree 的划分方式, 每个查询
将扫描较多的单元以及数据. 与 Qd-tree 在高频查询边界处直接切分数据不同, 在每个中间节点, LA-tree 在结合查询
负载选择合适的划分维度后, 按照该维度的数据分布将数据均匀地划分为多个子集, 从而保持全局上的数据平衡.
2.2 LA-tree 的离线索引构建
离线索引构建阶段, LA-tree 采取自顶向下的框架递归划分数据. 具体而言, 在每个中间节点, LA-tree 首先依
据查询负载选择合适的划分维度, 以保证“查询感知”; 随后在该维度上依据数据分布将数据均匀地划分为多个子
集, 以保证“均匀划分”.
形式化地, 本文将该过程建模为一个优化问题: 在给定查询负载 Q 的情况下, LA-tree 需要在每个中间节点选
择合适的划分维度, 从而最小化负载中所有查询在索引上的扫描比之和. 例如, 图 2 中紫色框内的节点划分及对应
的数据子集划分显示: 当 4 个中间节点选择了合适的划分维度时, 查询负载 (绿色矩形框) 中的大多数查询仅与少
量单元相交, 因此查询范围外的数据几乎无需扫描, 查询负载整体的扫描比较低.
解决上述优化问题颇具挑战: 一方面, 即便仅考虑单个节点, 在查询尚未执行之前, 难以直接获知该节点在不
同划分方案下对应的扫描比; 另一方面, 每个节点都可从多个候选维度中自由选择, 使得潜在的数据划分方式呈指
数级增长, 从而显著加剧了问题的复杂性.
针对上述挑战, 本文提出多层次查询感知的数据划分方法. 首先, 针对单节点维度选择中扫描比难以直接获知
的挑战, 构造一个基于扫描比上界的评分函数. 其基本想法是, 在不实际执行查询的前提下, 依据查询负载在候选
维度划分后需扫描的子节点所覆盖的数据量, 对各维度进行估计, 从而高效确定单节点的划分维度. 其次, 面向多
节点联合划分维度选择, 将问题归约为集合覆盖问题. 由于该问题属于 NP 难问题, 因此提出分段式多级搜索贪心
算法: 按深度将树划分为若干段 (每段含多层节点), 段内对多节点维度组合进行有限枚举面向评分函数优化, 段间
则采取贪心策略, 最终生成整棵树的数据划分. 该方法兼顾了筛选效果优化的同时, 实现高效的离线索引构建. 有
关多层次查询感知的数据划分的详细介绍请参见第 3 节.
2.3 LA-tree 的在线查询处理
在线查询阶段, LA-tree 利用学习模型加速自顶向下的筛选数据. 具体而言, 在中间节点, 预先基于该数据子集
在划分维度上的累积分布函数 (CDF) 训练情况模型, 并利用该模型根据查询范围的边界快速确定需访问的子节
点. 在叶子节点上, 同样对数据排序并训练模型学习其分布, 使索引能够在筛选的最后一步精确缩小候选扫描集的