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

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

优化的树形数据划分与学习模型结合的高效筛选机制, 使其在高维查询场景中表现尤为突出.
实验结论 1. LA-tree 在多维索引方法中表现出最佳的查询性能, 并且在高维场景下优势更加显著. 其原因在
于: 一方面, 优化的树形结构实现了更有效的数据划分; 另一方面, 学习模型显著加速了数据筛选.
结合图 6 和图 7 可以看出, LA-tree 在绝大多数测试中的扫描比和平均访问单元数量均为最小, 说明其在线查
询在筛选和扫描阶段的耗时均接近最低, 与其在平均查询时间上的实验结果相一致. 值得注意的是, 扫描比与平均
访问单元数量存在权衡关系, 而 LA-tree 能在保持平均访问单元数量普遍比其他多维索引低 1–2 个数量级的前提
下, 依然实现最佳的扫描比, 尤其在高维数据集 DSB Sales 上优势更加明显. 结合表 3 中展示的各多维索引查询用
时中筛选用时的比重, 可以看出 LA-tree 筛选方法效率相比现有方法大幅度提高, 同时结合其极低扫描比, 说明
LA-tree 查询感知的均匀划分同时取得很好的筛选效果.

表 3 多维索引在线查询筛选用时平均占比 (%)

数据集 查询负载 KD-tree Octree Qd-tree Tsunami LA-tree
Uniform 44.1 39.7 20.9 39.3 3.2
Stock
Skew 47.5 44.1 9.4 44.3 3.8
Uniform 43.5 40.0 47.4 38.7 16.7
TPC-H Lineitem
Skew 45.8 41.4 47.1 5.3 16.7
Uniform 48.9 42.5 49.3 55.2 7.0
DSB Sales Skew 48.7 42.7 50.0 57.6 6.8
HD 42.2 38.2 48.0 55.1 2.4
平均情况 45.8 41.2 38.9 42.2 8.1

在学习型方法中, Qd-tree 表现相对较好, 但在 DSB Sales 数据集的高维查询负载下, 其扫描比较其他查询负载
增加近 3.5 倍, 平均访问单元数量也显著上升. 这是因为高维查询导致查询边界数量激增, 非均匀划分放大了扫描
比的劣势. Tsunami 整体优于传统方法, 但在 DSB Sales 上平均访问单元数量和扫描比均大幅增加, 与其在该数据
集上较高的查询延迟相一致. 这反映出网格结构在高维数据分布下难以兼顾访问单元数量与扫描比调优的瓶颈,
本质原因在于网格难以拟合高维相关性, 尤其在稀疏分布中问题更加突出.

Clustered
KD-tree 436.77
Octree
Qd-tree 158.23
Tsunami
LA-tree 100.23 65.90 128.16 98.60
73.25 80.32 66.69 77.34
10 2 56.93
39.55 43.63 44.22
扫描比 12.90 14.58 13.36 12.64 14.32 10.80 13.36 20.80 35.64

10 1 7.96 8.06 9.06 10.80
4.42 4.47
2.57 4.25 2.55 2.52 2.69

1.19 1.56 1.19 1.10 1.07 1.59 1.07 1.04
10 0
Stock Stock TPC-H Lineitem TPC-H Lineitem DSB Sales DSB Sales DSB Sales
Uniform Skew Uniform Skew Uniform Skew HD
图 6 各索引在线查询平均扫描比对比

在传统方法中, Clustered 作为单维索引不涉及单元划分, 其在 Stock 数据集上的扫描比较低, 与其较短的查询
时间相符. 但在其他数据集上, 扫描比显著高于多维索引, 进一步验证了多维索引的有效性. KD-tree 和 Octree 在