Page 327 - 《软件学报》2026年第5期

2206 软件学报 2026 年第 37 卷第 5 期

索实现线性扩展. 2009 年, Beckmann 等人 [22] 提出了一种改进的 R*树结构, 适合在数据库管理系统中运行, 可以保
证仅在单个路径中插入, 为了使特定的数据分布和插入顺序更具鲁棒性, 研究者们重新设计了子树选择和拆分算
法, 实验证明该方法下 R*树的创建速度更快, 处理二维和三维数据查询所需的 I/O 成本平均提高了 30% 以上.
2020 年, Alamri 等人 [23] 提出一种基于单元格的索引结构即 Cell 树, 用于有效地分组和管理室内空间中移动物体
的更新, Cell 树可以有效服务于室内空间查询、邻接查询和基于密度的查询.
1.1.3 基于哈希网格技术的空间索引
基于哈希的网格技术是将整个地理空间划分为网格表示, 然后把划分在相同网格的移动对象存储在同一区域
中, 通过网格坐标计算得到该处的地址, 然后对网格中的对象进行索引. 网格索引的典型代表有 Grid file 以及 R-file
等算法, 更加适用于二维或三维移动对象. 2005 年, Hastings 等人 [24] 对空间区域的哈希技术进行了扩展及优化, 针
对空间哈希的碰撞检测功能, 研究者们优化模拟了多个方面, 包括移动物体碰撞、物体−地形碰撞、物体和地形渲
染等, 并通过实验给出仿真结果. 2015 年, Ding 等人 [25] 提出了一种基于自适应网格划分策略的遥感图像认证感知
哈希算法, 可以在细粒度级别对信息密集区域进行身份验证. 2020 年, Pâris 等人 [26] 在 Merkle 树的基础上提出了
Merkle 哈希网格, 将传输和存储成本降低了 50%, 且加快了行列间的搜索速度, 能实现快速定位.
1.1.4 基于空间目标排序的空间索引
空间目标排序法是将地理空间划分为网格后, 为每个网格进行唯一性编码, 网格中对象的地址由它本身和与
它相交的网格编码组合形成, 从而将高维空间映射至一维空间. 空间目标排序的典型代表有 location keys、Z-order

等. 2001 年, Kriegel 等人 [27] 提出了一种高效、动态且可扩展的方法来管理数据库系统中的一维间隔序列, 该方法
符合空间填充曲线的概念, 基于关系区间树, 易于嵌入到现代可扩展索引框架中, 并在可用性、并发性和执行性能
方面明显优于线性四叉树. 2014 年, Zhang 等人 [28] 为解决多维树索引结构复杂的问题, 提出了一种基于映射的大
小分离索引方法, 将数据和查询映射到一维空间中, 该方法包括尺寸分离、数据分布转换和高效映射算法, 通过广
泛实验表明, 该方法比以往基于映射的索引查询效率高出两个数量级, 且比 R 树更为有效. 2017 年, Kumar 等人 [29]
提出了一个索引和数据分发框架 M-Grid, 提供高效的数据分发、预警机制以及多维数据查询. 在建立索引阶段,
研究者们使用基于 Hilbert 空间填充曲线的技术, 通过保留数据的局部特点有效地管理键值索引, 实验表明 M-
Grid 的查询效率与基准结构相比实现了 3 个数量级的性能提升.
1.2 学习索引技术
机器学习模型具有学习数据模式并根据趋势预测数据的优势特点, 所以近年来研究者们考虑使用机器学习方
法来解决数据库的热点问题. 2018 年, Kraska 等人 [30] 提出了学习索引 (learned index, LI), 通过递归模型索引 RMI
提高检索效率. RMI 由多个模型构成包括神经网络、线性回归等, 每个模型以键值作为输入, 返回位置信息. 学习
索引使用机器学习模型生成索引预测值, 将查找范围确定在与预测值距离固定的有限范围中. 现有的大量研究中,
研究者们按照所处理数据的维度特点对学习索引进行分类.
1.2.1 一维学习索引
将一维值输入模型并完成训练, 因一维值便于排序, 所以实现便捷且高效. 2019 年, Wu 等人 [31] 提出了二级索
引 Hermit, 它利用隐藏在列中的软函数依赖关系构建了二级索引, 这样的结构有效地提高了与非主键特征相关的
查询操作性能. Hermit 使用分层回归搜索树 (tiered regression search tree, TRS) 挖掘隐藏在数据列之间的依赖关系,
为索引键的访问清除了冗余结构, 同时因为 TRS 是机器学习强化的数据结构, 可以实现数据曲线的快速拟合, 自
适应地动态捕获列数据的相关性和异常值. 2020 年, Kipf 等人 [32] 为解决学习索引构建速度较慢的问题, 介绍了一
种学习索引 RadixSpline, 使得数据可以在单次传递中被构建, 并且在空间占用和查询性能方面具有突出优势, 通
过实验评估表明该结构在各类数据集中均得到较好结果. 同年, Tang 等人 [33] 提出了专为快速查询而设计的并发有
序索引 XIndex, 该索引同样使用学习模型来优化索引效率, 其能够利用细粒度同步和新的两阶段压缩方案有效地
处理并发写入而不影响查询性能, XIndex 还能根据运行时工作负载特征调整其结构以支持动态工作负载. Wang
等人 [34] 则提出了一个并发学习索引 SIndex, 它可以作用于可变长度的字符串键, 解决了学习索引多集中在整数键