空间索引解析课件.ppt

1、 主要内容空间索引的概念空间索引的概念问题引入问题引入3 3 1 1索引的概念索引的概念3 33 32 21 1空间索引的分类空间索引的分类3 34 4空间数据库之空间索引技术1 问题引入l在图书馆中找到自己想要的书？在图书馆中找到自己想要的书？l怎样在字典里查找生字？怎样在字典里查找生字？l怎样在一栋大楼里找到人力资源部？怎样在一栋大楼里找到人力资源部？空间数据库之空间索引技术1 问题引入如何找到人力资源部空间数据库之空间索引技术 主要内容问题引入问题引入3 3 1 1索引的概念索引的概念3 33 3 2 21 13 3 4 4空间索引的概念空间索引的概念空间索引的分类空间索引的分类空间数据

2、库之空间索引技术2 索引的概念p 索引：英文index，指示位置的意思。p 索引是将文献中具有检索意义的事项（可以是人名、地名、词语、概念、或其他事项）按照一定方式有序编排起来，以供检索的工具书。（摘自互动百科）p 索引是根据表中一列或若干列按照一定顺序建立的列值与记录行之间的对应关系表。（摘自百度百科）p 索引本身是一个文件，当索引很大时，可以分块，建立高一层的索引。如此继续下去，得到一个多级索引结构。空间数据库之空间索引技术空间数据库之空间索引技术索引项：索引项：关键词值关键词值和和指针指针 索引的基本构件是索引的基本构件是索引索引项项。一个索引项中有。一个索引项中有关关键词值键词值和和指

3、针指针，通过指，通过指针就可找到含有此关键针就可找到含有此关键词值的记录，即一个索词值的记录，即一个索引项为：（关键词值，引项为：（关键词值，指针）。多个索引项就指针）。多个索引项就构成了一个索引（表）构成了一个索引（表）2 索引的概念索引构件 主要内容空间索引的概念空间索引的概念3 3 1 13 33 3 2 21 13 3 4 4问题引入问题引入索引的概念索引的概念空间索引的分类空间索引的分类空间数据库之空间索引技术3 空间索引的概念引入空间索引的原因l 计算机存储器分为内存、外存，空间数据采用外存存储l 访问一次内存时间3040ns（纳秒），外存810ms（毫秒），可以看出两者相差十万倍

4、以上l 如果对外存上数据的位置不加以记彔和组织，每查询一个数据项就要扫描整个数据文件l 必须将数据在磁盘上的位置加以记彔和组织，通过在内存中的一些计算来取代对磁盘漫无目的的访问（空间换时间）n计算机自身原因计算机自身原因空间数据库之空间索引技术3 空间索引的概念引入空间索引的原因n空间数据管理的独有特征l空间数据具有海量数据特征，NASA每天产生TB级数据，如无索引管理将寸步难行，必将成为“数据坟墓”。l由于地理数据的多维性，在任何方向上并不存在优先级问题。普通索引所针对的字符、数字等在一个维度上，任意两个元素，都可以确定其关系(,=)空间数据库之空间索引技术3 空间索引的概念内涵p 依据空间

5、对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。p 作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。空间数据库之空间索引技术 主要内容空间索引的概念空间索引的概念3 3 1 13 33 3 2 21 13 3 4 4问题引入问题引入索引的概念索引的概念空间索引的分类空间索引的分类空间数据库之空间索引技术4 空间索引的分类空空间间索索引引p 基于格网的空间索引p 基于树的空间索引结构p

6、基于填充曲线的空间索引结构空间数据库之空间索引技术4 空间索引的分类-格网索引（Grid Index)思路：将研究区域用横竖线条划分大小相等或不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。步骤：1）.将研究区域用横竖线条划分大小相等或不等的格网；空间数据库之空间索引技术4 空间索引的分类-格网索引（Grid Index)2）.记录每一个格网所包含的空间实体和记录实体穿过的网格；G G（1,21,2）：）：1 1G G（1,31,3）:2,8:2,8G G（2,32

