*,*,空间数据库之空间索引技术,空间数据库之空间索引技术,*,*,空间数据库之空间索引技术,空间数据库之空间索引技术,*,*,空间数据库之空间索引技术,*,*,空间数据库之空间索引技术,*,*,空间数据库之空间索引技术,*,*,空间数据库之空间索引技术,*,*,空间数据库之空间索引技术,*,*,空间数据库之空间索引技术,*,*,空间数据库之空间索引技术,*,*,空间数据库之空间索引技术,*,*,空间数据库之空间索引技术,*,空间数据库之空间索引技术,*,北京建筑大学测绘与城市空间信息学院,2015,年,12,月,03,日,空 间 索 引 技 术,主讲人：郭明 博士,空间数据库之,-,北京建筑大学测绘与城市空间信息学院2015年12月03日空,主要内容,空间索引的概念,问题引入,3,1,索引的概念,3,3,2,1,空间索引的分类,3,4,空间数据库之空间索引技术,主要内容空间索引的概念问题引入31索引的概念3321空,1 问题引入,在图书馆中找到自己想要的书？,怎样在字典里查找生字？,怎样在一栋大楼里找到人力资源部？,空间数据库之空间索引技术,1 问题引入在图书馆中找到自己想要的书？空间数据库之空间索引,1 问题引入,如何找到人力资源部,空间数据库之空间索引技术,1 问题引入如何找到人力资源部空间数据库之空间索引技术,主要内容,问题引入,3,1,索引的概念,3,3,2,1,3,4,空间索引的概念,空间索引的分类,空间数据库之空间索引技术,主要内容问题引入31索引的概念332134空间索引的概,2 索引的概念,索引：英文,index,，指示,位置,的意思。,索引是将文献中具有,检索意义,的事项（可以是人名、地名、词语、概念、或其他事项）按照一定方式有序编排起来，以供检索的,工具书,。（摘自互动百科）,索引是根据表中一列或若干列按照一定顺序建立的列值与记录行之间的,对应关系表,。（摘自百度百科）,索引本身是一个,文件,，当索引很大时，可以分块，建立高一层的索引。如此继续下去，得到一个多级索引结构。,空间数据库之空间索引技术,2 索引的概念索引：英文index，指示位置的意思。空间数据,索引项：,关键词值,和,指针,索引的基本构件是,索引项,。一个索引项中有,关键词值,和,指针,，通过指针就可找到含有此关键词值的记录，即一个索引项为：（关键词值，指针）。多个索引项就构成了一个索引（表）,2 索引的概念,索引构件,索引项：关键词值和指针 索引的基本构件是索引项。一个索引项,主要内容,空间索引的概念,3,1,3,3,2,1,3,4,问题引入,索引的概念,空间索引的分类,主要内容空间索引的概念31332134问题引入索引的概,3,空间索引的概念,引入空间索引的原因,计算机存储器分为,内存,、,外存，,空间数据采用外存存储,访问一次内存时间,3040ns,（纳秒），外存,810ms,（毫秒），可以看出两者相差,十万倍,以上,如果对外存上数据的位置不加以记彔和组织，每查询一个数据项就要,扫描整个数据文件,必须将,数据在磁盘上的位置,加以,记彔和组织,，通过在内存中的一些计算来取代对磁盘漫无目的的访问（空间换时间）,计算机自身原因,3 空间索引的概念引入空间索引的原因 计算机存储器分为内存,3,空间索引的概念,引入空间索引的原因,空间数据管理的独有特征,空间数据具有,海量数据,特征，,NASA,每天产生,TB,级数据，如无索引管理将寸步难行，必将成为“数据坟墓”。,由于地理数据的多维性，在任何方向上并不存在优先级问题。普通索引所针对的字符、数字等在一个维度上，任意两个元素，都可以确定其关系,(,=),3 空间索引的概念引入空间索引的原因空间数据管理的独有特征,3,空间索引的概念,内涵,依据空间,对象的位置,和,形状,或,空间对象之间的某种空间关系,按一定的顺序排列的一种,数据结构,，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的,指针,。,作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作,无关的空间对象被排除,，从而提高空间操作的速度和效率。,3 空间索引的概念内涵依据空间对象的位置和形状或空间对象之,主要内容,空间索引的概念,3,1,3,3,2,1,3,4,问题引入,索引的概念,空间索引的分类,主要内容空间索引的概念31332134问题引入索引的概,4,空间索引的分类,空间索引,基于格网的空间索引,基于树的空间索引结构,基于填充曲线的空间索引结构,4 空间索引的分类空间索引基于格网的空间索引基于树的空间索引,4,空间索引的分类,-,格网索引（,Grid Index),思路：,将研究区域用横竖线条划分大小相等或不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。,步骤：,1,）,.,将研究区域用横竖线条划分大小相等或不等的格网；,4 空间索引的分类-格网索引（Grid Index)思路,4,空间索引的分类,-,格网索引（,Grid Index),2,）,.,记录每一个格网所包含的空间实体和记录实体穿过的网格；,G,（,1,2,）：,1,G,（,1,3,）,:2,8,G,（,2,3,）,:3,4,7:G(2,1),G(2,2),G(3,1),G(3,2),8:G(1,3),G(2,4),G(3,4),G(3,5),G(4,5),4 空间索引的分类-格网索引（Grid Index)2）,4,空间索引的分类,-,格网索引（,Grid Index),3,）,.,查询（开窗）,4 空间索引的分类-格网索引（Grid Index)3）,4,空间索引的分类,-,格网索引（,Grid Index),对应格元：,G,（,2,3,），,G,（,2,4,）,G,（,3,3,）,G,（,3,4,）,4 空间索引的分类-格网索引（Grid Index)对应,4,空间索引的分类,-,格网索引（,Grid Index),对应实体：相交模式下：,3,4,5,8,12,对应实体：包含模式下：,3,4,5,12,4 空间索引的分类-格网索引（Grid Index)对应,将坐标空间中所有的几何体以分解完整且互不重叠的分块面片覆盖，其基本思想是将坐标空间的范围视为一矩形，四叉树分解的第一步是将矩形沿坐标轴方向平均分割生成四个相同大小的分块，对每一个与几何体相交的面片继续以相同形式分割，直至满足一定的原则，如面片达到一定大小或覆盖几何体的面片达到一定数目，则分解停止。,4,空间索引的分类,四叉树空间索引,将坐标空间中所有的几何体以分解完整且互不重叠的分块面片覆盖，,4,空间索引的分类,四叉树空间索引,4 空间索引的分类四叉树空间索引,树的概念,构成：根节点、中间结点、叶结点、无回路的图。,度量：树的深度，子结点个数,平衡树,根结点到每一个叶结点的深度相等。,树中每个非叶结点有,n到M个子结点，M 对特定的树是固定的(阶数)。2=n=M/2,4,空间索引的分类,R,树空间索引,-,平衡树,树的概念4 空间索引的分类R树空间索引-平衡树,B树的定义 B树是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件：（1）每个结点至多有m个子结点；（2）除根结点和叶结点外，其它每个结点至少有m/2 个子结点；（3）若根结点不是叶子结点，则至少有两个子结点；（4）所有的叶结点在同一层；,4,空间索引的分类,R,树空间索引,-B,树,B树的定义 B树是一种平衡的多分树，通常我们说m阶,基本思想,用最小外接矩形的层次集合来组织空间对象；,是,B,树在多维上的扩展,R-,树的分类,处理大的空间对象,R,树：叶结点（数据）矩形可能重叠，中间结点,（目录）矩形允许重叠,(overlap),R+,树：中间结点的目录矩形不允许重叠；,R,树和,R+,树的基本概念，阅读课本,4,空间索引的分类,R,树空间索引,基本思想4 空间索引的分类R树空间索引,R树的非叶结点,（,I,子结点的指针）：I为子树结点所表示的矩形MBR;子结点的指针:指向低一层结点。,R树的叶结点,（,I,元组标识符）：I为空间对象的MBR;元组标识符是数据库中存储对应于MBR的对象的元组唯一标识符。,R 树结点的表示,4,空间索引的分类,R,树空间索引,R树的非叶结点R 树结点的表示4 空间索引的分类R树空间,R-树的特征,平衡树,结点是矩形,子结点矩形位于父结点矩形内；,中间结点可能重叠；,其他属性见,4.2.2节；,查找操作的实现,搜索根结点、确定相关的子结点。,递归地搜索子结点；,由于中间结点可以重叠，查找路,径可能有多条,例如,:find record for rectangle 5,Root search identifies child x,Search of x identifies children b and c,Search of b does not find object 5,Search of c find object 5,Fig 4.15,Fig 4.16,R-树的特征 Fig 4.15Fig 4.16,R 树,R+特征,平衡树,结点是矩形,子结点矩形位于父结点矩形内；,中间结点不重叠；,叶结点,Polygon,Line的MBR,查找操作的实现,与,R树类似,但查找时每次只有一个子节点跟随(子结点上的查找路径只有一条),Fig 4.18,Fig 4.17,4,空间索引的分类,R,树空间索引,R 树R+特征Fig 4.18Fig 4.174 空间索,1-9,是图层中相应几何体的,MBR,。,a,、,b,、,c,、,d,是,R,树的叶结点，含有所包括的几何体的,MBR,和指向该几何体的指针；即,a,含,1-MBR,、,1-ID,、,2-MBR,、,2-ID,，,b,含,3-MBR,、,3-ID,、,4-MBR,、,4-ID,，,c,含,5-MBR,、,5-ID,、,6-MBR,、,6-ID,、,7-MBR,、,7-ID,，,d,含,8-MBR,、,8-ID,、,9-MBR,、,9-ID,。,A,含,a-MBR,、,a-ID,和,b-MBR,、,b-ID,，,B,含,c-MBR,、,c-ID,和,d-MBR,、,d-ID,。,根结点（,root,）含,A,和,B,的,MBR,。,4,空间索引的分类,R,树空间索引,1-9是图层中相应几何体的MBR。4 空间索引的分类,R,树优点,很强的灵活性：无须预知整个空间对象所在的空间范围,就能建立空间索引。,高维索引：,MBR,是个广义的概念。,插入和删除操作相对较容易，索引空间可以重叠。,较少的存储空间,4,空间索引的分类,R,树空间索引,R 树优点很强的灵活性：无须预知整个空间对象所在的空间范围,R,树缺点,查询效率有时很低：索引空间经常重叠,，,可能要对多条路径进行搜查后才能得到最后的结果。,频繁的数据更新影响查询效率：空间对象插入顺序的不同会形成不同结构的,R,树。,4,空间索引的分类,R,树空间索引,R 树缺点查询效率有时很低：索引空间经常重叠，可能要对多条路,选择,R,树或者四叉树索引,R,树索引,四叉树索引,不能调整对几何体的逼近精度,(Spatial,使用最小边界矩形来进行调整,),通过设置格网,(tile),以及格网数目调整对几何实体的逼近精度,索引的创建和调整容易,索引的调整比较复杂，设置合适的微调参数值对性能影响很大,对存储量的需求较小,需要很多的存储量,对邻近查询,(SDO-NN,操作,),速度较快,临近查询效率比较低,几何实体的更新操作频繁时，性能影响较大,大量更新不影响四叉树的性能,索引可以达到四维,只能索引二维数据,对于全球,(whole-earth),索引需要使用,R,树,对于大地数据上使用,SDO-WITHIN-DISTANCE,查询，推荐使用,R,树,4,空间索引的分类,R,树空间索引,选择R树或者四叉树索引 R树索引四叉