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

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

维学习索引做了更细致的优化.
基于空间划分的多维索引仍然保留传统多维索引 (如 R 树 [178] ) 对数据空间的划分方法, 将学习的方法加入递
归索引结构中以增加搜索效率. IF-Index [169] 用一维学习索引的查询替换了现有树结构 (例如 R 树) 中的叶节点查
询过程. IF-Index 的非叶节点遵循普通 R 树构建的构建方法, 但叶节点不仅存储相应的数据页, 还存储模型元数
据. 模型元数据包括用于对数据页中的点进行排序的维度和用于预测数据页上的搜索关键位置的线性插值模型.
RSMI [170] 在叶节点和内部节点中都使用基于神经网络模型进行查询预测. 与 KD 树 [179] 类似, RSMI 先使用压缩填
充曲线对数据进行映射, 然后每层将父节点空间划分为等深单元格, 并训练学习模型将单元格内的数据映射到下
一层的划分. 停止划分的条件是当前节点处理的数据数目小于阈值, 最后 RSMI 训练其叶子模型来预测每个点对
应的块编号. QD-Tree [171] 对特定的数据和查询工作负载进行优化, 利用强化学习对数据进行分区, 以便将特定查询
工作负载访问的块数量降至最低, QD-Tree 的非叶节点都使用特定的查询谓词对数据进行分区, 而叶节点中的数
据则被划分到同一个磁盘块. QD-Tree 的构造过程可以表述为马尔可夫决策过程, 索引的节点集合表示为状态, 动
作空间表示为查询谓词集合, 并使用所有查询中跳过的块数计算奖励. PolyFit [180] 和 LearnedKD [181] 同样是基于空间
划分的学习索引, 它们是将传统的空间索引与学习索引结合的方法, 这两种方法也利用学习模型的优势在经典索
引架构的基础上提升查询效率.
基于网格的多维索引的目标是学习紧凑的多维网格以有效地处理正交的范围查询谓词. Flood [172] 采用通用格
索引作为数据布局. Flood 首先选择排序维度对每个网格单元内的数据排序, 其余维度的数据采用各自维度进行网
格叠加. 不同于通常的网格索引, Flood 使用学习的 CDF 模型 (即 RMI [159] ) 构造网格分区. 为了更快地细化和过滤
查询的范围, 对于每个存储格, 使用排序维度的数据来训练 CDF 模型. Flood 建立了成本模型, 然后使用历史查询
工作负载来选择排序维度并调整其超参数. Flood 还设计了索引增强方法以快速处理范围查询, 首先检索与查询超
矩形相交的格, 然后查询这些格内的 CDF 模型以应用基于范围查询谓词的有效过滤. Tsunami [173] 是对 Flood 的改
进方法, Tsunami 主要在处理数据相关性和应对倾斜查询负载两方面做了针对性改进. Tsunami 由适应倾斜查询工
作负载的格索引和经过优化以捕获数据相关性的增强网格索引两部分组成. 与 Flood 相同 Tsunami 也是基于选定
的维度构建树形索引, Tsunami 将整个多维空间划分为几个不相交的区域, 减少每个区域内历史工作负载的查询
偏差, 然后为每个区域构建增强网格. 增强网格充分考虑了历史工作负载, 对频繁查询的区域进行密集分区.
SPRIG [182] 提出了一个新的多维学习模型, 它是通过采用空间插值和一种新颖的动态编码技术来改进现有的基于
格的方法. COAX [183] 通过学习数据集属性之间的相关性来降低数据集的维度, 从而使索引空间占用更小、查询更
高效.
4.1.2 数据分区
数据分区是一种数据库优化技术, 它将大型数据集按照特定规则划分为多个逻辑或物理子集, 以提高查询性
能、简化数据管理并优化存储资源利用. 现代数据库系统中, 数据分区的标准化流程通常包含 4 个关键阶段:
(1) 分区策略选择, (2) 分区键确定, (3) 分区方案实施, (4) 动态调整与优化.
在存储模型层面, 数据库物理分区设计主要采用行存储 (N-ary storage model, NSM) 和列存储 (decomposed
storage model, DSM) 两种基本方式. 行存储将每一行的数据连续存储, 适合快速整行读写操作; 而列存储将表的每
一列分开存储, 有利于加速数据聚合和分析操作. 这两种存储模型分别针对 OLTP 和 OLAP 系统进行优化, 但随着
混合事务分析处理 (HTAP) 需求的增长, 出现了融合两者的智能分区方法.
(1) 水平分区
水平分区技术按照数据行进行划分, 主要分为 3 类方法: 基于分区函数的确定性方法、基于外键的启发式方
法和基于强化学习的自适应方法. 基于分区函数的方法通过查询谓词将数据元组聚类, 寻找最优分区函数以最小
化总体成本. AdaptDB [184] 提出的方法根据连接频率进行动态分区, 而文献 [185] 开发了细粒度分区技术使查询能
够跳过不相关分区. 这些方法虽然高效, 但在分布式环境中的适应性有限. 基于外键的启发式方法通过分析表间引
用关系提高数据局部性. 文献 [186] 采用代价限制的启发式算法选择分区键, 而 Clay [187] 系统通过监控工作负载动
态识别和扩展“热元组”分区. 这类方法虽然提高了查询性能, 但往往需要承担数据冗余的代价. 基于强化学习的方