空间索引是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。

对一个数据集做“索引”，是为了提高对这个数据集检索的效率。书的”目录“就是这本书内容的”索引“，当我们拿到一本新书，想查看感兴趣内容的时候，我们会先查看目录，确定感兴趣的内容会在哪些页里，直接翻到那些页，就OK了，而不是从第一章节开始翻，一个字一个字地找我们感兴趣的内容，直到找到为止，这种检索内容的效率也太低了，如果一本书没有目录，可以想象有多么不方便…指可空间在索引查找中的重要性 可见书的目录有多重要 索引有多重要啊！

作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。

常见空间索引类型有BSP树、K－D－B树、R树、R+树和CELL树，空间索引的性能的优越直接影响空间数据库和地理信息系统的整体性能。结构较为简单的格网型空间索引在各GIS软件和系统中（如ArcGIS）都有着广泛的应用。

分形（Fractal）理论，是现代数学的一个新分支。分形几何学是一门以非规则几何形态为研究对象的几何学。通过对分形理论的深入研究，证明了皮亚诺曲线的一些性质，尤其对Hilbert空间填（略），为空间索引的研究提供了必要的理论知识。

空间数据（略）空间信息领域的核心研究内容之一.随着空间信息基础设施建设和空间数据获取技术的快速发展,空间数据规模越来越大，对空间数据共享的要求越来越高，与此同时空间数据仓库、空间数据挖掘等（略）系统性能提出了日益增长的需求。在依赖硬件改善数据库系统性能越来越困难的情况下，以提高空间数据共享能力，增强空间数据的索引效率成为当前研究的热点前沿。

基于分形理论，通过生成Hilbert曲线，将空间数据进行有效合理的划分，并且结合当前空间索引系统中应用广泛的R-树空间（略）成了一种新的空间索引算法及体系，很好地解决了空间索引速度和索引精度问题，（略）分布式海量空间数据的空间索引效率。具体如下：深入研究了分形图形的编码理论，L系统和迭代函数系统绘制分形图形的方法，并给出Hilbert空间填充曲线的生成方案，设计出扫描矩阵算法。

1984年Guttman发表了《R-树：一种空间查询的动态索引结构》

SQL Server 2008的空间索引

SQL Server 2008 引入了对空间数据和空间索引的支持，“空间索引”是一种扩展索引，允许您对空间列编制索引。空间列是包含空间数据类型（如 geometry 或 geography）数据的表列。本节中的主题介绍了空间索引。

在 SQL Server 2008 中，空间索引(存储在:sys.spatial_indexes表中)使用 B 树构建而成，也就是说，这些索引必须按 B 树的线性顺序表示二维空间数据。因此，将数据读入空间索引之前，SQL Server 2008 先实现对空间的分层均匀分解。索引创建过程会将空间分解成一个四级“网格层次结构”。这些级别指的是“第 1 级”（顶级）、“第 2 级”、“第 3 级”和“第 4 级”。

每个后续级别都会进一步分解其上一级，因此上一级别的每个单元都包含下一级别的整个网格。在给定级别上，所有网格沿两个轴都有相同数目的单元 （例如 4x4 或 8x8），并且单元的大小都相同。下图显示了网格层次结构每个级别的右上角单元被分解成 4x4 网格的情况。事实上，所有单元都是以这种方式分解的。因此，以此为例，将一个空间分解成四个级别的 4x4 网格际上会总共产生 65,536 个第四级单元。针对空间索引进行的空间分解与应用程序数据使用的度量单位无关。

网格层次结构的单元是利用多种 Hilbert 空间填充曲线以线性方式编号的。然而，出于演示目的，这里使用的是简单的按行编号，而不是由 Hilbert 曲线实际产生的编号。在下图中，几个表示建筑物的多边形和表示街道的线已经放进了一个 4x4 的 1 级网格中。第 1 级单元的编号为 1 到 16，编号从左上角的单元开始。

沿网格轴的单元数目确定了网格的“密度”：单元数目越大，网格的密度越大。例如，8x8 网格（产生 64 个单元）的密度就大于 4x4 网格（产生 16 个单元）的密度。网格密度是以每个级别为基础定义的。网格配置单元数目低 ：4X4 =16，中8X8 = 64，高16X16 =256，默认设置所有级别都为 中。

您可以通过指定非默认的网格密度控制分解过程。例如，在不同级别指定不同网格密度对于基于索引空间的大小和空间列中的对象来优化索引可能非常有 用。空间索引的网格密度显示在 sys.spatial_index_tessellations 目录视图的 level_1_grid、level_2_grid、level_3_grid 和 level_4_grid 列中。

