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

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

9 总结与展望

本文提出一种查询感知的自适应学习型多维索引 LA-tree, 设计学习型空间划分多叉树结构, 数据划分同时满
足均匀划分和查询感知, 并实现高效索引更新. LA-tree 具有 3 个关键技术点: 第一, 针对索引离线构建中数据划分
的挑战, 提出多层次查询感知的数据划分方法, 设计的评分函数和多级搜索贪心算法分别解决了扫描比估计和全
树节点维度选择的难题, 在多项式时间得出较优解, 数据划分优化效果好且索引离线构建效率高. 第二, 针对多维
索引数据筛选效果差、大量数值比较增加在线查询用时的问题, 提出基于学习模型的高效在线筛选方法, 通过设
计保序模型误差界限以及线性回归模型与分段线性回归模型混合的学习型空间划分多叉树结构, 分别保证了索引
的准确性和高效性. 第三, 提出自适应增量式的索引更新方法, 以学习型树结构快速定位数据更新实现增量更新,
以快速实时合并新查询扫描比与节点评分函数值实现自适应更新, 保持低在线查询用时. 实验结果表明, 我们的
LA-tree 在多个数据集上在线查询性能均优于现有方法, 特别在高维情形下优势显著. 同时, 还通过纵向对比实验,
验证 LA-tree 索引自适应增量更新方法相比朴素更新方法, 不仅有效保持了低查询用时, 而且更新用时极短.
展望未来, 我们计划进一步优化 LA-tree 的实现. 学习型空间划分多叉树结构具有良好的并行化潜力, 由于子
树之间的独立性, 我们首先可以尝试实现子树级并行的离线索引构建和在线查询子树级并行执行. 在此基础上, 进
一步引入数据库事务中读写锁的机制, 实现多查询并行在线执行以及节点级并行的索引更新, 最终预期有效提高
通用的并行事务的执行性能.

References
[1] Bentley JL. Multidimensional binary search trees used for associative searching. Communications of the ACM, 1975, 18(9): 509–517.
[doi: 10.1145/361002.361007]
[2] Meagher DJR. Octree encoding: A new technique for the representation, manipulation and display of arbitrary 3-D objects by computer.
New York: Rensselaer Polytechnic Institute, Image Processing Laboratory, 1980. https://www.researchgate.net/publication/238720460
[3] Yang ZH, Chandramouli B, Wang C, Gehrke J, Li YN, Minhas UF, Larson PÅ, Kossmann D, Acharya R. Qd-tree: Learning data layouts
for big data analytics. In: Proc. of the 2020 ACM SIGMOD Int’l Conf. on Management of Data. Portland: ACM, 2020. 193–208. [doi: 10.
1145/3318464.3389770]
[4] Nathan V, Ding JL, Alizadeh M, Kraska T. Learning multi-dimensional indexes. In: Proc. of the 2020 ACM SIGMOD Int’l Conf. on
Management of Data. Portland: ACM, 2020. 985–1000. [doi: 10.1145/3318464.3380579]
[5] Ding JL, Nathan V, Alizadeh M, Kraska T. Tsunami: A learned multi-dimensional index for correlated data and skewed workloads. Proc.
of the VLDB Endowment, 2020, 14(2): 74–86. [doi: 10.14778/3425879.3425880]
[6] Nievergelt J, Hinterberger H, Sevcik KC. The grid file: An adaptable, symmetric multikey file structure. ACM Trans. on Database
Systems, 1984, 9(1): 38–71. [doi: 10.1145/348.318586]
[7] Codd EF. Providing OLAP (on-line analytical processing) to user-analysts: An IT mandate. 1993. https://cir.nii.ac.jp/crid/15708541755
48221952
[8] Gray J, Chaudhuri S, Bosworth A, Layman A, Reichart D, Venkatrao M, Pellow F, Pirahesh H. Data cube: A relational aggregation
operator generalizing group-by, cross-tab, and sub-totals. Data Mining and Knowledge Discovery, 1997, 1(1): 29–53. [doi: 10.1023/A:
1009726021843]
[9] Hyafil L, Rivest RL. Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 1976, 5(1): 15–17. [doi:
10.1016/0020-0190(76)90095-8]
[10] Even Hallmark. Daily historical stock prices (1970–2018). 2020. https://www.kaggle.com/ehallmar/daily-historical-stock-prices-1970-
2018
[11] TPC. TPC-H Version 2 and Version 3. 2019. http://www.tpc.org/tpch/
[12] Ding BL, Chaudhuri S, Gehrke J, Narasayya V. DSB: A decision support benchmark for workload-driven and traditional database
systems. Proc. of the VLDB Endowment, 2021, 14(13): 3376–3388. [doi: 10.14778/3484224.3484234]
[13] Zhang JY, Su K, Zhang HC. Making in-memory learned indexes efficient on disk. Proc. of the ACM on Management of Data, 2024, 2(3):
151. [doi: 10.1145/3654954]
[14] Liu QY, Han SY, Qi YL, Peng JS, Li J, Lin LL, Chen L. Why are learned indexes so effective but sometimes ineffective? Proc. of the
VLDB Endowment, 2025, 18(9): 2886–2898. [doi: 10.14778/3746405.3746415]
[15] Guibas LJ, Sedgewick R. A dichromatic framework for balanced trees. In: Proc. of the 19th Annual Symp. on Foundations of Computer
Science. Ann Arbor: IEEE, 1978. 8–21. [doi: 10.1109/SFCS.1978.3]