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

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

3.2 多层节点划分维度选择
LA-tree 具有多层的空间划分多叉树结构, 因此单节点划分维度选择仅能解决 LA-tree 查询感知数据划分的一

个子问题. 现在分析以评分函数 OPRS T,Q,N k (a) 为目标的全树节点划分维度选择问题.
● 全树节点划分维度选择是 NP 难问题. 为方便讨论, 不妨将 LA-tree 看作一棵满多叉树, 且树高为 h+1 (含
叶子节点), 分叉数为 b. 首先, 讨论 N k 为最底层中间节点的情况, 这是一个典型的单节点扫描比优化问题, 故需要
0 1 h−2 h−1 种维度组合, 则最
枚举索引可能的维度组合共计 b |A| 种. 现在, 假设已枚举完成 h−1 层子树, 即枚举了 b |A|
h
上面一层的根节点 N 1 枚举其划分维度 a N 1 ∈ A. 带来整个问题共计枚举 b h−1 |A| 种维度组合. 至此发现多层次节点
划分维度选择是 NP 难问题, 可归约其简化问题 (令 b = 2, 是否存在一棵 LA-tree, 使 Q 在其上总扫描比为 1) 至精
确覆盖问题加以证明, 参考 Hyafil 等人 [9] 研究最小决策树的思路.
结合公式 (5), 注意到任意节点 N k 上, 数据子集 T N k 被不同节点维度 a N k 等分为 b 份, 产生的数据表子集
{ }
c−1 a N k c
T N k ,c = t l | < CDF(T ) ⩽ ,t l ∈ T N k ,c ∈ {1,2,...,b} 有很大差异. 随节点深度增加, 数据子集大小 T N k
b N k = v t l ,a N k b
关于 b 指数级下降, 因而浅层节点维度的选择对整棵 LA-tree 优化效果的影响比深处节点更大, 这意味着对于每个
节点, 其维度选择导致产生不同子问题本身的优化, 比子问题的优化更加重要. 因此, 可将全局优化自顶向下地拆
解为局部优化.

● 多级搜索贪心算法. 将优化分数 (a) 的计算推广到多层节点, 并设置一个参数级数 w, 将高度为 h
OPRS T,Q,N k
的树构造问题按每级高度为 w 分段. 段内搜索: 即每高度 w 的子树, 枚举其中每个节点维度, 以从该子树最后一层
节点自下而上计算的优化比为目标. 段间贪心: 不同段的子树忽略后效性, 在上层段所有节点确定划分维度后, 独
立地搜索下层段各节点划分维度.
分析该算法, 贪心算法本身就可以得到相当优的解, 因为查询负载感知选择维度优化划分数据的过程类似剪
枝, 越浅层节点, 对应越大的数据子集, 对其优化越能提高索引筛选效果. 而多级搜索则进一步考虑了后效性的影
响, 令全树节点维度选择更接近最优解. LA-tree 离线索引构建见算法 1.

算法 1. LA-tree 离线索引构建: latree-offline( T N k , Q N k ht 0 ht).
,
输入: 数据表子集 T N k , 查询负载训练集子集 Q N k , 本级枚举起始高度 ht 0 , 当前高度 ht;
输出: LA-tree 已构建节点 N k .
1. if ht = h then //叶子节点直接决定节点维度构建
2. Choose where has smallest sel on T a
a N k
Q N k
N k
3. N k ← Leaf node on T N k
) 为目标
4. else //中间节点 w 步枚举节点维度, 以最小化 (a N k
OPRS T N k ,Q N k ,N k
5. if ht 0 ⩽ ht then //节点尚未确定, 处于维度选择过程中
6. if ht = ht 0 +w−1 then // N k 是本级 w 层枚举的最后一层
7. Choose with smallest )
a N k
OPRS T N k
,Q N k ,N k (a N k
8. else //本级 w 层枚举的中间层, 每个 a N k 都选择最优子问题以最小化 )
,Q N k ,N k (a N k
OPRS T N k
9. for c from 1 to b do
,
,
10. Choose with smallest ) by latree-offline( T N k ,c Q N k ,c ht 0 ht +1)

a N k
OPRS T N k
,Q N k ,N k (a N k
11. end for
12. end if
13. Try partition T N k and divide Q N k by a N k
14. Try N k ← Middle node on T a N k
N k
15. if ht = ht 0 then //本级枚举完成, 枚举的根节点确定当前构建的子树