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

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

1. if C N k = ∅ then
t
2. Insert/delete/update data tuple t after locating with PLM on dimension
a N k
3. else
4. c ← Choose the child node by t a N k with LM on dimension a N k , refine by ±eb
5. latree-incremental-data-update( N C N k ,c t , )
6. end if
7. return
● 数据更新对索引影响. 在 LA-tree 对数据的划分不发生改变之前, 上述增量更新过程不会影响任何节点上机
器学习模型的 error-bound. 由公式 (12) 和公式 (13) 可以保证, 新数据总会被更新到各节点正确的分位点之间, 即
最终更新到正确的单元. 这种情况下, 任何范围包含新数据的查询, 不会发生结果遗漏. 然而, 随着数据更新的累
积, 数据分布的变化将使得部分区域数据量明显超过平均水平, 即 LA-tree “均匀划分”的特性不再保持. 这会导致
范围与该区域有交集的查询扫描量升高, 查询用时变长.
● 查询负载变化对索引影响. 随查询负载的变化, 查询范围分布将发生变化, 部分节点的维度和分位点可能被
查询范围完全包含, 从而失去筛选数据的效果. 这同样会导致查询扫描量升高, 查询用时变长.
综上, 更新的关键影响在于检查查询扫描量的变化. 随着数据更新与查询负载变化的累积, 原有 LA-tree 索引
的划分模式可能不再适应于当前的数据分布和查询负载, 导致在线查询扫描比上升, 查询耗时增加, 因而需要对
LA-tree 的划分模式重新调整.
● 自适应更新. 利用动态扫描量自适应判断 LA-tree 索引的哪些节点需要重构以调整数据划分, 该方法既不按
照数据分布的变化判断, 也不按照查询负载的变化判断, 而是当局部索引的性能真正受到两者共同变化的影响, 体
现在节点的评分函数受新查询较高的扫描比影响, 增大幅度超过阈值, 即性能明显劣化, 判断以该节点为根的子树
需要重构以重新拟合新的数据分布与查询负载. 如图 5, 若干新查询执行过程中, 参与筛选的节点在自底向上结果
合并时, 以子节点返回的查询扫描比快速更新节点评分函数. 在这一过程中, 如检测到评分函数大幅增大, 如图 5
中红框内的节点, 则标记该相应子树需重构, 并在本次查询结束后执行.

新查询 X OPRS=0.23
··· OPRS'=0.26
q': SELECT* FROM T 17 37
WHERE 3≤X≤35
AND 70≤Y≤75 OPRS=0.35 OPRS=0.10
Y X Y
OPRS'=0.32 OPRS'=0.12
30 61
X Y X OPRS=0.2 Y 子树重构
OPRS'=0.3
6 11 33 38 12 15 75 87
Y Y X X X Y X Y Y Y Y Y
图 5 LA-tree 自适应更新子树重构

算法 4 展示了自适应重构的框架, 检查出满足上述条件的节点, 并对相应子树调用离线构建算法 2 重构子树.
如此, 所有需要重构的子树全部重新优化了性能, 此外没有任何多余的调整操作.
算法 4. LA-tree 自适应索引子树重构: latree-adaptive-reconstruction( N 1 q).
,
输入: LA-tree 根节点 N 1 , 在线查询 q;
输出: 更新后的 LA-tree 索引根节点 N .
′
1
1. N ← latree-adaptive-check( N 1 q) //需更新节点集合
,
′