将索引空间分解成网格层次结构后，空间索引将逐行读取空间列中的数据。读取空间对象（或实例）的数据后，空间索引将为该对象执行“分割过程”。分割过程通过将对象与其接触的网格单元集（“接触单元”）相关联使该对象适合网格层次结构。从网格层次结构的第 1 级开始，分割过程以“广度优先”方式对整个级别进行处理。在可能的情况下，此过程可以连续处理所有四个级别，一次处理一个级别。

研究历程

当前数据搜索的一个关键问题是速度。提高速度的核心技术是空间索引。空间索引是由空间位置到空间对象的映射关系。当前的一些大型数据库都有空间索引能力，像Oracle，DB2。空间索引技术并不单是为了提高显示速度，显示速度仅仅是它所要解决的一个问题。空间索引是为空间搜索提供一种合适的数据结构，以提高搜索速度。空间索引技术的核心是：根据搜索条件，比如一个矩形，迅速找到与该矩形相交的所有空间对象集合。当数据量巨大，矩形框相对于全图很小时，这个集合相对于全图数据集大为缩小，在这个缩小的集合上再处理各种复杂的搜索，效率就会大大提高。所谓空间索引，就是指依据空间实体的位置和形状或空间实体之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空间实体的概要信息如对象的标识、外接矩形及指向空间实体数据的指针。简单的说，就是将空间对象按某种空间关系进行划分，以后对空间对象的存取都基于划分块进行。 1 引言 空间索引是对存储在介质上的数据位置信息的描述，用来提高系统对数据获取的效率。空间索引的提出是由两方面决定的：其一是由于计算机的体系结构将存贮器分为内存、外存 两种，访问这两种存储器一次所花费的时间一般为30~40ns，8~10ms，可以看出两者相差十 万倍以上，尽管有“内存数据库”的说法，但绝大多数数据是存储在外存磁盘上的，如果对磁盘上数据的位置不加以记录和组织，每查询一个数据项就要扫描整个数据文件，这种访问磁盘的代价就会严重影响系统的效率，因此系统的设计者必须将数据在磁盘上的位置加以记录和组织，通过在内存中的一些计算来取代对磁盘漫无目的的访问，才能提高系统的效率，尤其是GIS涉及的是各种海量的复杂数据，索引对于处理的效率是至关重要的。其二是GIS 所表现的地理数据多维性使得传统的B树索引并不适用，因为B树所针对的字符、数字等传统数据类型是在一个良序集之中，即都是在一个维度上，集合中任给两个元素，都可以在这个维度上确定其关系只可能是大于、小于、等于三种，若对多个字段进行索引，必须指定各个字段的优先级形成一个组合字段，而地理数据的多维性，在任何方向上并不存在优先级问题，因此B树并不能对地理数据进行有效的索引，所以需要研究特殊的能适应多维特性的空间索引方式。 1984年Guttman发表了《R树:一种空间查询的动态索引结构》，它是一种高度平衡的树，由中间节点和页节点组成，实际数据对象的最小外接矩形存储在页节点中，中间节点通过聚集其低层节点的外接矩形形成，包含所有这些外接矩形。其后，人们在此基础上针对不同空间运算提出了不同改进，才形成了一个繁荣的索引树族，是流行的空间索引。

R树

R树是B树向多维空间发展的另一种形式，它将空间对象按范围划分，每个结点都对应一个区域和一个磁盘页，非叶结点的磁盘页中存储其所有子结点的区域范围，非叶结点的所有子结点的区域都落在它的区域范围之内；叶结点的磁盘页中存储其区域范围之内的所有空间对象的外接矩形。每个结点所能拥有的子结点数目有上、下限，下限保证对磁盘空间的有效利用，上限保证每个结点对应一个磁盘页，当插入新的结点导致某结点要求的空间大于一个磁盘页时，该结点一分为二。R树是一种动态索引结构，即：它的查询可与插入或删除同时进行，而且不需要定期地对树结构进行重新组织。

1 R-Tree数据结构

R-Tree是一种空间索引数据结构，下面做简要介绍：

（1）R-Tree是n 叉树，n称为R-Tree的扇（fan）。

（2）每个结点对应一个矩形。

（3）叶子结点上包含了小于等于n 的对象，其对应的矩为所有对象的外包矩形。

（4）非叶结点的矩形为所有子结点矩形的外包矩形。

