高效空间数据索引R树及其批量加载方法STR简介

工作中经常需要跟空间数据打交道，因此频繁使用一个工具类 com.vividsolutions.jts.index.strtree.STRtree 。STRtree类似于一个集合，向其插入一些带空间信息的数据后可以很便利地按范围查询空间数据，如下图示意。

由于不清楚STRtree的查询实现逻辑，为探明原因及避免后续踩坑了解了一下，发现STRtree应用了非常精巧且应用广泛的空间索引结构R树（R-Tree）及优秀的批量加载算法STR。下文我们将从R树开始介绍，进一步了解STR算法，并说明一些STRtree相关的注意事项。

R树是一种层次数据结构，它是B树在k维空间上的自然扩展，因此和B树一样，R树是一种高度平衡树，在叶结点中包含指向实际数据对象的指针。

定义：

简单来说，R树种的每个节点都是一个矩形，而且是节点数据的最小外接矩形（MBR，Minimun Bounding Rectangle），即覆盖内部几何图形的最小矩形边界。

MBR本身通过x、y坐标容易计算，计算MBR相交也十分简单高效，适用于应用在索引结构中。

其中，叶子结点为实际结点空间数据的MBR；非叶子结点则为其所有子节点形成的MBR，即刚好包裹住所有子节点。

从定义中可以看出来，其结构与B树类似：

简单的部分到此为止，R树具体的插入删除规则涉及到复杂的规则，在节点分裂和合并之外还涉及父节点MBR的调整等，详情可参考原论文或 其他资料 。

在不使用R树时，最基础的范围搜索方法是遍历整个数据集，将所有落在范围内的数据返回，在较大数据集中这个代价显然是不可接受的。当然通过网格划分数据集的方式也可以大大缩小候选数据集，但仍需要遍历候选网格的全量数据。

而R树的搜索算法则类似B树，从根节点开始，根据搜索范围找到命中的节点，并不断向下查找到叶子结点，缩小范围，最终返回命中的数据。这非常易于理解：当我们要找到某个商场时，思考路径也是AA市->BB区->CC路->DD路口依次缩小范围。

但R树与B树最显著的区别在于R树在非一维空间使用MBR描述节点的上下界，无法像B树节点一样准确适应子节点的分布。虽然通过通过MBR提高了计算和求交的效率，不过这也势必牺牲了空间利用率（父节点包含了空白区域）及查询效率（兄弟节点MBR可能会重叠）。

在查询时，以下常见的情况会导致需要多路径搜索：

现在我们可以理解，R树中的R表示Rectangle，也表明其本质是一组有层次关系的“矩形”，在一维空间是线结构，在没有重叠的情况下结构很像B树，推广到三维则是长方体。

R树作为一个比较宽泛的结构定义，并未限定具体的构造方式，而基于R树的概念及各种组织方式衍生出了庞大的R树家族，不同组织方式的R树变体性能差距很大。其他比较有特点的一些变体索引结构：

通常从空树开始构建整个R树时，将记录逐个插入直至生成整个树的过程中会频繁触发索引结构的动态维护，这对于海量空间数据的初始化而言耗时巨大，代价过高。由此发展而来的Packing（批量加载）算法则可以在数据已知且相对静态的情况下尽可能提高R树的构建速度并优化索引结构。

其中Leutenegger等提出了一种STR(Sort-Tile-Recursive，递归网格排序) Packing算法，该算法易于实现且适用范围较广，在大多数场景下表现良好，且易于推广到高维空间。

STR算法本质上只是R树的一种构建算法，STR R-Tree本质上仍是R树。

STR可以理解为切蛋糕，首先确定一共应该切成N份，然后从左到右根据蛋糕上草莓个数竖切成sqrt(N)个中份，再从上到下把每个中份横切成sqrt(N)个小份，一趟递归就完成了。下一趟则是将小份蛋糕当作草莓，继续切直到不需要切为止，自下而上递归构成R树。

具体细节可以查看 作者原论文 ，算法介绍不到一页，概念好理解。

STR本身逻辑并不复杂，其排序和网格化的逻辑是与维度无关的，还可以拆分至按维度计算，对算法实现比较友好，构建效率也高；同时，其使用递归和网格化的思路可以较好地将兄弟MBR大致分离，尽可能减少重叠区域，大多数数据分布下查询效率较高。

R-Trees - A Dynamic Index Structure for Spatial Searching

STR: A Simple and Efficient Algorithm for R-Tree Packing

R树家族的演变和发展 - 中国科学院

空间数据索引RTree（R树）完全解析及Java实现 - 佳佳牛 - 博客园

MySQL :: MySQL 5.7 Reference Manual :: 11.4.9 Creating Spatial Indexes

