第五章 空间索引二

1、空间查询与空间检索（二）第五章第五章 空间查询是根据某个查询条件，对空间数据和属性数据进行查询，在数据库中检索出满足条件的数据子集。一、空间查询概念u图形图形-属性：属性：如如鼠标点取，拉框等鼠标点取，拉框等方式方式，检检索其相应属性；索其相应属性；u属性属性-图形图形检索对应的空间实体检索对应的空间实体 二、空间查询方式三、空间数据查询种类 1、几何参数查询包括点的位置坐标，两点间的距离，一个或一段包括点的位置坐标，两点间的距离，一个或一段线目标的长度，一个面目标的周长或面积等。线目标的长度，一个面目标的周长或面积等。2、空间定位查询给定一个点或一个几何图形，检索该图形范围内给定一个点或一个

2、几何图形，检索该图形范围内的空间对象及其属性。的空间对象及其属性。1 1）按点查询）按点查询：给定一个鼠标点，查询离它最近的对象及属性给定一个鼠标点，查询离它最近的对象及属性-点的捕捉点的捕捉。2 2）开窗查询）开窗查询-按矩形、圆、多边形查询按矩形、圆、多边形查询分为该窗口分为该窗口包含包含和和穿过穿过的区别。的区别。3、空间关系查询1 1）相邻分析检索相邻分析检索-通过通过检索拓扑关系检索拓扑关系p面面面面：如查询与面状地物相邻的多边形的：如查询与面状地物相邻的多边形的实现方法：实现方法：A A、从、从多边形与弧段关联表中，检索该多边形关联多边形与弧段关联表中，检索该多边形关联的所有弧段；

3、的所有弧段；B B、从、从弧段关联的左右多边形表中，检索出这些弧弧段关联的左右多边形表中，检索出这些弧段关联的多边形。段关联的多边形。p线线线线（与某干流（与某干流A A相连的所有支流）相连的所有支流）A A、从、从线状地物表中，查找组成线状地物表中，查找组成A A的所有弧段及关联的所有弧段及关联的结点；的结点；B B、从、从结点表中，查询与这些结点关联的弧段；结点表中，查询与这些结点关联的弧段；p点点点点（A A与与B B是否相通是否相通）等。）等。A12BC2 2）相关分析检索相关分析检索（不同要素类型之间的关系）（不同要素类型之间的关系）-通通过过检索拓扑关系检索拓扑关系 点点线线（自来

4、水（自来水GISGIS中，与某阀门相关的水管）中，与某阀门相关的水管）3 3）包含关系查询包含关系查询 查询某个面状地物所包含的空间对象。查询某个面状地物所包含的空间对象。4 4）穿越查询穿越查询 某公路穿越了某些县，采用空间运算的方法执行某公路穿越了某些县，采用空间运算的方法执行，根据一个线目标的空间坐标，计算哪些面或线，根据一个线目标的空间坐标，计算哪些面或线与之相交。与之相交。3、空间关系查询3、空间关系查询5 5）落入查询）落入查询 一个空间对象落入哪个空间对象之内。一个空间对象落入哪个空间对象之内。-空间运算空间运算 6 6）缓冲区查询）缓冲区查询根据用户给定的一个点、线、面缓冲的距

5、离，从而形根据用户给定的一个点、线、面缓冲的距离，从而形成一个成一个缓冲区的多边形缓冲区的多边形，再根据，再根据多边形检索多边形检索原理，检原理，检索该缓冲区内的空间实体。索该缓冲区内的空间实体。1 1） 查找查找仅选择一个属性表，给定仅选择一个属性表，给定一个属性值，找出对应的属性一个属性值，找出对应的属性记录或图形。记录或图形。在屏幕上已有一个属性表，在屏幕上已有一个属性表，用户任意点取记录，对应的图用户任意点取记录，对应的图形以高亮显示。形以高亮显示。 实现实现：执行数据库执行数据库查询语查询语言言，找到满足要求的，找到满足要求的记录记录，得得到它的到它的目标标识目标标识，再通过目标，再

6、通过目标标识在标识在图形数据文件图形数据文件中找到中找到对对应的空间对象应的空间对象，并，并显示出来显示出来。 4、属性查询4、属性查询实现实现：交互式选择各项，输入后，系统再交互式选择各项，输入后，系统再转转换换为标准的为标准的SQLSQL，由数据库系统执行或，由数据库系统执行或ODBC ODBC C C语言执行，得到结果，提取目标标识，在语言执行，得到结果，提取目标标识，在图形文件中找到空间对象，并显示。图形文件中找到空间对象，并显示。Select Select 属性项属性项 From From 属性表属性表 Where Where 条件条件 oror条件条件 and and 条件条件2

