引用部分均为笔者思考.

1. 引入

1.1 何谓地理空间索引

地理空间索引是在存储空间数据时依据空间对象的位置和形状或空间对象的某种空间关系,按照一定的顺序排列的一种数据结构,介于空间操作算法和空间数据之间.

简单来说,地理空间索引主要的功能是:

• 给定空间范围快速找到空间对象
• 给定空间对象快速定位空间范围

1.2 为何需要空间索引

• 几何数据的特点:
  • 形状不规则,实体间空间关系复杂,存储需求量大
  • 实体间的空间操作计算代价比传统的连接操作复杂,计算量大

即:没有索引不行

• 传统索引技术面对空间数据的不足:
  • 传统的索引技术面向的是一维/良序的数据
  • 空间数据顺序难以确定,且一般为多维,无法使用这些传统的索引技术

2. 空间索引的分类

空间索引没有银弹,分类的目的是为寻找特定场景下更加合适的索引方式.

2.1 按搜索对象分类

按搜索对象分类的原因是明确使用场景为特定形态的地物

可分为:

• 基于点区域划分:
  • KD树
  • B树
  • KDB树
  • 点四叉树
• 基于面区域划分:
  • 区域四叉树
  • R树家族
  • 格网索引机制
• 基于三维体区域划分(他们大多数都停留在学术或专业领域):
  • Morton编码
  • 无边界QU码
  • 球面QTM编码
  • 球面HSDS编码

2.2 按空间分割法分类

空间分割法包含两个子分类:

• 对象分割
• 空间分割

它们的区别在于:对象分割法更关心对象,在游戏领域比较常见.空间分割法更关心空间与对象的关系,而在现实生活中,地物与地物往往不是直接产生关系,而是通过空间间接的关联在一起,所以在GIS系统中较为常用.

2.2.1 对象分割

对象分割法一般由层次包围体实现.常见的五种包围体为:

名称	描述	优点	缺点
包围球	最简单的包围体	便于计算,易于做重叠检测和节点修改	逼近程度较差
轴向包围盒(AABB)	长方体的包围体,各轴方向与坐标轴一致	易于做重叠测试	逼近程度较差
方向包围盒(OBB)	任意方向的长方体包围体	逼近程度较高,更新效率较高	-
离散方向多面体(k-DOP)	凸多面体,面由一系列半空间决定.这些半空间的外法向是从k个固定的方向中选取的.AABB就相当于一个6-DOP.	与包围球和AABB相比逼近程度更高.与OBB相比重叠测试和修改成本较低	-
凸包	最精确的外包围体	逼近程度最高	修改和重叠检测成本很高

• 层次包围体算法查询高效,算法成熟,但实现较为复杂.

2.2.2 规则分割

规则分割法是将地理空间按照某种规则或半规则的方式进行分隔,分割单元间接的与空间要素关联,空间要素可能被分割到相邻的单元,这时候空间要素的描述要保持完整,空间索引单元只存储空间要素地址的参考信息.

常见的分隔法:

• 规则格网
• 四叉树/八叉树
• KD树
• BSP树
• R树

2.3 按技术分类

按技术分类基于是用途更加细分的分类法,可能为了避免某种不足或者是为了达到某种性能需求.

空间索引技术大致可分为四大类(还有其他不构成大类的小类不再详述):

• 基于二叉树的空间索引技术
• 基于R树的空间索引技术
• 基于哈希格网的空间索引技术
• 基于空间填充曲线的空间索引技术

2.3.1 基于二叉树的空间索引技术

索引名称	优点	缺点
KD树	存储需求较低,查询高效	无法管理海量数据,更新较麻烦
KDB树	动态索引,高效查询	删除算法效率较低,浪费空间

特点:

• 实现简单
• 一般仅适用于点数据

2.3.2 基于R树的空间索引技术

R树是B树在多维空间的扩展,具有B树的特点:

• 自动平衡
• 空间效率高
• 适合外存存储
  • 节点大小是磁盘页大小的整数倍,适合以磁盘页为传输单位的数据处理
• 查询效率高

特点:

• 适合空间对象,并适合扩充到高纬度
• 区域重叠度改善,效率改善
• 算法较为复杂,动态维护性较差

2.3.3 基于哈希格网的空间索引

基本思路:

1. 将索引空间划分为规则的小方格
2. 与每个格网相关联的空间目标存储在同一个磁盘页
3. 可以通过数组下标的方式得到格网的访问地址以实现快速的空间目标查找

特点:

• 实现简单

• 当索引目标很大或目标大小不均匀时会产生大量冗余.索引效率不佳

  • 可以通过建立多层索引解决,不过这样也带来了更多的冗余和数据更新的不便

• 非多层索引下单一分辨率

2.3.4 基于空间填充曲线的空间索引

上文中提到的各种三维空间编码就属于这一类.

基本思路:

1. 将索引空间细分为许多均等的网格,并赋予其编号.常见的赋予编号的排序算法有:
   • Z排序
   • 希尔伯特排序
2. 编号可以转换为具有代表意义的数字
3. 多维目标可以转化为一维目标

特点:

• 常用于四叉树索引中
• 查询性能不如R树,但增/删/改效率更高
  • 适用于索引经常变更的场景
• 隐形位置表达
• 换算计算量大
• 数据存储量大