空间数据库索引技术课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,空间数据库索引技术,目录,空间数据库索引,的理论基础,有代表性的空间数据索引结构,空间数据库的索引是提高空间数据库存储效率、空间检索性能的关键技术,。,空间数据库索引,的理论基础,空间数据,空间数据是指与二维、三维或更高维空间的空间坐标及空间范围相关的数据,例如地图上的经纬度、湖泊、城市等。典型的关系型数据库模式中,并没有存储空间数据的位置,它只能处理单维的属性数据。所谓单维属性数据是指传统类型,(,包括数字型、字符型等,),的数据,它不包括描述空间位置和形状的坐标信息和描述空间关系的拓扑信息。与传统的数据库相比,空间数据的处理是一项时间和空间开销更大的操作。为了有效提高对空间数据的处理效率,空间数据库必须利用有效的索引机制,。,空间数据,空间数据的特征,1.,数据结构的复杂性和多样性,2.,数据的动态性,3.,数据的海量性,4.,没有标准的空间代数操作,5.,时间代价比较大,6.,多尺度与多态性,7.,不能排序性,8.,空间关系特性,数据结构的复杂性和多样性,对于空间数据来说，空间对象有可能是点、线或者其他类型的对象，因此在数据库进行存储的时候，不可能用一种固定长度的数据类型来存取所有的数据，需要根据对象的不同情况来选择合适的数据结构。,没有标准的空间代数操作,数据的海量性,数据的动态性,这个特性要求数据结构要能够适应由插入、删除或者更新等操作所引起的数据的变化。,空间数据的数据量是非常巨大的，通常成为海量数据，一个城市的地理信息系统中的数据可以达到几十,GB,，若将视频数据也加在其中，可以达到,TB,的数量级。,在空间数据库中，空间对象的操作并没有一定的标准，通常要根据实际的应用领域来确定，而且操作是不封闭的,对象的相交可能形状就会发生变化，这也是导致空间代数操作不能标准化的重要原因。,多尺度与多态性,同一个空间对象，在不同的观察尺度具有不同的比例尺和精度，导致一个对象在不同的情况下，其表现的形态也各不相同,如一个城市一定的比例尺下就退化为一个点。,空间关系特性,不能排序性,空间对象都有其空间位置信息，无法对空间数据进行线性排序并且保证空间相邻的对象仍然能够相邻。,空间数据不仅仅包含了空间的位置信息，而且包含了对象的拓扑信息，这些信息方便空间数据的查询和空间分析，但同时也增加了对空间数据一致性和完整性的维护复杂度。,空间数据的海量性，加上操作的不标准，没有更好的标准的方法进行查询优化，所以对于各种操作所花费的时间代价也各不相同，但往往都高于传统的关系数据库的操作代价。,时间代价比较大,空间数据库索引,的理论基础,空间数据库,空间数据库指的是,GIS,地理信息系统,在计算机物理存储介质上存储的与应用相关的,地理空间数据,的总和，一般是以一系列特定结构的文件的形式组织在存储介质之上的。空间数据库的研究始于,20,世纪,70,年代的,地图制图,与,调干图像处理,领域，其目的是为了有效地利用卫星遥感资源迅速绘制出各种经济专题地图。由于传统的关系数据库在空间数据的表示、存储、管理、检索上存在许多缺陷，从而形成了空间数据库这一数据库研究领域。而传统数据库系统只针对简单对象，无法有效的支持复杂对象（如图形、图像）。,注：,空间数据库就是将,GIS,中的图层、数据集、网络、,拓扑关系,存在关系等数据库中，如,SQLSERVER,、,ORACLE,、,Access,等，就构成了一个空间数据库。,空间数据库索引,的理论基础,空间索引,空间索引是指依据空间对象的位置和形状或空间对象之间的某种空间关系,按一定顺序排列的一种数据结构,其中包含空间对象的概要信息。作为一种辅助性的空间数据结构,空间索引介于空间操作算法与空间对象之间,它通过筛选作用,大量与特定空间操作无关的空间对象被排除,从而提高空间操作的速度和效率。空间索引的性能优劣直接影响空间数据库和地理信息系统的整体性能,它是空间数据库和地理信息系统的一项关键技术。,空间索引结构的特点,1.,动态构造,2.,二级,/,三级存储管理,3.,支持尽量多的操作,4.,独立于输入数据及插入顺序,5.,可增长性,6.,时间的有效性,7.,空间的有效性,8.,并行性及可恢复性,动态构造,在数据库中，数据有动态和静态两种，由于对数据库中的数据需要有一定的操作，比如插入或删除，因此要求索引结构也必须能够与之保持一致，即空间的索引结构也应该支持动态的数据的插入和删除，以便于维护数据的一致性。,独立于输入数据及插入顺序,支持尽量多的操作,二级,/,三级存储管理,尽管随着技术的发展，主存的容量日益增大，但仍不能将一个完整的数据库调入到主存中，因此索引结构要充分考虑到二级以及三级的存储管理，以提高对这中间缓存的利用率。,输入数据的顺序对有些索引结构的索引效率产生一定的影响，有些索引结构在不同的输入顺序下会产生不同的索引并且性能差异很大，因此空间索引结构应该支持各种高维数据，并且支持任意的插入顺序，使索引结构能够适用于各种数据的情况。,索引结构应支持多种操作以满足不同数据的类型需要，在提高对某些数据处理能力的基础上，不能牺牲其它的操作的处理能力，应同时保持相应的处理性能。,可增长性,索引结构要能够根据数据库大小的增长而调整相应的结构，具有一定的自适应性。,并行性及可恢复性,空间的有效性,时间的有效性,查找速度必须是快速的，要求查询或者更新等操作的时间复杂度要低,。,索引结构要能够支持并行操作，以提高查询的效率，并在发生异常时，可以较快的对建立的索引结构进行重建，即要有一定的可恢复性,。,一个索引结构同其原始数据相比应是比较小的，从而保证一定的空间利用率,。,几种有代表性的空间数据索引结构,KD-,树类,网格文件,R-,树,四叉树,网格文件,网格文件的基本思想是根据一正交的网格划分,k,维的数据空间。,k,维数据空间的网格由,k,个一维数组表示,这些数组称为刻度。将其保存在主存。刻度的每一边界构成,k-1,维的超平面。整个数据空间被所有的边界划分成许多,k,维的矩形子空间,这些矩形子空间称为网格目录,用,k,维的数组表示,将其保存在硬盘上。网格目录的每一网格单元包含一外存页的地址,这一外存页存储了该网格单元内的数据目标,称为数据页。一数据页允许存储多个相邻网格单元的目标。网格文件的查找简单,查找效率较高,适用于点目标的索引。,KD-,树类,KD-,树是,k,维的二叉查找树,是二叉查找树在多维空间的扩展。主要用于索引多属性的数据或多维点数据。每一个节点所表示的,k,维空间被一个可能在,k,个方向上出现的超平面划分为两个部分。每一个超平面中至少有一个点数据。,KD-,树对于点匹配查找,它继承了二叉查找树的优点,但删除操作较复杂。,四叉树,四叉树实际上是指在,k,维数据空间中,每一节点有,2,k,子树。用于对空间点的表示与索引。每个节点存储了一空间点的信息及,2,k,个子节点的指针。如二维空间的四叉树,每个子节点对应一个矩形,用四种方位,NW,NE,SW,SE,表示。逐级将空间划分到含有数据的个数低于某一值的矩形为止。,R-,树,R-,树是,B-,树在多维空间的扩展,其特点是能索引一定范围内的对象。其叶子节点包含多个形式为,(OI,MBR),的实体,OI,为空间目标标志,MBR,为该目标在,k,维空间中的最小包围矩形。非叶子节点包含多个形式为,(CP,MBR),的实体。,CP,为指向子树根节点的指针,MBR,为包围其子节点中所有,MBR,的最小包围矩形。,R-,树必须满足如下特性,:,(1),若根节点不是叶子节点,则至少有两棵子树,;,(2),除根之外的所有中间节点至多有,M,棵子树,至少有,m,棵子树,;,(3),每个叶子节点均包含,m,至,M,个数据项,;,(4),所有的叶子节点都出现在同一层次,;,(5),所有节点都需要同样的存储空间,(,通常为一个磁盘页,),。,因此各子空间会产生重叠,;,查找路径也往往是多条的。随着索引数据量的增加,包围矩形的重叠会增加,将严重影响查找性能。,R-,树,THANKS,