第5章-空间索引与优化分解

第五章空间索引与查询优化2013.4第五章空间索引与查询优化•第一节空间索引•第二节空间查询优化•一部工具书好比是一个微型数据库；工具书的索引，就好比进入它的数据库的钥匙。•数据库的索引用来快速访问一条特定查询所请求的数据，而无需遍历整个数据库。第一节空间索引定义•索引：–索引是一种独立的对象，用来快速地寻找那些具有特定值的记录–索引要占用存储空间–索引可以减少全表扫描，从而提高检索速度•例如：学生信息表student如下：学号姓名性别年龄系别001aaa男19计算机002bbb男20城环系003ccc女19城环系004ddd男18中文系005eee女18中文系006fff女20计算机•查询005号学生的信息：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开销大。•索引方法：记录河流和省界的外接矩形。用外接矩形进行比较。空间属性表描述要素的一般信息，空间索引表描述要素所在格网的信息，要素描述表描述要素的点数，范围等信息，三张表通过FID（FeatureID）关联定义•空间索引：–空间索引就是指依据空间对象的位置和形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。•空间索引的基本思想，也是空间查询的基本思想，即近似体的使用。•让索引结构按照一个或多个空间码来管理对象，这些空间码是比对象本事更简单的几何对象。•常见的空间索引：–对象范围索引–格网索引–四叉树索引–R树和R+树索引–BSP树索引一、对象范围索引•在记录每个空间实体的坐标时，记录包围每个空间实体的外接矩形的最大最小坐标。•在检索空间实体时，根据空间实体的最大最小范围，预先排除那些没有落入检索窗口内的空间实体，仅对那些外接矩形落在检索窗口的空间实体作进一步的判断，真正落入窗口内的空间实体。ABCEFD基于实体范围的空间数据检索•这种方法没有创建真正的空间索引文件，而是在空间对象的数据文件中增加了矩形范围，主要依靠空间计算进行判别。•查询时仍需要对整个数据文件的空间对象进行检索，只是某些对象可以通过矩形范围予以直接判别，而有些对象仍需要进行复杂计算才能判别。•虽然该方法仍需要花费大量时间来进行空间检索，但随着计算机的处理速度的加快，这种方法在一定程度上能够满足查询检索的效率要求对象范围索引IDXmaxXminYmaxYmin1…………2…………3………………………空间对象不被检索Xmax≤XWORXmin≥XEORYmax≤YSORYmin≥YN空间对象被检索Xmax≥XWandXmin≤XEANDYmax≥YSandYmin≤YN空间对象集合123456检索窗口YNXWXEYS4xmaxxminyminymaxxy•在进行空间范围查询时，分为两级过滤（筛选）：•初次过滤根据空间要素外包络矩形来过滤掉大部分不在查询范围的空间要素；•第二级过滤则用查询空间范围直接和初次过滤结果集中空间要素的二进制边界坐标比较，从而得到查询的准确结果。对象范围索引5123412312二、格网索引•将研究区域用横竖线条划分大小相等和不等的格网，记录每一个格网所包含的空间实体•用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体•通常是把整个数据库数值空间划分成32×32（或64×64）的正方形网格，建立另一个倒排文件——栅格索引。–每一个网格在栅格索引中有一个索引条目(记录)，在这个记录中登记所有位于或穿过该网格的物体的关键字。ABCDEF2123293153556163202228305254606217192527495157591618242648505658571315373945474612143638444613911333541430281032344042Peano键空间对象7B12E13E14E15E24E25A,E26E27E32D33D35D,F37E38D39E45E50E51E54C55C56E57E60C空间对象Peano键集A25-25B7-7C54-55C60-60D32-33D35-35D38-38E12-15E24-27E37-37E39-39E48-51E45-45E56-57F35-35空间索引对象索引检索原理：•第一阶段（RDBMS完成）：–接收SQL语句，获取空间过滤器的封装边界–检测空间过滤器的封装边界跨越的网格–到空间索引表中检索出封装边界所在网格内的要素•第二阶段：–几何过滤器的封装边界与第一阶段检索出的要素的边界相比较，找出具有重叠关系的要素•第三阶段–几何过滤器的坐标与第二阶段检索出的要素的边界比较，找出边界在几何过滤器内的要素•第四阶段：–几何过滤器的坐标与第三阶段检索出的要素的比较，找出最终在几何过滤器内的要素类ABCDEFGH6713154512141391102810ABCDEFGH6713154512141391102810第一阶段:(1)接收SQL语句，获取空间过滤器的封装边界(2)检测空间过滤器的封装边界跨越的网格(3)到空间索引表中检索出封装边界所在网格内的要素CEFGH6713154512141391102810第二阶段:几何过滤器的封装边界与第一阶段检索出的要素的边界相比较，找出具有重叠关系的要素EFGH6713154512141391102810第三阶段:几何过滤器的坐标与第二阶段检索出的要素的边界比较，找出边界在几何过滤器内的要素EFGH6713154512141391102810第四阶段:几何过滤器的坐标与第三阶段检索出的要素的坐标比较，找出最终在几何过滤器内的要素类•按格网法对空间数据进行索引时，所划分的格网数不能太多，否则，索引表本身太大而不利于数据的索引和检索三、四叉树索引•二维空间范围被划分为一系列大小相等的棋盘状矩形，即将地理空间的长和宽在X和Y方向上进行2N等分，形成2N×2N的网格，并以此建立N级四叉树。•四叉树是具有一个根节点,其中的每个中间节点都有四个孩子。四叉树的每个节点对应一个正方形。四叉树及其子分割•在建立四叉树索引时，根据所有空间对象覆盖的范围，进行四叉树分割，使每个子块中包含单个实体，然后根据包含每个实体的子块层数或子块大小，建立相应的索引。•在四叉树索引中，大区域空间实体更靠近树的根部，小实体位于叶端，以不同的分辨率来描述不同实体的可检索性用线性四叉树组织的空间索引57E1315GB46121413028AFDCPeano边长空间对象04E02D01A41F82C151G,B•第一阶段（RDBMS完成）：–接收SQL语句，获取空间过滤器的封装边界–将空间索引四等分，每一份与空间过滤器的封装边界的边界比较，取出与空间过滤器的封装边界没有重叠的网格（这些网格不再分）–将得到的部分继续四等分，与空间过滤器的封装边界的边界比较。•第二阶段：–几何过滤器的封装边界与第一阶段检索出的要素的边界相比较，找出具有重叠关系的要素•第三阶段–几何过滤器的坐标与第二阶段检索出的要素的边界比较，找出边界在几何过滤器内的要素•第四阶段：–几何过滤器的坐标与第三阶段检索出的要素的比较，找出最终在几何过滤器内的要素类检索原理：ABCDE四、BSP树索引•BSP树（BinarySpacePartitionTree）：–空间二叉树算法–对于要处理的一组空间对象，选择一个平面，将该对象分成两组（如果某个对象与该平面相交，则用这个平面将这个对象分成两个对象），作为该节点的两个孩子，然后分别对两个对象用相同的方法，直到满足一个特定的条件（通常是到节点上只有一个对象）为止。一般来说，选择的平面尽量不要把同一对象分成两个。•原理：–第一阶段•（1）接收查询语句，从中获取空间过滤器的封装边界；•（2）以空间过滤器封装边界的第一条边为界，将空间索引表分成两部分，取空间过滤器一侧的要素进行索引；•（3）按某一方向，选择第二条、第三条和第四条边为边界，分别除去在封装边界外测的要素–第二阶段•将空间过滤器的几何坐标和第一阶段选择出的要素的封装边界进行比较，得到索引结果–第三阶段•将空间过滤器的几何坐标和第二阶段选择出的要素的几何坐标进行比较，得到最终的索引结果。B树•对于一维升序或降序数据序列（假设其个数为N）来说，可以采用两分检索的方法来迅速地找到需要插入或删除元素的位置。•顺序表：–插入一个元素，需要将其以下的数据均进行后移–删除一个元素，需要将以下的数据进行前移。•提高插入和删除的工作效率，研究者提出了多种解决方法，B树就是其中较好的一种方案。•B树是由一系列节点所构成•它的每一个节点均由2m个数据域和2m+1个指针域所构成•每个节点的数据从左向右成升序排列•一般情况下，B树的每个节点中的数据域不一定存放满数据，但基本上每个节点存放的数据数大于m个。例如：插入数据0.660.66•由此可以看出：–B树中同一键值不会出现多次–并且它有可能出现在叶结点，也有可能出现在非叶结点中。–因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树–B+树是B树的变形–要求所有的信息都在叶子节点上–B+树的所有关键字都出现在叶结点上，上面各层结点中的关键码均是下一层相应结点中最大关键码的复写–B+树的键在非叶结点中也有可能重复出现，以维持B+树的平衡。R树–R树（ReferenceTree）–R树是处理空间数据的B+树的改进，它像B+树一样，是一个高度平衡的数据结构。–R树算法是由美国加州大学的AntommGuttman教授在1984年提出的一种空间数据库动态索引算法，现已成为空间数据库索引中应用最广泛的算法之一。–R树较好地解决了许多传统算法未解决的空间数据动态索引问题。R树•R树：–称为参考树，是以空间要素的封装边界作为参考，从树根（也就是所有空间对象的几何）开始，对空间要素进行分组，每一组作为根节点的孩子节点，依此类推，直到不可再分（即分到单个要素作为孩子节点，也就是叶节点）。–全部分组过程中，每一分组的数量视空间对象的分布情况（即各封装边界的组合程度）确定。•R树的每个结点不存放空间要素的值：•叶结点–由多个(Rect,OID)数据项组成–存储该结点对应的空间要素的外接矩形和空间要素标识。•其中OID为指向空间对象的具体数据指针•Rect为对象OID的MBR•非叶结点–由多个(Rect,child)结构的数据项组成–存放其子女结点集合的整体外接矩形和指向其子女结点的指针。•child为子结点指针•Rect为与子结点child相关的MBR。•让空间上靠近的空间对象拥有尽可能近的共同祖先,能提高R树的查询效率。•因此在组织R树的时候,尽可能的让空间对象的空间位置的远近体现在其最近共同祖先的远近。•形象的说就是让聚集在一起空间对象尽可能早的组合在一起。R树结构示意图原理•第一阶段（RDBMS完成）：–接收查询语句，获取空间过滤器的封装边界–从树根R开始，将空间过滤器的封装边界与要素的封装边界相比较，首先选出R–继续遍历，找出具有重叠关系的R1–依此类推，直至遍历到树的叶节点•第二阶段：–几何过滤器的坐标与第一阶段检索出的要素的边界比较，找出边界在几何过滤器内的要素•第三阶段–几何过滤器的坐标与第二阶段检索出的要素的比较，找出最终在几何过滤器内的要素类•插入：–向R树中插入一个数据,实际上是插入该数据的MBR。当所插入的叶结点中已经没