空间数据库的研究始于20世纪70年代的地图制图与遥感图像处理领域。由于传统数据库在空间数据的表示、存储和管理上存在许多问题，从而形成了空间数据库这个多学科交叉的数据库研究领域。空间数据库（Spatial Database）是指地理信息系统在计算机物理存储介质上存储的与应用相关的地理空间数据的总和，一般是以一系列特定结构的文件的形式组织在存储介质之上的（黄杏元等，2001）。

ArcSDE可看成是一个连续的空间数据模型，借助这一模型，就可用关系型数据库（RDBMS）管理空间数据库。在关型数据库中融入空间数据后，通过ArcSDE实现空间、非空间数据高效率操作服务。ArcSDE提供了应用程序接口（API），开发人员可将空间数据检索和分功能集成到自己的应用系统。ArcSDE具有如下一些特点。

1）高性能的DBMS 通道。ArcSDE 是多种DBMS 与应用程序（如ArcGIS）的通道。它本身并非一个关系数据库或数据存储模型。它是一个能在多种DBMS平台上提供高级的、高性能的GIS数据管理的接口。

2）开放的DBMS支持。ArcSDE允许你在多种DBMS中管理地理信息：Oracle、Oracle with Spatial/Locator、Microsoft SQL Server、Informix，以及IBM DB2。

3）支持多用户GeoDatabase。ArcSDE为用户提供大型空间数据库支持，并且支持多用户编辑。

4）连续、可伸缩的数据库。ArcSDE可以支持海量的空间数据库和任意数量的用户，直至DBMS的上限。

5）GIS工作流和长事务处理。GIS中的数据管理工作流，例如多用户编辑、历史数据管理、Check-out/Check-in，以及松散耦合的数据复制等都依赖于长事务处理和版本管理。ArcSDE为DBMS提供了这种支持。

6）丰富的地理信息数据模型。ArcSDE保证了存储于DBMS中的矢量和栅格几何数据的高度完整性。这些数据包括，矢量和栅格几何图形、支持X，Y，Z和X，Y，Z，M的坐标、曲线、立体、多行栅格、拓扑、网络、注记、元数据、空间处理模型、地图、图层，等等。

7）灵活的配置。ArcSDE通道可以让用户在客户端应用程序内或跨网络、跨计算机地对应用服务器进行多种多层结构的配置方案。ArcSDE支持Windows、UNIX、Linux等多种操作系统。

对空间数据的管理职责是由GIS软件和常规DBMS软件所共同承担的。某些空间数据的管理功能，如磁盘存储、属性类型定义、查询处理，以及多用户事务处理等是由DBMS来完成的。而对空间数据索引和搜索功能主要由ArcSDE 负责实现。一般在服务器端有SDE服务器处理程序、关系数据库管理系统和实际的数据。

ArcSDE通过SQL引擎执行空间数据的搜索，将满足条件的数据在服务器端缓冲区中存放并返回到客户端。缓冲区处理收集一批数据，然后将整个缓冲区中的数据发往客户端应用，而不是一次只发一条记录。在服务器端处理并缓冲的方法大大提高了效率，使网上荷载大大降低，这在应用操作数据库中成百上千万的记录时体现其优势。ArcSDE采用协作处理方式，即处理可在SDE客户库或服务器端实现，但取决于处理在哪一端更快。有的功能不需要与服务器通信，像多边形叠加和分割这类主要耗费CPU资源的任务，则由客户库来完成，可避免大量的网上操作。所有的服务器任务都是在SDE服务器所在的平台上完成的。而客户端应用则可运行于多种不同的平台和环境中，去访问同一个SDE服务器和数据库。

【转载】R-Tree空间索引算法的研究历程和最新进展分析2008-07-09 23:15摘要：本文介绍了空间索引的概念、R-Tree数据结构和R-Tree空间索引的算法描述,并从R-Tree索引技术的优缺点对R-Tree的改进结构——变种R-Tree进行了论述.最后,对R-Tree的最新研究进展进行了分析.

关键词：空间索引技术；R-Tree；研究历程；最新进展

当前数据搜索的一个关键问题是速度.提高速度的核心技术是空间索引.空间索引是由空间位置到空间对象的映射关系.当前的一些大型数据库都有空间索引能力,像Oracle,DB2.

空间索引技术并不单是为了提高显示速度,显示速度仅仅是它所要解决的一个问题.空间索引是为空间搜索提供一种合适的数据结构,以提高搜索速度.

空间索引技术的核心是：根据搜索条件,比如一个矩形,迅速找到与该矩形相交的所有空间对象集合.当数据量巨大,矩形框相对于全图很小时,这个集合相对于全图数据集大为缩小,在这个缩小的集合上再处理各种复杂的搜索,效率就会大大提高.

