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

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

X
⩽ CDF(T = v) (12)
M T X(lb)−eb M T X ⩽ M T X(v)−eb M T X
X
同理, 对于 ∀v ∈ T , 若在线查询 [lb,ub] 满足 ub ⩾ v, 必有:

X
CDF(T = v) ⩽ M T X(v)+eb M T X ⩽ M T X(ub)+eb M T X (13)
证毕. 公式 (12) 和公式 (13) 证明了公式 向
(11) 将学习模型估计的两端位置按训练阶段确定的误差界限
eb M T X
外扩张, 索引不会遗漏任何查询范围内的数据. 即对于任何保序的学习模型, 学习型索引 I T 都能在误差界限范围
内保证准确性.
● 高效性分析. 图 4(a) 以基于 LM 的学习型单维索引为背景, 展示了线性回归模型拟合数据分布并根据约束
O(n) 的时间快速训练 LM 即完成索引的离线构建. 在线回答过
范围检索数据的基本原理. 离线训练过程中, 仅需
程中, O(1) 时间确定范围比传统方法 O(logn) 明显更加高效. 本例中, 传统方法需两次二分或平衡树查找分别确定
该查询内数据条目的范围, 共计约 6–8 次数值比较操作. 而此学习型索引训练得到的 LM 满足 error-bound 仅 0.12,
在回答该查询时, 仅需约 2–3 次数值比较操作, 大幅度降低了在线查询用时. 随数据量增大, 二分所需数值比较次
数呈对数级增长, 而 LM 的误差通常仍维持在常数范围内, 即数值比较次数几乎不变. 进一步地, 对于数据量较大
且分布倾斜的情形, LM 误差将增大. 对此, 可使用分段式线性回归模型 (PLM) 拟合 CDF, 模型输入输出与 LM 一
致, 将误差控制在常量范围内. PLM 的正确性支撑类似函数微分原理, 在局部线性化近似函数曲线. 在 PLM 中, 排
序后的数据将被分为若干连续的小区间, 由一个总体 LM 定位区间, 而每个小区间内再由一个 LM 拟合局部 CDF,
且保证任意小区间内 LM 的 error-bound 不超过设定的限制, 时间复杂度为 O(1).

q: SELECT* FROM T CDF(X)
WHERE 7≤X≤10
AND 45≤Y≤82;
17 37
CDF(Y)
X Y

离线 30 61
数据表T 训练 LM模型
X Y CDF(X)
id 1 2 3 4 5 6 7 8 9 10
X 1 2 4 7 12 13 14 15 17 19
6 11 33 38 12 15
扫描筛选出的数据条目
CDF(X)
0.37−0.12≤CDF(X)≤0.87+0.12 范围约束 6≤X≤16; Y Y X X X Y Y Y
转化为CDF(X)
(a) 线性回归模型拟合累积分布函数 (b) LA-tree基于学习模型的高效在线筛选方法
图 4 线性回归模型拟合数据积累分布函数

● 基于学习模型的高效在线筛选方法. 如图 4(b), 总体上, 该方法首先在 LA-tree 树形索引结构中自顶向下地
筛选出数据范围与查询范围有交集的所有节点, 直到叶子节点确定需要进一步筛选和扫描的所有单元, 通过扫描
得出查询结果子集. 最后, 该方法自底向上地合并各子树上的查询结果子集, 得到完整的查询结果.
b 通常较小, 因而中间节点对 error-bound 不敏感.
对于每个具体的节点 N k , 若 N k 是一中间节点, 由于分叉数
自顶向下筛选时, 通过拟合 CDF(T a N k ) 的 LM 模型, 对查询 q 的谓词在节点维度 a N k 上的范围 ], 用模型
N k [lb q,a N k ,ub q,a N k
估算其两端点在数据子集 关于 的投影 T a N k 中的有序位置, 再将估算结果向两端分别扩张 的宽度以
T N k a N k eb M a N k
N k
T
N k
保证数据筛选没有遗漏. 这样, 可以得到 [lb q,a N k ,ub q,a N k ] 包含的节点内的分位点, 对应了与查询范围相交的、数据子
集 按维度 进一步划分的所有子集. 计算完成后, 即可获得明确的需要访问以进一步细化筛选的所有子节点.
T N k a N k
当筛选与扫描结束, 自底向上合并查询结果时, 再在节点 N k 上求这些被访问的子节点返回的查询结果子集的并
集, 作为节点 N k 返回的查询结果子集. 结合公式 (2) 和公式 (11), 经上述流程, 节点 N k 的查询结果子集为:

∪
(q) = (q) (14)
c I T N C N k ,c
I T N k
M a N k (lb q 0 ,a N k )−eb M a N k ⩽ b ⩽M a N k (ub q 0 ,a N k )+eb M a N k
T T T T
N k N k
N k N k