R-Tree的定义很宽泛，同一套数据构造R-Tree，不同方可以得到差别很大的结构。什么样的结构比较优呢？有两标准：

（1）位置上相邻的结点尽量在树中聚集为一个父结点。

（2）同一层中各兄弟结点相交部分比例尽量小。

R树是一种用于处理多维数据的数据结构，用来访问二维或者更高维区域对象组成的空间数据.R树是一棵平衡树。树上有两类结点：叶子结点和非叶子结点。每一个结点由若干个索引项构成。对于叶子结点，索引项形如(Index，Obj_ID)。其中，Index表示包围空间数据对象的最小外接矩形MBR，Obj_ID标识一个空间数据对象。对于一个非叶子结点，它的索引项形如(Index，Child_Pointer)。 Child_Pointer 指向该结点的子结点。Index仍指一个矩形区域，该矩形区域包围了子结点上所有索引项MBR的最小矩形区域。一棵R树的示例如图所示：

2 R-Tree算法描述

算法描述如下：

对象数为n，扇区大小定为fan。

（1）估计叶结点数k=n/fan。

（2）将所有几何对象按照其矩形外框中心点的x值排序。

（3）将排序后的对象分组，每组大小为 *fan，最后一组可能不满员。

（4）上述每一分组内按照几何对象矩形外框中心点的y值排序。

（5）排序后每一分组内再分组，每组大小为fan。

（6）每一小组成为叶结点，叶子结点数为nn。

（7）N=nn，返回1。

3 R-Tree空间索引算法的研究历程

1 R-Tree

多维索引技术的历史可以追溯到20世纪70年代中期。就在那个时候，诸如Cell算法、四叉树和k-d树等各种索引技术纷纷问世，但它们的效果都不尽人意。

R+树

在Guttman的工作的基础上，许多R树的变种被开发出来， Sellis等提出了R+树，R+树与R树类似，主要区别在于R+树中兄弟结点对应的空间区域无重叠，这样划分空间消除了R树因允许结点间的重叠而产生的“死区域”（一个结点内不含本结点数据的空白区域），减少了无效查询数，从而大大提高空间索引的效率，但对于插入、删除空间对象的操作，则由于操作要保证空间区域无重叠而效率降低。同时R+树对跨区域的空间物体的数据的存储是有冗余的，而且随着数据库中数据的增多，冗余信息会不断增长。Greene也提出了他的R树的变种。

R*树

在1990年，Beckman和Kriegel提出了最佳动态R树的变种——R*树。R*树和R树一样允许矩形的重叠，但在构造算法R*树不仅考虑了索引空间的“面积”，而且还考虑了索引空间的重叠。该方法对结点的插入、分裂算法进行了改进，并采用“强制重新插入”的方法使树的结构得到优化。但R*树算法仍然不能有效地降低空间的重叠程度，尤其是在数据量较大、空间维数增加时表现的更为明显。R*树无法处理维数高于20的情况。

QR树

QR树利用四叉树将空间划分成一些子空间，在各子空间内使用许多R树索引，从而改良索引空间的重叠。QR树结合了四叉树与R树的优势，是二者的综合应用。实验证明：与R树相比，QR树以略大（有时甚至略小）的空间开销代价，换取了更高的性能，且索引目标数越多，QR树的整体性能越好。

SS树

SS树对R*树进行了改进，通过以下措施提高了最邻近查询的性能：用最小边界圆代替最小边界矩形表示区域的形状，增强了最邻近查询的性能，减少将近一半存储空间；SS树改进了R*树的强制重插机制。当维数增加到5是，R树及其变种中的边界矩形的重叠将达到90%，因此在高维情况（≥5）下，其性能将变的很差，甚至不如顺序扫描。

X树

X树是线性数组和层状的R树的杂合体，通过引入超级结点，大大地减少了最小边界矩形之间的重叠，提高了查询效率。X树用边界圆进行索引，边界矩形的直径（对角线）比边界圆大，SS树将点分到小直径区域。由于区域的直径对最邻近查询性能的影响较大，因此SS树的最邻近查询性能优于R*树；边界矩形的平均容积比边界圆小，R*树将点分到小容积区域；由于大的容积会产生较多的覆盖，因此边界矩形在容积方面要优于边界圆。SR树既采用了最小边界圆（MBS），也采用了最小边界矩形（MBR），相对于SS树，减小了区域的面积，提高了区域之间的分离性，相对于R*树，提高了邻近查询的性能。