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

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

孩子代替分位值比较, 消除了 B 树中间节点上的数值比较操作, 有效加快 B 树索引的在线查询效率. Galakatos 等
人 [20] 使用分段式线性回归模型 (PLM) 进一步优化了 RMI 的叶子节点, 提高了属性值到数据条目的映射效率.
Kipf 等人 [21] 直接使用回归模型拟合属性值的积累分布, 一次映射筛选与扫描替代了树结构的多层映射筛选, 大幅
提升在线查询效率, 但索引更新性能下降. Ding 等人 [22] 使用神经网络 (neural network) 代替 RMI 节点上的线性回
归模型, 降低映射误差提高筛选效果, 并在此重新设计了节点分裂算法提高数据更新操作的效率. 学习型单维索引
对多维属性范围/等值查询提升非常有限, 但是其基于学习模型的思想对后续研究有重要启发.
● 传统多维索引. 对于多维查询, 单维索引因为仅能筛选一个属性的值从而在线查询效率低, 学界和业界提出
了多种多维索引结构, 同时按多个属性上的谓词约束条件筛选数据. 其中, 二级索引 [23] 先后筛选两个不同的属性
[24]
维度. 四叉树 (quadtree) 是一棵二维平面划分树, 递归地将平面中的区域按二维坐标轴四象限方向划分为 4 个子
[2]
区域. 八叉树 (Octree) 是一棵三维空间划分树, 递归地将空间中的区域按三维坐标轴八方向划分为 4 个子区域.
这些结构的共同特点是只能对较少数量的属性做索引, 使用场景局限, 且效率较低. Z-value [25] 是一种曲线映射方
法, 将二维空间的每个位置降维映射到同一根曲线上的点, 也可拓展到更多维, 缺点是计算量过大且对每个属性值
本身的有序性造成部分丢失. R 树 (R-tree) [26,27] 的核心思想是将空间对象按最小包围矩形 (MBR) 分层组织, 主要用
于二维地图的索引, 也可拓展至多维的数据, 但是当维度增加和值域增加时, 树的空间消耗和在线查询用时都大幅
[1]
增长. KD 树 (KD-tree) 是一棵二叉划分树, 按多个维度轮流均匀划分空间, 树节点过多和划分不够精细都会导致
[6]
在线查询用时长, 而这两点问题难以兼顾优化. 网格 (grid) 按每个维度独立划分空间, 把数据映射到超立方体网
格单元, 关键问题是忽视了不同属性之间的相关性, 对数据划分不合理导致索引效率低, 尤其不适用具有稀疏性的
高维空间. 总体来说, 传统多维索引数据结构, 除了具有单维索引本身的问题, 还有多维空间映射或划分效率低的
问题. 这些导致传统多维索引低效的问题, 是学习型多维索引所要解决的主要挑战.
● 学习型多维索引. 第 1 类是地图查询索引. Wang 等人 [28] 在 Z-value 二维空间降维的基础上, 结合 RMI 的思
路, 利用学习模型提升了查询性能. Qi 等人 [29] 提出 RSMI 模型, 构建了多层网络结构, 每一层都用 Z-value 方法排
序数据条目, 进一步提升了查询性能. 王小丽等人 [30] 提出 ZFT INDEX 模型, 在 Z-value 基础上使用 PLM 模型提升
查询性能.
第 2 类是范围/等值查询索引. Yang 等人 [3] 在数据库分片 (database cracking) [31] 的基础上提出 Qd-tree, 不考虑
数据分布, 选择高频查询边界划分数据, 减少在线查询时额外扫描的单元, 由于不能均匀划分, 部分仍然需扫描大
量数据, 性能较差. Nathan 等人 [4] 基于网格数据结构提出 Flood, 在每个维度上独立划分数据, 用 LM 模型拟合多维
数据分布, 并面向查询负载调整各维度划分密度, 降低多维索引在线查询的扫描量, 但只适用于各维度分布独立的
数据和各查询谓词范围比较一致的查询负载. Ding 等人 [5] 引入网格树 (Grid-Tree) 根据查询负载划分数据, 实现分
治, 并利用条件累积分布 (CCDF) 拟合二维相关性, 提出 Flood 的优化算法 Tsunami, 兼具网格和树的特点, 但无法
解决网格结构难以拟合多维相关性的弊端. Davitkova 等人 [32] 提出 ML-index, 将多维数据聚类成多个不相交超球
体再降至单维处理, 并利用学习型单维索引, 适用于较低维度的多维范围查询. Gao 等人 [33] 提出学习型单调空间填
充曲线多维索引 LMSFC, 先使用学习型参数化可变 Z-order 曲线将多维数据降维到一维, 再进行分页优化和页内
排序进一步提高数据筛选效果. Pai 等人 [34] 提出 WaZI, 在 Z-index 基础上提出查询负载感知的学习型多维索引, 先
执行自适应分区令划分位置对齐高频查询边界, 再使用 Z-order 曲线进行分区内排序. 这两种方法都基于曲线降维
法, 适用于低维情形, 难以拓展到较高维度的数据上. Li 等人 [35] 提出 LISA, 先使用网格划分多维数据, 再将各网格
单元内数据通过映射函数降维至一维, 然后再使用回归模型分片和维护数据, 由于网格和映射函数都难以处理高
维情形, 故该索引适用于低维查询.
比较两类学习型多维索引. 第 1 类解决二维地图上的查询, 缺点是各维度的局部单调性有一定损失, 且空间曲
线拓展到更高维度计算量很大, 因此不适用于多维属性范围查询, 作为早期学习型多维索引, 其开启了后续进一步
研究. 第 2 类适用于典型的多维数据上的多维属性范围/等值查询, 并在 TPC-H Lineitem [28] 等属性维度在 5 左右的
数据集上测试性能, 挑战在于查询性能的进一步提升, 尤其在更高维度的数据上.