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

王撷阳 等: 基于数据分布的移动对象学习索引及查询算法 2205

1.1 时空数据索引结构
在移动对象数据库中数据访问与查询的频率高, 由于移动对象的动态性, 迅速定位数据位置成为数据库的基
础操作之一, 这对于提升查询操作的总体性能至关重要. 空间索引是移动对象数据库中用于提升查询和存储性能
的数据结构, 是依据移动对象的位置信息或空间关系等特征, 按照一定的顺序存储数据的结构. 通过空间索引可以
快速锁定数据位置范围, 能够有效地提高空间查询操作的效率 [8,9] . 现有的空间索引主要分为以下 4 类.
1.1.1 基于二叉树的空间索引
二叉树是应用最为广泛的树形数据结构之一, 其存储结构及算法都较为简单, 每个树节点最多有两棵子树, 以
左右区分. 在移动对象数据库中, 基于二叉树的索引结构以 KD 树 [10] 为典型代表, KD 树是一种二分索引树结构,
即 K 维的二叉树, 是一种空间划分的数据结构, 其中的每一个节点都是 K 维的数据, 主要功能是对多维数据进行
索引, 常用作空间划分及最近邻查询. 2019 年, Ram 等人 [11] 以随机分区树为基础, 针对高维度移动对象数据集, 提
出了基于 KD 树的近似搜索方案, 克服了 KD 树长期以来不适合用于精确最近邻搜索的难题, 并通过实验验证了
该方案的搜索准确性和查询时间保证. 虽然 KD 树是一种对 K 维空间的移动对象点检索快速的树形数据结构, 但
KD 树针对空间关系的查询效率非常低.
研究者们为了优化 KD 树, 在此基础上做了很多探索. 2018 年, Nurgaliev 等人 [12] 通过在区块链系统中引入加
密签名的树结构, 实现了对时空区块链数据的高效查询处理, 维护了数据存储和完整性, 并通过实验综合评价了所
提方法的通用性和有效性. 此外, 研究者们还提出了 KDB 树, 将 KD 树与 B 树结合的索引结构, 目的是将 KD 树
存储到外存中. 2013 年, Li 等人 [13] 提出一种工作负载自适应的在线算法, 该方法在闪存上实现了 KDB 树, 将树节
点表示为日志集合, 称为日志记录条目, 以有效处理节点的细粒度更新, 提高查询性能. 2017 年, Liu 等人 [14] 提出基
于加密的安全框架以保障空间众包分配时工作人员的安全隐私问题, 为了提高分配效率, 提出了一种基于 SKD 树
的新型安全索引技术, 在集合索引时以查询对象的中心点作为查询键.
1.1.2 R 树及其主要变体
基于 R 树的空间索引最早是由 Guttman [15] 提出的, 是通过普通关系数据库中的 B 树索引改进而来, 适用于多
维空间非零数据对象的动态索引结构. R 树中的每个非叶子节点存放的是数据集空间中的一个矩形和一个指针,
该矩形是包含其所有子节点的最小外包矩形 (minimum bounding rectangle, MBR), 该指针指向的是下一层节点. R
树的叶子节点则存放了指向查询对象位置的指针. 2020 年, Qi 等人 [16] 提出了一种基于空间填充曲线的 R 树堆积
策略, 满足实际和最坏情况下数据的多样访问, 该策略会在最坏情况下为窗口查询生成具有渐近最佳 I/O 复杂度
的 R 树, 实验表明该 R 树在查询不同分布的真实数据和合成数据方面都非常高效.
R 树具有很好的灵活性, 能够保持较高的空间利用率, 允许兄弟节点所对应的空间区域相互重叠, 这就使得 R
树的搜索路径多样化, 导致查询效率降低, 且高频更新导致索引重构开销过大. 为了改进这一不足, 研究者们还陆
续提出了 3DR 树、TB 树、TPR 树、TPR*树、SETI、R+树和 Cell 树等数据结构, 来提高查询效率并节省访问时
间. 1996 年 Theodoridis 等人 [17] 提出的 3DR 树将时间视作第 3 维度, 与空间坐标一同构建三维 MBR, 通过三维分
裂策略最小化体积增量, 既支持实时位置更新, 也天然保留历史轨迹, 但由于三维分裂与批量重构开销较大, 更新
延迟和树膨胀问题仍需通过重建策略加以缓解. 2000 年 Pfoser 等人 [18] 提出一种基于 R 树的空间索引结构 TB 树.
其叶节点将同一轨迹的各个分段组织在一起, 从而支持高效的轨迹检索. 但由于 TB 树在处理空间聚集性较差的
区域时, 可能导致不属于同一轨迹但空间上相近的线段被分散存储在不同的节点中, 从而影响了其空间利用效率
与查询性能. 同年, Šaltinis 等人 [19] 提出的 TPR 树假设移动对象以线性速度运动, 引入速度和时间概念, 其 MBR 会
随着时间推移扩大, 查询时将目标时间代入预测边界进行剪枝, 从而大幅减少因频繁位置变化带来的更新成本, 适
合速度较稳定的在线服务场景, 但对非线性运动的支持有限. 2003 年, Tao 等人 [20] 提出的 TPR*树对 TPR 树进行了
改进, 通过引入更高效的节点分裂策略和边界扩展算法, 有效减少了查询时的重叠区域和更新开销, 从而在对象运
动状态有轻微波动的情形下获得更优的查询性能. 同年, Chakka 等人 [21] 提出的 SETI 索引在分布式环境中以空间
网格与时间分段对时空域进行分片, 在每个分区中的轨迹线段用一个 R 树来索引, 并通过全局目录路由与并行检