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

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

扫描比和访问单元数量上均明显优于 Clustered, 但仍不及学习型方法, 说明学习型多维索引在筛选性能上的优势.
二者中 KD-tree 因节点功能更简洁、算法开销更低, 相比 Octree 具有更好的查询性能. 需要注意的是, 快速在线查
询依赖于筛选和扫描两个阶段同时具备较低开销, 单一指标的优势不足以显著提升整体性能. 例如, Tsunami 在
Stock 数据集的 Skew 查询负载下实现了与 LA-tree 相当的极低扫描比, 又在 TPC-H Lineitem 数据集的 Skew 查询
负载下实现了最小的平均访问单元数量, 但由于另一指标表现明显不足, 其在线查询平均用时依然较长. 实验中
Tsunami 按照其论文提出的代价函数搜索超参数, 该函数目标最小化查询负载在筛选和扫描阶段的总耗时. 在
Skew 负载上, 受查询范围位置分布较为倾斜, 宽度分布方差较大, 可能出现牺牲扫描比但大幅减少划分格子数量
提高整体在线查询性能的情况. 这里 Tsunami 在线查询性能不够好的原因主要在于网格难以拟合多维相关性.

KD-tree Tsunami
Octree LA-tree 9.6×10 6 1.1×10 7 8.9×10 6
10 7 Qd-tree
1.4×10 6 1.3×10 6 1.5×10 6 1.3×10 6 1.8×10 6 1.8×10 6 1.8×10 6 1.8×10 6
10 6 2.2×10 5 2.2×10 5 8.2×10 4 1.5×10 5 3.9×10 5 3.6×10 5 4.7×10 5 5.5×10 5 4.7×10 5
平均访问单元数量 10 5 4 2.4×10 4 7.3×10 3 6.4×10 4 3.7×10 4 8.9×10 3 6.0×10 4 7.8×10 4 3.4×10 4 8.9×10 3 2.7×10 4 2.7×10 4 1.5×10 4

10

10 3
1.0×10 2 1.3×10 2
10 2 65

Stock Stock TPC-H Lineitem TPC-H Lineitem DSB Sales DSB Sales DSB Sales
Uniform Skew Uniform Skew Uniform Skew HD
图 7 各多维索引在线查询平均访问单元数量对比

实验结论 2. LA-tree 的多层次查询感知的数据划分方法显著优于现有索引方案. 通过在树形结构中同时兼顾
“均匀划分”与“查询感知”, LA-tree 在多维范围查询中展现出更强的筛选能力, 能够有效降低扫描比. 特别是在高
维场景下, 其优势更加凸显.
表 4 和表 5 展示了索引在离线构建的用时与空间开销, 最优结果用加粗表示. 学习型索引整体上离线构建耗
时较高, 传统多维索引与学习型网格索引 Tsunami 在数据量较大的 Stock 数据集上空间开销急剧膨胀, 显示出较
差的可扩展性. 除单维索引 Clustered 外, 其余多维索引均存在较大的空间占用, 但整体仍处于数据库系统可接受
范围.

表 4 索引离线构建用时比较 (s)

数据集 查询负载 Clustered KD-tree Octree Qd-tree Tsunami LA-tree
Uniform 2 33 35 199 236 191
Stock
Skew 2 33 35 168 234 184
Uniform 0.4 4 4 87 206 47
TPC-H Lineitem
Skew 0.4 4 4 81 205 48
Uniform 0.5 7 9 430 546 406
DSB Sales Skew 0.5 7 9 412 545 410
HD 0.5 7 9 296 546 408

相比之下, LA-tree 在离线构建开销上与其余学习型方法处于同一水平, 且空间占用保持稳定并相对轻量. 这
表明 LA-tree 在保证高效查询性能的同时, 能够在离线构建和空间开销两个方面兼顾可扩展性与实用性.