对R-Tree的风行探究进展举办了剖析,若转载请于显著处标明出处

随笔版权由作者李晓晖和微博共有,若转载请于显著处标明出处:http://www.cnblogs.com/naaoveGIS/

作品版权由作者李晓晖和博客园共有,若转载请于显然处标明出处:http://www.cnblogs.com/naaoveGIS/

转自原文
R-Tree空间索引算法的研商过程和最新进展分析,2008

1.背景

在事先的博客中,我分别介绍了依照网格的上空引得(http://www.cnblogs.com/naaoveGIS/p/5148185.html)以及四叉树和网格结合的联合索引(http://www.cnblogs.com/naaoveGIS/p/6641449.html),要解决的问题均是判断一个点落在了面图层中的哪个面要素中。单从算法层面上分析,以上两种索引均有一些弊端:

a.网格索引由于对全体空间拓展网格划分,如若划分粒度太细容易出现索引冗余,尽管划分粒度太大则索引功能又极大回落。

    图片 1

b.四叉树索引同样存在一个图元标识被三个区域所关联,相应地囤积在三个叶子节点上,这样就存在索引的冗余,与网格索引存在一样的流弊。

        图片 2

为更加优化索引,大家决定利用R树来开展优化。

1.背景

在后边的博客中,我分别介绍了依照网格的空中引得(http://www.cnblogs.com/naaoveGIS/p/5148185.html)以及四叉树和网格结合的联合索引(http://www.cnblogs.com/naaoveGIS/p/6641449.html),要解决的问题均是判断一个点落在了面图层中的哪个面要素中。单从算法层面上分析,以上两种索引均有一些弊端:

a.网格索引由于对任何空间拓展网格划分,假使划分粒度太细容易并发索引冗余,倘使划分粒度太大则索引功效又宏大降低。

    图片 3

b.四叉树索引同样存在一个图元标识被三个区域所涉及,相应地蕴藏在多少个叶子节点上,这样就存在索引的冗余,与网格索引存在同样的流弊。

        图片 4

为越来越优化索引,我们决定动用R树来展开优化。

 

2.R树介绍

R树首要采取空间划分的见地,即采用MBR(Minimal Bounding
Rectangle,最小边界矩形)的措施,从叶子结点最先用矩形(rectangle)将空间框起来,结点越往上,框住的空间就越大,以此对空中拓展剪切:

        图片 5

有着的本来面目空间要素均是叶节点,这样便不会出现如四叉树索引和网格索引中冒出的长空要素被六个索引段带领,进而现身大量冗余索引的问题。

2.R树介绍

R树首要利用空间划分的见识,即采取MBR(Minimal Bounding
Rectangle,最小边界矩形)的办法,从叶子结点起首用矩形(rectangle)将空间框起来,结点越往上,框住的长空就越大,以此对空间拓展划分:

        图片 6

拥有的原来空间要素均是叶节点,这样便不会冒出如四叉树索引和网格索引中冒出的半空中要素被六个索引段率领,进而出现大量冗余索引的题材。

 

3.依据JTS的有血有肉落实

JTS中提供了构建索引的章程,其得以构建四叉树索引、R树索引、KD索引等。这里,我们直接利用JTS来构建R树索引。

JTS的介绍:https://en.wikipedia.org/wiki/JTS_Topology_Suite

JTS的源码下载:https://sourceforge.net/projects/jts-topo-suite/?source=navbar

3.依照JTS的具体贯彻

JTS中提供了构建索引的点子,其得以构建四叉树索引、R树索引、KD索引等。这里,我们一向行使JTS来构建R树索引。

JTS的介绍:https://en.wikipedia.org/wiki/JTS_Topology_Suite

JTS的源码下载:https://sourceforge.net/projects/jts-topo-suite/?source=navbar

摘要:正文介绍了半空中引得的定义、R-Tree数据结构和R-Tree空间引得的算法描述,并从R-Tree索引技术的利害对R-Tree的改善结构——变种R-Tree进行了讲演。最终,对R-Tree的流行琢磨进展举行了剖析。

3.1R树的构建

选拔GT读取到本地的SHP,获取到拥有的要素集,然后遍历要素将envelope和要素音信一一插入至StrTree中,构建R树:

   图片 7

3.1R树的构建

利用GT读取到本地的SHP,获取到所有的要素集,然后遍历要素将envelope和因素音讯一一插入至StrTree中,构建R树:

   图片 8

关键词:空间索引技术;R-Tree;讨论过程;最新进展

3.2依据R树的查询

将查询的半空中条件构造成一个Envelope在R树中询问,对查询出来的结果再一次开展点面关系判断:

   图片 9

3.2依照R树的查询

将查询的空中条件构造成一个Envelope在R树中询问,对查询出来的结果再一次开展点面关系判断:

   图片 10

时下数量检索的一个关键问题是速度。提高速度的核心技术是空间引得。空间引得是由空间地方到空中对象的照射关系。当前的局部特大型数据库都有空间引得能力,像Oracle,DB2。

4.优化

在我们事先的二种索引方法中,我们均将引得文件保留到了当地,每趟调用时去加载索引,如此IO是一个很大的瓶颈。现在我们创造一个容器,将StrTree保存至该容器中。查询时,间接从内存中获取到该树。

4.优化

在大家事先的二种索引方法中,大家均将引得文件保留到了当地,每一趟调用时去加载索引,如此IO是一个很大的瓶颈。现在我们创设一个器皿,将StrTree保存至该容器中。查询时,直接从内存中获取到该树。

空间索引技术并不单是为了增进显示速度,展现速度只有是它所要解决的一个问题。空间引得是为空间搜索提供一种适于的数据结构,以增进搜索速度。

5.效用相比较

5.效用相比较

空间索引技术的着力是:按照查找条件,比如一个矩形,急忙找到与该矩形相交的具备空中对象集合。当数据量巨大,矩形框相对于全图很时辰,这个集合相对于全图数据集大为缩短,在这个收缩的聚合上再处理各样复杂的追寻,效能就会大大进步。

5.1询问效用比较

在测试数据中选中一个特殊点(六个多边形的交接处):

   图片 11

 

各自对利用的两种索引举行了性能相比:

a.本地网格索引:

   图片 12

b.本地混合索引(四叉树与网格索引整合):

 图片 13

c.内存R树索引:

 图片 14

可见查询效能快了一倍左右。

5.1查询成效相比较

在测试数据中当选一个特殊点(两个多边形的交接处):

   图片 15

 

独家对拔取的两种索引举办了性能比较:

a.本地网格索引:

   图片 16

b.本地混合索引(四叉树与网格索引整合):

 图片 17

c.内存R树索引:

 图片 18

足见查询效率快了一倍左右。

所谓空间引得,就是指依据空间实体的职位和形制或空中实体之间的某种空间关系,按一定顺序排列的一种数据结构,其中含有空间实体的大意音讯如目的的标识、外接矩形及针对空间实体数据的指针。简单的讲,就是将空间对象按某种空间关系举办分割,未来对空中对象的存取都遵照划分块举办。

5.2索引构建效能比较

样本数量有2000两个面要素,此前的两种索引均使用当地工具构建,时间大体是1S左右(没有具体总括)。现在拔取JTS构建R树索引,效用为:

   图片 19

5.2索引构建效用相比

样本数量有2000多少个面要素,在此以前的两种索引均采取当地工具构建,时间大体是1S光景(没有具体总计)。现在采纳JTS构建R树索引,功用为:

   图片 20

1
引言

5.3占据的内存效能

此索引的优化中,我们将数据总体存入了内存。这里不可不着眼内存的占用量有多大。

貌似监控内享有二种艺术,通过工具查看或者代码段编写。代码段编写可以由此选拔SizeOf.jar实现,工具查看可以通过jvisualvm实现:

   图片 21

固有的本土SHP数据大小为:3.8M。

网格索引大小为:4.4M。

混合索引文件的深浅为:8.4M。

而读入内存中的R树索引的大小为:4.3M。

由于我们存储了要素所含有的具备信息,理论上,假诺大家将积存消息越来越缩减,内存占用会更小。目前来看,SHP数据本身的高低,会跟存入内存的消息大小有直接关系。

5.3占有的内存功能

此索引的优化中,我们将数据总体存入了内存。这里不可不着眼内存的占用量有多大。

一般监控内装有二种模式,通过工具查看或者代码段编写。代码段编写可以通过使用SizeOf.jar实现,工具查看可以经过jvisualvm实现:

   图片 22

原始的地头SHP数据大小为:3.8M。

网格索引大小为:4.4M。

混合索引文件的轻重缓急为:8.4M。

而读入内存中的R树索引的尺寸为:4.3M。

由于我们存储了要素所含有的有着音信,理论上,假诺我们将积存信息更为削减,内存占用会更小。近日来看,SHP数据我的分寸,会跟存入内存的信息大小有一直关联。

空间引得是对存储在介质上的数额地方信息的描述,用来提升系统对数据得到的频率。空间引得的指出是由两方面决定的:其一是出于统计机的系统布局将存贮器分为内存、外存
二种,访问这两种存储器一回所花费的日子一般为30~40ns,8~10ms,可以看到两岸相距十
万倍以上,即使现目前有“内存数据库”的布道,但大部分数据是储存在外存磁盘上的,倘使对磁盘上多少的岗位不加以记录和协会,每查询一个数码项就要扫描整个数据文件,这种访问磁盘的代价就会严重影响系统的效能,由此系统的设计者必须将数据在磁盘上的职务加以记录和公司,通过在内存中的片段总结来代替对磁盘漫无目的的拜访,才能加强系统的频率,尤其是GIS涉及的是各个海量的错综复杂数据,索引对于拍卖的功用是首要的。其二是GIS
所表现的地理数据多维性使得传统的B树索引并不适用,因为B树所针对的字符、数字等观念数据类型是在一个良序集之中,即都是在一个维度上,集合中任给多少个元素,都足以在那个维度上确定其关联只可能是超出、小于、等于二种,若对四个字段展开索引,必须指定各类字段的先行级形成一个整合字段,而地理数据的多维性,在此外方向上并不存在优先级问题,由此B树并无法对地理数据进行实用的目录,所以需要钻探相当的能适应多维特性的长空引得格局。

6.总结

当下目录模式任然有几点不足:

a.索引构建中的要素获取情势为本土SHP读取,需要扩张成对第三方服务数量的支撑。

b.当R数查询命中唯有一个元素时,因为小小的矩形的限定是过量等于实际要素范围的,所以还要举办一回点面判断。如此,当图层要素个数本身不多时,建立索引不必然可以加快。

 

                             —–欢迎转载,但保留版权,请于彰着处标明出处:http://www.cnblogs.com/naaoveGIS/

                                                                             
假设你认为本文确实协助了您,可以微信扫一扫,举办小额的打赏和鼓励,谢谢
^_^

                                                                   
                     
图片 23

 

6.总结

此时此刻目录模式任然有几点不足:

a.索引构建中的要素获取格局为本土SHP读取,需要扩张成对第三方服务数量的支撑。

b.当R数查询命中唯有一个要素时,因为小小的矩形的限定是出乎等于实际要素范围的,所以还要开展两次点面判断。如此,当图层要素个数本身不多时,建立索引不肯定可以加速。

 

                             —–欢迎转载,但保留版权,请于分明处标明出处:http://www.cnblogs.com/naaoveGIS/

                                                                             
假如您觉得本文确实援助了你,可以微信扫一扫,举行小额的打赏和鞭策,谢谢
^_^

                                                                   
                     
图片 24

 

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+树对跨区域的空间物体的多少的存储是有冗余的,而且随着数据库中多少的加码,冗余音信会持续增进。格林e也提出了他的R树的变种。

3 R\*

在1990年,贝克man和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索引树有效地跳过不参与配合的要素的接连算法。但那种索引方法在拓展路径的连接运算中仍旧存储大量的中等匹配结果,为此一种基于全部查询形式的依据索引的路子连接算法提议,即拔取堆栈链表来临时压栈存储爆发的一些匹配结果,并且随着匹配的动态进展出栈操作。这样在询问连接处理到位以后,直接出口最终结果,既节约了仓储空间又增长了操作功效。

 

相关文章