7、2）SQLSQL查询查询3）扩展）扩展SQL4、属性查询对对标准标准SQLSQL的的扩展扩展，即在，即在SQLSQL上上加入加入空间关系空间关系查询。查询。为此需要增加为此需要增加空间数据类型空间数据类型（如点、线、面等）和（如点、线、面等）和空间空间操作算子操作算子（求（求长度、长度、面积等）面积等）。在给定查询条件时也需。在给定查询条件时也需含有空间概念，如距离、邻近、叠加等。含有空间概念，如距离、邻近、叠加等。例如，例如，“查询长江流域人口大于查询长江流域人口大于5050万的县或市万的县或市”，可表示为：可表示为：SELECT SELECT * *FROM FROM 县县或市或市WHER

8、E WHERE 县或市县或市. .人口人口 50 50万万 AND AND CROSSCROSS（河流（河流. .名名称称=“=“长江长江”）示例示例1 11 1）查询：列出）查询：列出CountryCountry表中所有与美国（表中所有与美国（USAUSA）相邻的国家名字。）相邻的国家名字。SELECT C1.Name AS “Neighbors of USA”FROM Country C1，Country C2WHERE Touch（C1.Shape，C2.Shape）=1 ANDC2.Name= USA示例示例2 22 2）查询：找出）查询：找出RiverRiver表中所列出的河流流经的

9、国家。表中所列出的河流流经的国家。SELECT R.Name, C.NameFROM River R, Country CWHERE Cross（R.Shape, C.Shape）=1示例示例3 34 4）查询：圣劳伦斯河能为方圆）查询：圣劳伦斯河能为方圆300300公里以内的城市供水，列出能从该河公里以内的城市供水，列出能从该河获得供水的城市。获得供水的城市。SELECT Ci.NameFROM City Ci，River RWHERE Overlap（Ci.Shape, Buffer（R.Shape,300）=1 AND R.Name=St.Laurence示例示例4 45 5）查询：列出

10、）查询：列出CountryCountry表中每个国家的名字、人口和国土面积。表中每个国家的名字、人口和国土面积。SELECT C.Name, C.Pop, Area（C.Shape）AS AreaFROM Country 注意：Country表中的shape是polygon集合类型。示例示例5 56 6）查询：求出河流在流经的各国境内的长度。）查询：求出河流在流经的各国境内的长度。SELECT R.Name，Length（Intersection （R.Shape, C.shape） AS “Length”FROM River R，Country CWHERE Cross（R.Shape，C.

11、Shape）=1注意：注意： Intersection函数与拓扑关系判断函数函数与拓扑关系判断函数Intersect的不同点。前者是运算结果是一个几何的不同点。前者是运算结果是一个几何类类型，后者的运算结果是一个逻辑值。型，后者的运算结果是一个逻辑值。l怎样在一栋大楼里找到人力资源部？怎样在一栋大楼里找到人力资源部？l怎样在图书馆中找到自己想要的书？怎样在图书馆中找到自己想要的书？l怎样在字典里查找生字？怎样在字典里查找生字？问题引入问题引入一、索引的概念一、索引的概念l 索引：英文index，指示位置的意思。l 索引是将文献中具有检索意义的事项（可以是人名、地名、词语、概念、或其他事项）按照

12、一定方式有序编排起来，以供检索的工具书。（摘自互动百科）l 索引本身是一个文件，当索引很大时，可以分块，建立高一层的索引。如此继续下去，得到一个多级索引结构。空间索引空间索引 索引的基本构件是索引的基本构件是索引索引项项。一个索引项中有。一个索引项中有关关键词值键词值和和指针指针，通过指，通过指针就可找到含有此关键针就可找到含有此关键词值的记录，即一个索词值的记录，即一个索引项为：（关键词值，引项为：（关键词值，指针）。多个索引项就指针）。多个索引项就构成了一个索引（表）构成了一个索引（表）1.引入空间索引的原因引入空间索引的原因l 计算机存储器分为内存、外存，空间数据采用外存存储l 访问一次

13、内存时间3040ns（纳秒），外存810ms（毫秒），可以看出两者相差十万倍以上l 如果对外存上数据的位置不加以记彔和组织，每查询一个数据项就要扫描整个数据文件l 必须将数据在磁盘上的位置加以记彔和组织，通过在内存中的一些计算来取代对磁盘漫无目的的访问（空间换时间）n计算机自身原因计算机自身原因二、空间索引二、空间索引n空间数据管理的独有特征空间数据管理的独有特征l 空间数据具有海量数据特征，NASA每天产生TB级数据，如无索引管理将寸步难行，必将成为“数据坟墓”。l 由于地理数据的多维性，在任何方向上并不存在优先级问题。普通索引所针对的字符、数字等在一个维度上，任意两个元素，都可以确定其关系

14、(,=)2. 空间索引的概念空间索引的概念n依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。n作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。3.空间索引的分类空间索引的分类l基于格网的空间索引l基于树的空间索引结构l基于填充曲线的空间索引结构1)1)格网格网索引（索引（Grid Index)Grid Index)思路：将研究区域用横竖线条划分大小相等或不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。 格网索引（Grid Index)n步骤：1.将研究区域用横竖线条划分大小相等或不等的格网2.记录每一个格网所包含的空间实体和记录实体穿过的网格G G（1,21,2）：）：1 1G G（1,31,3）:2,8:2,8G G（2,32,3）:3,4