所谓空间索引,就是指依据空间实体的位置和形状或空间实体之间的某种空间关系,按一定顺序排列的一种数据结构,其中包含空间实体的概要信息如对象的标识、外接矩形及指向空间实体数据的指针.简单的说,就是将空间对象按某种空间关系进行划分,以后对空间对象的存取都基于划分块进行.

1 引言

空间索引是对存储在介质上的数据位置信息的描述,用来提高系统对数据获取的效率.空间索引的提出是由两方面决定的：其一是由于计算机的体系结构将存贮器分为内存、外存 两种,访问这两种存储器一次所花费的时间一般为30~40ns,8~10ms,可以看出两者相差十 万倍以上,尽管现在有“内存数据库”的说法,但绝大多数数据是存储在外存磁盘上的,如果对磁盘上数据的位置不加以记录和组织,每查询一个数据项就要扫描整个数据文件,这种访问磁盘的代价就会严重影响系统的效率,因此系统的设计者必须将数据在磁盘上的位置加以记录和组织,通过在内存中的一些计算来取代对磁盘漫无目的的访问,才能提高系统的效率,尤其是GIS涉及的是各种海量的复杂数据,索引对于处理的效率是至关重要的.其二是GIS 所表现的地理数据多维性使得传统的B树索引并不适用,因为B树所针对的字符、数字等传统数据类型是在一个良序集之中,即都是在一个维度上,集合中任给两个元素,都可以在这个维度上确定其关系只可能是大于、小于、等于三种,若对多个字段进行索引,必须指定各个字段的优先级形成一个组合字段,而地理数据的多维性,在任何方向上并不存在优先级问题,因此B树并不能对地理数据进行有效的索引,所以需要研究特殊的能适应多维特性的空间索引方式.

1984年Guttman发表了《R树:一种空间查询的动态索引结构》,它是一种高度平衡的树,由中间节点和页节点组成,实际数据对象的最小外接矩形存储在页节点中,中间节点通过聚集其低层节点的外接矩形形成,包含所有这些外接矩形.其后,人们在此基础上针对不同空间运算提出了不同改进,才形成了一个繁荣的索引树族,是目前流行的空间索引.

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

2 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树的示例如图所示：

3 R-Tree算法描述

算法描述如下：

对象数为n,扇区大小定为fan.

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

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

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

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

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

（6）每一小组成为叶结点,叶子结点数为nn.

（7）N=nn,返回1.

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

1 R-Tree

多维索引技术的历史可以追溯到20世纪70年代中期.就在那个时候,诸如Cell算法、四叉树和k-d树等各种索引技术纷纷问世,但它们的效果都不尽人意.在GIS和CAD系统对空间索引技术的需求推动下,Guttman于1984年提出了R树索引结构,发表了《R树:一种空间查询的动态索引结构》,它是一种高度平衡的树,由中间节点和页节点组成,实际数据对象的最小外接矩形存储在页节点中,中间节点通过聚集其低层节点的外接矩形形成,包含所有这些外接矩形.其后,人们在此基础上针对不同空间运算提出了不同改进,才形成了一个繁荣的索引树族,是目前流行的空间索引.

2 R+树

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

3 R*树

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

4 QR树

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

5 SS树

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

6 X树

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

5 R-Tree空间索引算法的最新研究

信息的膨胀使数据库检索需要面对的问题越来越多.在构建索引方面,最主要面临的则是如何构造高效的索引算法来支持各种数据库系统（比如：多媒体数据库、空间数据库等）,特别是如何有效的利用算法来实现加速检索.概括地说,R-Tree空间索引算法的研究要做到：支持高维数据空间；有效分割数据空间,来适应索引的组织；高效的实现多种查询方式系统中的统一.R-Tree的索引结构最新研究不能是单纯为了加速某种查询方式或提高某个方面的性能,忽略其他方面的效果,这样可能会造成更多不必要的性能消耗.

XML作为可扩展的标示语言,其索引方法就是基于传统的R-Tree索引技术的XR-Tree索引方法.该方法构造了适合于XML数据的索引结构.XR-Tree索引方法是一种动态扩充内存的索引数据结构,针对XISS（XML Indexing and Storage System：XML索引和存储体系）中结构连接中的问题,设计了基于XR-Tree索引树有效地跳过不参与匹配的元素的连接算法.但这种索引方法在进行路径的连接运算中仍然存储大量的中间匹配结果,为此一种基于整体查询模式的基于索引的路径连接算法提出,即利用堆栈链表来临时压栈存储产生的部分匹配结果,并且随着匹配的动态进行出栈操作.这样在查询连接处理完成以后,直接输出最终结果,既节省了存储空间又提高了操作效率.

---