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

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

′
I (q)
T
ScanRatio(I T (q)) = (3)
|I T (q)|
显然, 扫描比大于等于 1, 其数值越小, 说明索引筛选效果越好, 即在相同查询条件下需要扫描的数据量越少.
2 自适应学习型多维索引 LA-tree
针对结构化数据多维查询, 本文提出一种查询感知的学习型多维索引 LA-tree. 本节首先介绍 LA-tree 的基本
结构, 随后分别介绍其离线索引构建、在线查询处理和自适应更新问题.
2.1 LA-tree 的基本结构
图 2 为 LA-tree 的基本结构, (a) 为 LA-tree 的基本结构, (b) 为所对应的空间划分情况. 如图 2(a) 所示, LA-tree
[3]
[1]
采用了与 KD-tree 、Qd-tree 类似的树形多维索引结构, 其基本结构是一棵空间划分多叉树. 下面从索引功能, 即
检索查询结果的角度, 对 LA-tree 的基本结构进行形式化描述, 递归定义各节点的索引功能.

q: SELECT* FROM T X
WHERE 7≤X≤10 100
AND 45≤Y≤82; 17 37 T 7 T 8 T 9
q
80
Y X Y
30 61 60
Y
X Y Y T 6
40
T 5
T 4
12 15
6 11 33 38
20
CDF(X)
Y Y X X X Y Y Y
T 1 T 2 T 3 T 4 T 5 T 6 T 8 T 9 T 1 T 2 T 3
0
0 10 20 30 40 50
X
T 7
(a) LA-tree结构 (b) LA-tree数据划分
图 2 LA-tree 总览

形式化地, 在公式 (1) 的基础上, 记 LA-tree 上的任意一节点为 N k , 其对应数据子集为 T N k . 由于每个节点都可
视为一棵 LA-tree 子树的根, 因此其本身可以作为对应数据子集 T N k 上的索引, 查询结果表示为:

{ }
,∀a j ∈ A (4)
(q) = i | lb q,a j ⩽ v t i ,a j ⩽ ub q,a j ,t i ∈ T N k
I T N k
下面根据节点 N k 类型的不同, 即中间节点或叶子节点, 给出更为具体的定义.
● 若 N k 是中间节点, 它将数据按划分维度 a N k 将数据子集 T N k 划分为 b 个等量子集, 并将其对应到 N k 的子节
{ } { }
点 C N k = C N k ,1 ,C N k ,2 ,...,C N k ,b 中, 并产生 b−1 个分位点 U N k = u N k ,1 ,...,u N k ,b−1 . 显然, 任意查询 q 在 N k 上的查询结果
等于其在所有子节点查询结果的并集, 即有:

∪
(q) = (q) (5)
I T N k I T N C N k ,c
>u N k ,c−1
⩽u N k ,c ∧ub q,a N k
lb q,a N k
● 若节点 N k 为叶子节点, 则对应一个单元 (cell), 其中存储若干数据记录. 通过设置叶子节点来终止递归划分,
可以有效控制树的深度, 避免过多的空间开销与性能消耗.
上述从索引查询结果的角度定义了树形索引各节点的功能, 对于树形索引这一对象本身, 我们定义其为包含
{
}
所有节点的集合 I = N 1 ,N 2 ,...,N |I| . 图 2 展示了一个二维数据空间下的 LA-tree 示例 (为简便起见, 本文以 X 和 Y
表示数据的两个属性维度), 其中, 图 2(a) 是 LA-tree 的结构示意图, 其中浅蓝色节点表示图中在线查询 q 筛选数据
时访问的节点; 图 2(b) 则是相应的空间划分结果, 其中蓝色圆形散点表示数据记录, 绿色实线框表示查询负载, 紫
色线段表示空间划分, 绿色的虚线框表示在线查询 q, 浅蓝色阴影覆盖扫描的数据. 其中, 浅蓝色阴影范围小于单