7、,3）:3,4:3,47: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)3）.查询（开窗）查询（开窗）空间数据库之空间索引技术4 空间索引的分类-格网索引（Grid Index)对应格元：G（2,3），G（2,4）,G（3,3）,G（3,4）空间数据库之空间索引技术4 空间索引的分类-格网索引（Grid Index)对应实体：相交模式下：对应实体：相交模式下：3,4,5,8,123,4,5,8,12对应实体：包含模式下：对应实体：包含模式下

8、：3,4,5,123,4,5,12空间数据库之空间索引技术将坐标空间中所有的几何体以分解完整且互不重叠的分块面片覆盖，其基本思想是将坐标空间的范围视为一矩形，四叉树分解的第一步是将矩形沿坐标轴方向平均分割生成四个相同大小的分块，对每一个与几何体相交的面片继续以相同形式分割，直至满足一定的原则，如面片达到一定大小或覆盖几何体的面片达到一定数目，则分解停止。4 空间索引的分类四叉树空间索引空间数据库之空间索引技术4 空间索引的分类四叉树空间索引空间数据库之空间索引技术 树的概念 构成：根节点、中间结点、叶结点、无回路的图。度量：树的深度，子结点个数 平衡树平衡树 根结点到每一个叶结点的深度相等。树

9、中每个非叶结点有n到M个子结点，M 对特定的树是固定的(阶数)。2=n=M/24 空间索引的分类R树空间索引-平衡树空间数据库之空间索引技术B树的定义 B树是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件：（1）每个结点至多有m个子结点；（2）除根结点和叶结点外，其它每个结点至少有m/2 个子结点；（3）若根结点不是叶子结点，则至少有两个子结点；（4）所有的叶结点在同一层；4 空间索引的分类R树空间索引-B树空间数据库之空间索引技术基本思想用最小外接矩形的层次集合来组织空间对象；是B树在多维上的扩展 R-树的分类 处理大的空间对象 R 树：叶结点（数据）矩形可能重叠，中间结点（目录

10、）矩形允许重叠(overlap)R+树：中间结点的目录矩形不允许重叠；R树和R+树的基本概念，阅读课本4 空间索引的分类R树空间索引空间数据库之空间索引技术 R树的非叶结点（I,子结点的指针）：I为子树结点所表示的矩形MBR;子结点的指针:指向低一层结点。R树的叶结点（I,元组标识符）：I为空间对象的MBR;元组标识符是数据库中存储对应于MBR的对象的元组唯一标识符。R 树结点的表示4 空间索引的分类R树空间索引空间数据库之空间索引技术R-树的特征 平衡树 结点是矩形 子结点矩形位于父结点矩形内；中间结点可能重叠；其他属性见4.2.2节；查找操作的实现搜索根结点、确定相关的子结点。递归地搜索子

11、结点；由于中间结点可以重叠，查找路 径可能有多条例如:find record for rectangle 5Root search identifies child xSearch of x identifies children b and cSearch of b does not find object 5Search of c find object 5Fig 4.15Fig 4.16空间数据库之空间索引技术R 树R+特征平衡树结点是矩形 子结点矩形位于父结点矩形内；中间结点不重叠；叶结点Polygon,Line的MBR查找操作的实现 与R树类似但查找时每次只有一个子节点跟随(子结点上

12、的查找路径只有一条)Fig 4.18Fig 4.174 空间索引的分类R树空间索引空间数据库之空间索引技术 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树空间索引空

13、间数据库之空间索引技术R 树优点 很强的灵活性：无须预知整个空间对象所在的空间范围,就能建立空间索引。高维索引：MBR是个广义的概念。插入和删除操作相对较容易，索引空间可以重叠。较少的存储空间4 空间索引的分类R树空间索引空间数据库之空间索引技术R 树缺点 查询效率有时很低：索引空间经常重叠，可能要对多条路径进行搜查后才能得到最后的结果。频繁的数据更新影响查询效率：空间对象插入顺序的不同会形成不同结构的R 树。4 空间索引的分类R树空间索引空间数据库之空间索引技术选择R树或者四叉树索引 R树索引树索引四叉树索引四叉树索引不能调整对几何体的逼近精度(Spatial使用最小边界矩形来进行调整)通过

