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

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

2. Q ← Q∪{q} //更新查询负载训练集
′ ′
3. for N in N do
c
4. ht ← Height of N ′ c
′
0
,
,
5. N ← latree-offline( T N ′ Q N ′ ht ht )
′
′
′

c c c 0 0
6. end for
7. return N ′
1
算法 5 是自适应子树重构触发. 这是算法 4 高效的关键, 触发方法随在线查询算法 2 同时执行, 实时检查索引
是否需要更新, 并确定需要更新的局部, 在当前查询完毕后执行索引更新, 即自适应索引子树重构算法 4. 我们通
O(1) 的额外时间开销不断更新, 高效且准
过在节点增加一个数值变量维护实时评分函数变化, 在线查询过程中以
确. 在自底向上合并查询结果子集的过程中, 不断地将查询扫描比与所访问节点评分函数做加权平均, 更新节点的
τ, 说明该节点为根的子树不再适应当前的新数据和查询, 将节
评分函数. 当一个节点当前评分函数增高超过阈值
点加入重构节点集合. 同时, 考虑到不同层次数据子集之间的包含性, 当上层节点加入重构节点集合后, 将自动从
集合剔除其所有后代节点, 避免重复构造. 由于越上层的节点覆盖的数据范围越大, 查询数量越多, 从而受新数据
和新查询影响越小. 因此, 算法实际通常只触发少量下层节点重构, 更新耗时少.
算法 5. LA-tree 自适应子树重构触发: latree-adaptive-check( N k q τ).
, ,
输入: LA-tree 节点 N k , 在线查询 , 阈值 τ;
q 0
,
′
输出: 需重构节点集合 N q 0 的真实局部扫描比 sr q 0 .
1. if C N k = ∅ then //叶子节点直接计算扫描比
2. ∅, sr q ← Leaf node not to reconstruct. Scan ratio of q on T N k by PLM on dimension a N k
3. else //中间节点合并子树扫描比, 更新当前 (a N k )
OPRS T N k
,Q N k ,N k
[ ]
4. fchild,tchild ← Filter child nodes by lb q,a N k ,ub q,a N k with LM on dimension a N k , refine by ±eb
5. for c from fchild to tchild
6. N , sr q ← Union and average of latree-adaptive-check( N C N k ,c , q 0 )
′
7. end for
8. Update OPRS ′ ) by merging sr q //中间节点用局部扫描比加权平均更新评分函数值
,N k (a N k
T N k ,Q N k
9. if OPRS ′ ) rises sharply then //本节点及整棵子树需要重构
T N k ,Q N k ,N k (a N k ) > (1+τ)OPRS T N k ,Q N k ,N k (a N k
10. N ← {N k }
′
11. end if
12. end if
′
13. return N , sr q
综上, 算法 3 与算法 4、算法 5 共同组成了高效的 LA-tree 索引自适应增量更新方法.

6 实 验

6.1 实验数据集和查询负载
本文在公开且常用的评测数据集 Stock [10] 与 TPC-H Lineitem [11] 上进行了实验. 为进一步评测多维索引在高维数
据下的性能, 又在较新的基准数据集 DSB Sales [12] 上开展实验. 表 1 总结了各数据集及其对应查询负载的基本情况.
(1) 数据集 Stock 记录了多支股票在多个日期的价格变化. 其特点是数据记录规模大, 部分维度值域较广, 且
数据维度间相关性较强, 适于考察多维索引在大规模数据上的性能表现.