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

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

实验结论 3. LA-tree 多层次查询感知的数据划分方法支持高效的离线索引构建. 其在节点层面采用的轻量化
LM 与 PLM 模型, 不仅保证了索引筛选性能, 同时有效降低了离线构建的时间开销与空间占用.

表 5 索引占用空间大小比较 (MB)

数据集 查询负载 Clustered KD-tree Octree Qd-tree Tsunami LA-tree
Uniform 240 2 640 3 540 292 938 509
Stock
Skew 240 2 640 3 540 164 1 152 524
Uniform 34 358 463 332 234 207
TPC-H Lineitem
Skew 34 358 463 332 80 195
Uniform 65 631 803 631 471 322
DSB Sales Skew 65 631 803 631 380 321
HD 65 631 803 631 471 206

6.4 实验 2: 索引泛化性能及动态场景索引更新评测
本节从多个角度评估 LA-tree 在动态场景下的索引性能与泛化能力, 涵盖 3 类典型情形: 无查询负载、查询
负载偏移以及索引更新.
如表 6 所示, 最优结果用加粗表示. 首先在不使用查询负载的条件下评估 LA-tree 的性能, 即禁用其多层次查
询感知的数据划分方法. 需要注意的是, 由于其他学习型索引无法关闭查询感知特性, 因此此处仅将关闭查询感知
优化的 LA-tree 与传统索引方法进行对比. 结果表明, LA-tree 的基于学习模型的筛选方法依然非常高效, 相比最快
的传统多维索引平均查询用时降低约 62%, 说明在缺乏查询负载时, LA-tree 仍能作为高性能的学习型多维索引使
用. 进一步地, 结合实验 1 中表 2 的结果, 在有查询负载条件下当启用多层次查询感知的数据划分方法后, 完整的 LA-
tree 在相同实验条件下还可减少约 52% 的查询用时. 这一结果表明, LA-tree 在索引构建阶段的“查询感知数据划
分”与在查询阶段的“学习型筛选优化”两方面相辅相成, 共同作用于减少在线查询时间.

表 6 LA-tree 无查询负载训练集情形在线查询平均每条查询用时

数据集 查询负载 Clustered (ms) KD-tree (ms) Octree (ms) LA-tree (ms) 提升 (%)
Uniform 41 456 468 33 20
Stock
Skew 30 419 338 30 0
TPC-H Uniform 178 23 30 18 22
Lineitem Skew 182 24 29 18 25
Uniform 483 313 442 228 27
DSB Sales Skew 429 314 445 221 30
HD 901 128 251 94 27
平均情况 320.6 240.0 286.1 91.7 62

实验结论 4. LA-tree 的多层次查询感知的数据划分方法与学习型筛选方法均能显著降低在线查询用时. 即使
在缺乏查询负载的情况下, LA-tree 依然保持较高的查询效率, 体现出其良好的泛化能力.
查询负载变化令查询范围分布发生变化, 使得利用查询负载训练集优化的学习型索引性能下降. 表 7 比较学
习型索引在查询负载变化情形的泛化性能, 最优结果用加粗表示. 不难看出, 对于在 Uniform 查询负载上离线构建
索引而在线查询负载为 Skew 的查询负载变化场景, LA-tree 总是表现出最快的在线查询平均用时, 且总体性能比
学习型基准方法提升了 54%, 高于之前静态场景提升幅度.

表 7 查询负载变化情形学习型索引泛化性能 (在线查询平均每条用时) 比较

数据集 Qd-tree (ms) Tsunami (ms) LA-tree (ms) 提升 (%)
Stock 103 48 28 42
TPC-H Lineitem 18 31 13 28
DSB Sales 138 1 017 77 44
平均情况 86.3 365.3 39.3 54