14、设置格网(tile)以及格网数目调整对几何实体的逼近精度索引的创建和调整容易索引的调整比较复杂，设置合适的微调参数值对性能影响很大对存储量的需求较小需要很多的存储量对邻近查询(SDO-NN操作)速度较快临近查询效率比较低几何实体的更新操作频繁时，性能影响较大大量更新不影响四叉树的性能索引可以达到四维只能索引二维数据对于全球(whole-earth)索引需要使用R树对于大地数据上使用SDO-WITHIN-DISTANCE查询，推荐使用R树4 空间索引的分类R树空间索引空间数据库之空间索引技术创建创建R树索引树索引CREATE INDEX territory_idx ON territories(

15、territory_geom)INDEXTYPE IS MDSYS.SPATIAL_INDEX;创建四叉树索引创建四叉树索引CREATE INDEX ROADS_FIXED ON ROADS(SHAPE)INDEXTYPE IS MDSYS.SPATIAL_INDEXPARAMETERS(SDO_LEVEL=8);Oracle中空间索引的创建4 空间索引的分类空间索引空间数据库之空间索引技术4.1.5 聚类文件组织 目的：降低常见的大查询的寻道时间和等待时间；对于空间数据库，在二级存储中，空间上相邻的和查询上有关联的对象在物理上应当存储在一起。有序文件不能体现空间数据的特点。类别：内部聚类：一

16、个对象的全部存放在一个磁盘页面中；局部聚类：一组近似的对象存放在一个磁盘页面中；全局聚类：一组邻接对象存放在多个物理上相邻的磁盘页面中 全局聚类：用空间填充曲线的方法 Z曲线；Hilbert曲线。Z曲线Hilbert曲线空间数据库之空间索引技术Z曲线的搜素顺序（Z值）0 21 344 空间索引的分类填充曲线空间数据库之空间索引技术 将一个区域在x和y坐标上进行折半（0，1）迭代划分；在i次迭代中(i=0,1,n-1)，x,y轴上的分段数为N=2i，分段的x，y位置可以用i位二进制数（0，1）表示。将平面分成NxN的网格区域。每个网格坐标的二进制表示 如何计算每个单元的Z值？i=0,N=2i=1

17、i=1,N=2i=2i=2,N=2i=40 11000 01 10 11111001004 空间索引的分类填充曲线-Z曲线的构造空间数据库之空间索引技术 1）读入每个网格x和y坐标的二进制表示；2）交叉扫描X、Y二进制数字的比特，形成一个新二进制字符串；计算出结果二进制串的十进制值作为该网格的Z值。4 空间索引的分类填充曲线-Z曲线的构造步骤空间数据库之空间索引技术三个对象A,B,C给出x,y坐标，查找Z值4 空间索引的分类填充曲线-Z曲线的例子空间数据库之空间索引技术 1 读入每个网格x和y坐标的n比特二进制表示；2 对x和y隔行扫描二进制比特到一个字符串；3 将字符串分成两个比特长的字符串

18、；4 计算两比特字符串的十进制表示；5 对于网格的十进制串的每个数字j 如果 j=0,把跟在其后的所有1变为3，如果是3变为1 如果 j=3，把跟在其后的所有0变为2，如果是2变为0 6 将步骤5转换的十进制串中每一个十进制值转换为二进制，然后连接成串，在将整个串转换成十进制，作为该网格的H序号值。4 空间索引的分类填充曲线-Hilbert曲线的产生空间数据库之空间索引技术例子例子x、y隔行扫描,形成二进制串两比特计算的十进制转换十进制的Hillbert 序号空间数据库之空间索引技术Z曲线有斜线，Hilbert 要比Z曲线好一些。4 空间索引的分类填充曲线-比较空间数据库之空间索引技术作业 P133 习题1和习题2对于下图中的一组叶结点和中间结点，画出相应的R树结构，并列出用虚线表示的查询矩形所要搜索的结点。第一层结点是1和2，第二层结点是A、B、C、D和E。叶结点包括a、b、k.