第5章-空间索引与优化分解ppt课件.ppt

《第5章-空间索引与优化分解ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章空间索引与查询优化2013.4第五章空间索引与查询优化第一节空间索引第二节空间查询优化一部工具书好比是一个微型数据库；工具书的索引，就好比进入它的数据库的钥匙。数据库的索引用来快速访问一条特定查询所请求的数据，而无需遍历整个数据库。第一节空间索引定义索引：索引是一种独立的对象，用来快速地寻找那些具有特定值的记录索引要占用存储空间索引可以减少全表扫描，从而提高检索速度例如：学生信息表student如下：学号姓名性别年龄系别001aaa男19计算机002bbb男20城环系003ccc女19城环系004ddd男18中文系005eee女18中文系006fff女20计算机查询005号学生的信息：

2、SELECT*FROMstudentWHERE学号=‘005’学号姓名性别年龄系别001aaa男19计算机002bbb男20城环系003ccc女19城环系004ddd男18中文系005eee女18中文系006fff女20计算机学号姓名性别年龄系别001aaa男19计算机002bbb男20城环系003ccc女19城环系004ddd男18中文系005eee女18中文系006fff女20计算机建立索引学号位置001002003004005006例如：查找经过河南省的所有河流。常规方法：检查所有河流和河南省省界是否相交。缺点：用实际空间对象比较，算法复杂，计算开销大、IO开销大。索引方法：记录河流和

3、省界的外接矩形。用外接矩形进行比较。空间属性表描述要素的一般信息，空间索引表描述要素所在格网的信息，要素描述表描述要素的点数，范围等信息，三张表通过FID（FeatureID）关联定义空间索引：空间索引就是指依据空间对象的位置和形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。空间索引的基本思想，也是空间查询的基本思想，即近似体的使用。让索引结构按照一个或多个空间码来管理对象，这些空间码是比对象本事更简单的几何对象。常见的空间索引：对象范围索引格网索引四叉树索引R树和R+树索引BSP树索引一、对

4、象范围索引在记录每个空间实体的坐标时，记录包围每个空间实体的外接矩形的最大最小坐标。在检索空间实体时，根据空间实体的最大最小范围，预先排除那些没有落入检索窗口内的空间实体，仅对那些外接矩形落在检索窗口的空间实体作进一步的判断，真正落入窗口内的空间实体。ABCEFD基于实体范围的空间数据检索这种方法没有创建真正的空间索引文件，而是在空间对象的数据文件中增加了矩形范围，主要依靠空间计算进行判别。查询时仍需要对整个数据文件的空间对象进行检索，只是某些对象可以通过矩形范围予以直接判别，而有些对象仍需要进行复杂计算才能判别。虽然该方法仍需要花费大量时间来进行空间检索，但随着计算机的处理速度的加快，这种

5、方法在一定程度上能够满足查询检索的效率要求对象范围索引IDXmaxXminYmaxYmin1…………2…………3………………………空间对象不被检索Xmax≤XWORXmin≥XEORYmax≤YSORYmin≥YN空间对象被检索Xmax≥XWandXmin≤XEANDYmax≥YSandYmin≤YN空间对象集合123456检索窗口YNXWXEYS4xmaxxminyminymaxxy在进行空间范围查询时，分为两级过滤（筛选）：初次过滤根据空间要素外包络矩形来过滤掉大部分不在查询范围的空间要素；第二级过滤则用查询空间范围直接和初次过滤结果集中空间要素的二进制边界坐标比较，从而得到查询的准确结

6、果。对象范围索引5123412312二、格网索引将研究区域用横竖线条划分大小相等和不等的格网，记录每一个格网所包含的空间实体用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体通常是把整个数据库数值空间划分成32×32（或64×64）的正方形网格，建立另一个倒排文件——栅格索引。每一个网格在栅格索引中有一个索引条目(记录)，在这个记录中登记所有位于或穿过该网格的物体的关键字。ABCDEF21232931535561632022283052546062171925274951575916182426485056585713153739454746121436

7、38444613911333541430281032344042Peano键空间对象7B12E13E14E15E24E25A,E26E27E32D33D35D,F37E38D39E45E50E51E54C55C56E57E60C空间对象Peano键集A25-25B7-7C54-55C60-60D32-33D35-35D38-38E12-15E24-27E37-37E39-39E48-51E45-45E56-5