空间索引结构(学生)

1、第七章 空间索引结构空间索引技术是从空间数据库中获取空间数据的有效方法，是提高空间数据查询和各种空间分析效率的关键技术。建立空间索引是为了缩小空间数据的搜索范围，以便在空间数据查询时不必遍历整个空间数据集，只访问空间索引数据便可快速得到一条特定的空间查询语句所请求的空间数据，或得到包含全部空间查询结果的一个较小的空间数据集。索引文件中包含的数据称为索引数据，索引结构是索引数据的数据结构及索引创建与维护算法的总称。空间索引结构是按照空间数据在空间分布上的特性来组织和存储索引数据的索引结构。一种良好的空间索引结构应满足下列三个要求：一、存储效率高：相对于被索引的数据集而言，索引数据的数据量应尽量小

2、。否则，访问索引数据可能成为数据查询与更新的效率瓶颈。二、查询效率高：空间索引结构需要选择良好的索引数据结构，设计具体的基于索引的空间访问方法（SAM Spatial Access Method），必须能够高效的实现以下几种基于位置的查询：1、点选择：从数据集中找出包含给定点的所有空间对象。2、范围查询：查询与给定对象间的距离小于某个给定值的所有空间对象。3、区域（窗口）查询：查找含在区域内、与区域相交或部分位于区域中的所有空间对象。窗口是一个特殊的区域，窗口查询是GIS中最常用、最基本的查询。4、K-最邻近查询：给定一个参照对象（点、线或区域），查询距离参照对象最近的K ³ 1个空

3、间对象。5、空间关系查询：相交、相邻、包含等拓扑关系查询，方位关系和基于距离的各种查询。6、其他查询：将满足一定空间条件的两个空间对象集合进行空间连接，空间集合运算等也是一种空间访问。三、更新效率高：许多GIS应用中会涉及海量且不断变化的空间数据集。数据集中数据对象的增加、修改和删除将直接导致索引数据的更新，索引数据与被索引的数据集必须保持一致，才能保证基于索引数据的查询结果的正确性。索引数据的更新操作包括：插入索引项，将新数据对象的索引项添加到索引数据中；删除索引项，把数据对象的索引项从索引数据中删除；修改索引项，在索引数据中先删除再增加该数据对象的索引。数据集经常变化时，要求其索引数据的更

4、新开销不要很大，特别要避免更新时引起的索引重组。因此，需要考虑新增索引项和删除索引项时，索引结构的快速更新能力。很难设计一种空间索引结构同时能够提供高效的存储、高效的查询和高效的更新，实际应用中总是牺牲某些方面的效率来换取另外方面的效率。索引结构可分为静态索引和动态索引结构。静态索引结构针对静态不变的数据，索引只建一次，不需要更新，强调索引数据的存储效率和查询效率，不强调索引更新的效率。动态索引结构强调数据在动态更新过程中保证较高的查询效率和索引空间存储效率，往往以牺牲索引更新效率为代价，这种牺牲是有限度的。索引结构还分为内存索引和外存索引，外存索引需要考虑磁盘页面访问的效率瓶颈问题。这里主要

5、研究面向海量空间数据的、2D空间对象的外存索引结构。7.1空间索引分类非空间数据库中存储的数据为结构化数据，通常以主关键字建立索引文件，以非主属性建立倒排文件，索引项按自然数序列或字符顺序排列。空间数据库存储的数据为结构复杂、不能完全结构化的空间数据，为了支持基于位置的各类查询和分析，需要以表示空间对象几何形状的坐标数据为索引字段来建立空间索引。非空间数据库的索引结构不能满足空间数据库的索引需求，必须研究和设计专用的空间索引结构和基于索引的空间访问方法（SAM Spatial Access Method）。7.1.1非空间索引与SAM非空间索引结构一般为B树和hash文件结构，这种索引结构可以

6、准确的定位和查找所需数据，复杂度为对数函数。一、索引的假设和要求（一）B树和hash文件结构遵从的假设1、被索引的数据集所占空间远远大于内存空间；2、磁盘访问比内存访问慢得多；3、对象按物理页分组，页是内存和外存交换数据的单位（大小为1K到4K），读/写一页为一次I/O操作。4、访问一个具体对象时，该对象所在页可能在内存中，或不在内存中需要调入内存。非空间数据库的索引操作中，CPU时间与I/O操作时间相比可忽略不计，访问方法的效率用I/O数衡量。空间索引的操作中，有些情况下需考虑CPU时间，但不考虑页的缓存，使用一页时才调入内存。（二）SAM应满足的要求空间索引是依据空间对象的空间位置、几何形

7、状及空间分布特征，按一定顺序排列的一种数据结构。空间访问方法SAM的设计基于B树和hash表相同的假设，但B树和hash表均不适合于空间索引。SAM应满足下列要求：1、时间复杂度：点选择和区域查询应具有线性复杂度。SAM访问一个数据集合的子集所用的时间，应小于以集合元素数量的线性函数为复杂度的序列查找算法。2、空间复杂度：如果被索引的集合占据n页，索引的大小应该是n级的。3、空间索引结构必须考虑动态性：适合于空间索引项的增加和删除，大多数空间索引结构在索引查找方面是高效的，复杂度为被索引集合中元素数量的对数。二、非空间数据库中的B+树索引B+树是B树的一个变种，B+树是一个平衡树，所有叶子位于

8、相同的深度。B+树的每个结点为一个索引单元，存贮多个索引项，对应磁盘上一个物理页，每个索引单元存贮索引项的数量由物理页容量和索引项大小来确定。结点上每个索引项的内容为KEY，PRT，叶结点的PRT指向关键字为KEY的数据对象，非叶结点的PRT指向孩子结点。每个结点中的索引项按关键字升序排序，非叶结点中每个索引项左子树中的关键字小于等于该索引项的关键字，右子树中的关键字大于该索引项的关键字。图7.1为一个B+树索引结构的例子： 例子：有一组关键字集合2，3，7，9，10，13，15构成的索引文件，索引数据采用B+树结构来组织。假设每个结点最多存贮四个索引项，结果如图7.1a所示。 图7-1 B树

9、：（a）插入23,OID前，(b) 插入23,OID后1、索引的查找索引查找从树根开始，通过比较关键字大小，查找相应的子树，直到叶结点。一次查找中读入物理页的数量等于树的深度，复杂度是被索引数据集大小的对数。2、插入索引项插入新的索引项E = 23，PRT。1）从根结点搜索，该索引项应插入到第二个叶子中。2）插入时该叶结点满了，必须分裂，原结点的一部分索引项保留在原索引单元内（9，10，13），另一部分索引项和E形成一个新的叶结点（15，23）。3）按照B+树的定义，应将左边叶结点（9，10，13）中最右边一个关键字13插入父结点中，插入新索引项后的B+树如图7.1b所示，仍然是平衡树。B+树

10、是一种较好的外存空间索引结构，时间复杂度是数据集合中元素数量的对数，空间复杂度使索引空间的利用率为50%以上，动态性能支持随机插入和删除。B+树的上述优点是以关键字有序为基础的，空间数据不具备这样的特点，不能简单照搬。7.1.2 空间索引分类空间索引技术的基本原理是采用基于空间位置或基于空间对象的分割方法，把研究查询空间划分为若干区域，每个区域为一个索引单元，存储多个空间对象的索引项。考虑到空间位置上的邻近度，按照空间位置邻近的对象其索引项的位置也应该邻近的原则来组织空间索引数据。空间索引支持的最主要的查询是定位查询和窗口查询。一、空间对象的近似空间对象的几何形状错综复杂，表示几何形状的坐标序

11、列是变长的，直接以坐标序列为索引字段建立的空间索引，其索引项很长且变长。为此，需要将空间对象的形状进行某种近似，平行于坐标轴的、包含特定空间对象的最小外接矩形MBB（Minimal Bounding Box）或MBR(Minimum Bounding Rectangle)就是空间对象几何形状的一种近似表示。以 MBB，OID 为索引字段建立空间索引，每个空间索引项具有固定的长度，最少包含三种成分MBB，OID，PRT，OID为对象标识，MBB为相应对象的最小外接矩形，PRT为指向几何数据的指针，OID直接将MBB映射到存放几何形状和属性的物理页。 空间索引介于空间计算算法与空间数据之间，用于过

12、滤大量与空间计算无关的数据，以提高空间操作的效率。SAM只加速了索引项中MBB的查找（过滤），在此基础上还要对几何图形进行精确查找。基于空间索引的空间查询分两步完成，第一步利用空间索引结构和空间访问方法SAM对数据集进行过滤（初选），在索引表中查找满足查询条件的MBB，结果为对象的一个超集（多个OID）。第二步对初选结果进行准确查找，在超集中通过空间计算算法，求取满足查询条件的精确对象。二、空间分割与空间索引单元划分建立空间索引的第一步是按照一定的方式将被查询空间分割成多个索引单元。有两种对空间进行划分的方法，形成两大类空间索引结构，很多SAM都属于这两类结构之一。1、空间驱动结构：采用基于空

13、间位置的分割方法，将研究区域的2D空间进行完全划分，划分为多个矩形或正方形范围，每个范围定义为一个空间索引单元，对象在2D空间的分布是独立的，对象按一定原则分配到不同的矩形单元。也可将研究区域的2D空间划分为多个凸多边形范围，每个凸多边形近似表示一个空间对象的几何形状。例如：将研究空间用规则的正方形格网进行分割，每个正方形网格为一个空间索引单元，索引多个空间对象。空间对象覆盖多个相邻的空间索引单元时，在其覆盖的每个索引单元中各有一个索引项，索引项中包含空间对象标识OID。2、数据驱动结构：是一种基于对象的分割，对2D研究区域的空间分割直接由分布在其中的空间对象来确定，对空间对象集合进行分割。每

14、个空间对象用它的最小外接矩形MBB近似表示，每个空间索引单元的形状也是一个矩形区域，它包含多个空间对象的最小外接矩形MBB。空间索引单元的面积大小取决于其索引的空间对象集合的面积、形状和分布，索引单元中存储空间对象的最小外接矩形MBB。基于对象的分割不是空间的一种完全划分。三、空间索引结构的具体分类综合现有研究及参考文献，可将主要的空间索引技术分类如下：R树点对象线性四叉树空间索引非线性索引线性索引网格空间索引基于树的索引基于凸多边形基于约束基于MBBR树系列树CELL系列BSP树CELL树CP树OS-CELL树PR树GPR树LUR树R+树R*树R-Link树Qr树Sr树TV树X树SDR树线性

15、映射结构网格文件图7-2 空间索引分类索引结构中，如果将2D或3D分布的空间索引单元，按照一定的方式组织成线性形式，相应的索引称为线性空间索引。相反，以非线性形式来组织空间索引单元，相应的索引称为非线性空间索引。一、线性索引线性索引主要有线性映射结构与线性四叉树。1、线性映射结构：首先，用均匀或不均匀的正方形格网对被索引空间区域进行划分；然后，采用填充曲线对索引空间进行填充（如Hilbert Curve曲线），取填充曲线编码为索引单元的序号，将索引单元按序号排序建立线性索引结构。这里，空间划分是基于位置的完全划分，建立的索引为空间驱动的、线性组织的、规则的网格空间索引结构。2、线性四叉树：每一

16、个空间对象用其MBB近似表示，对含有MBB集合的空间进行四叉树划分，划分后的不均匀网格作为索引单元，每个单元分别编号，叶结点根据编号组织成B-树结构，这种结构叫线性四叉树。二、非线性索引非线性空间索引按索引的逻辑组织方式分成网格空间索引和基于树的空间索引。（一）网格空间索引网格空间索引简称称网格索引，是基于位置的空间驱动结构。它将被索引空间用平行于坐标轴的横竖线条划分成大小相等或不等的网格，每个网格为一个索引单元，记录每个网格所包含的多个对象的标识。空间查询时，先计算出对象所在的网格，然后在网格中快速查询对象。网格索引分为均匀网格索引和网格文件索引，可以索引点对象及用MBB近似的其他类型的空间

17、对象。网格索引以二维数组结构来存储，是一种非线性空间索引结构。（二）基于树的空间索引基于树的空间索引是一种基于对象的数据驱动结构。首先采用某种几何形状近似算法，将被索引空间中的空间对象表示为其近似体，然后将近似体按确定规则组织成树形结构。基于树的空间索引按几何形状近似技术的不同可分为基于凸多边形的空间索引、基于约束的空间索引和基于MBB的空间索引。1、基于凸多边形的空间索引基于凸多边形的空间索引又称划分树结构，它将被索引空间划分成凸多边形，然后再对凸多边形进行同样的划分，直到该划分满足特定精度为止。用凸多边形近似表示对象的形状。（1）BSP树 BSP树是一种二叉树，它将被索引空间逐级进行一分为

18、二的划分，形成一棵二叉树BSP树。（2）CELL树、CP树、OS-CELL树 CELL树与BSP树相似，BSP树将被索引空间一分为二，CELL树则将被索引空间划分成多个凸多边形，然后依次再对每个凸多边形进行相似的划分，直到到达预定的精度为止，CELL树是一棵多叉树。CELL树与BSP树的相同之处是子空间相互间不覆盖，优点是磁盘1/0次数较少，但索引项中凸多边形的存储需较多空间，且进行几何形状的精确匹配时计算也较复杂。 CP树是CELL树的一种变种树，采用CELL树同样的空间划分方法，但允许子空间部分覆盖。特点是与R树相比，具有较小的子空间覆盖面积，磁盘1/0次数较少，同样索引项中对凸多边形的存

19、储需较多的空间，且进行空间对象的精确匹配时计算较复杂。 OS-CELL树也是CELL树的一种变种树，只是针对CELL树中存在的特大空间对象，对CELL树进行改进、完善和优化。由于特大空间对象占据较大的被索引空间，其在CELL树中可能会被分割成多个凸多边形，当特大空间对象较多时，CELL树的叶节点分裂会相当频繁，使CELL树的重构时间增多，有效访问速度变慢；每个特大空间对象可能存放到多个磁盘块中，增加CELL树的高度，从而增加磁盘1/ 0次数，恶化CELL树的搜索性能。OS-CELL树分配特大盘块专用于存储特大空间对象，在父节点中添加指向该特大盘块的指针。对普通几何对象而言，OS-CELL树的特

20、点与CELL树相同。2、基于约束的空间索引其代表O树采用空间近似算法，将几何对象按axby=c(a，b)，c (a，b) (-1，0，1)表示为一组约束表达式，相应于笛卡尔坐标空间中的六条曲线中的某种组合，然后根据空间对象间的空间关系建立空间索引树。特点是能够自然地表示空间对象间的空间关系，但对空间对象的精确匹配需较多的计算。3、基于MBB的空间索引基于MBB的树状空间索引均将空间对象近似为其MBB，根据MBB间的空间关系建立相应的树形结构，这类空间索引主要指R树系列。自1984年Guttman提出R树以来，学者根据不同应用对R树的需求，对R树进行了各种改进，形成了诸多R树的变种，如图7-2所

21、示。当前主要的空间索引结构归纳为网格索引、线性四叉树、R树结构、划分树结构和线性映射结构等类型。本章主要探讨这几类空间索引的索引结构，索引建立和简单的查询操作。7.2 空间驱动的索引结构空间驱动索引结构的主要特征是采用某种格网对2D空间进行划分，将空间划分成小区域，每个小区域为一个索引单元，每个索引单元索引多个空间对象。索引单元按照一定的数据结构来组织，如果组织成线性结构，则相应的空间索引为线性索引，如果组织成非线性结构，则相应的空间索引为非线性索引。即空间驱动结构既包含线性索引，也包含非线性索引，非线性结构主要有网格索引，线性结构有线性四叉树和线性映射结构。7.2.1网格索引网格索引是一种空

22、间驱动的非线性索引结构，其基本特征是用正方形或矩形格网对研究区域的2D空间进行划分，每个网格单元为一个索引单元，索引多个空间对象，索引单元按行列号组织成2D目录。网格索引包括均匀网格索引和网格文件索引，均匀网格适合于索引空间点对象；网格文件是均匀网格的改进，是一种多关键字索引，可索引点对象和对象的MBB，能够与B+树简单集成，在商用数据库Oracle中已实现。一、均匀网格（一）均匀网格的特征设几何对象均为点对象。研究区域为一个大小的空间，将其划分为个相同大小的网格，每个网格的边长为，起始坐标为。每个网格为一个索引单元，对应于磁盘上一个物理页，每个网格中的点存入相应的磁盘页中。如图7-3，索引目

23、录表为一个2D数组DIR，每个目录项DIRi，j含有页标识PageID。图7-3 均匀网格（二）基于均匀网格索引的空间访问1、插入新点：假设新点的坐标为（x，y），计算新点所在网格（索引单元）的行列号，。新点的索引目录项为DIRi，j，假设对应的磁盘页DIRi，j.PageID为(a，b)所在的页P(a，b)，将新点插入P(a，b)页中。2、点查询：假设鼠标当前位置的坐标为 (x，y)，计算鼠标位置所属索引单元的行列号和，读入对应的磁盘页DIRi，j.PageID，扫描该页中所有点对象，判断哪些点对象与(x，y)点重叠。3、窗口查询：计算窗口W覆盖的网格集合S=，对S中的每个读取DIRi，j.

24、PageID，返回这些页中包含的所有点对象，即为窗口W范围内包含的点对象。 如果目录在内存中，点查询只需一次I/O。窗口查询的I/O数与窗口覆盖的网格数成正比。格网分辨率的选择取决于被索引点对象的数量。假设共有N个点对象，每页存储的最大点数为M，则至少需要有N/M个网格。如果某个网格中的点数超过M，多出的点放到溢出区，溢出区与索引区域用指针相连。如图7-4中例子，每个网格所存的最大点数M=4，k,l,m,n,o五个点对象位于同一个网格中，对应于磁盘页P。将k,l,m,n四个点放入P页，o放入溢出区，将溢出区与P页相连。所有的网格共用一个溢出区，溢出区可能由多个磁盘页连接成溢出区链。如果o点存储

25、在溢出区链的第q页，则点查询的I/O数为q。最坏的情况下，所有点都位于同一网格中，索引结构为磁盘页的线性列。点的频繁插入会导致较长的溢出链，而点删除会导致空页。对于某些具体分布，这种索引不能满足磁盘存储的要求。图7-4 均匀网格中的溢出页二、点对象的格网文件格网文件与均匀格网的相同之处是采用平行于坐标轴的格网对空间进行完全划分，每个网格单元为一个索引单元，索引单元组织成2D目录形式。与均匀格网不同的是，每次发生溢出时，动态的将网格单元在横向或纵向上分裂为两个单元，可根据网格单元中点对象的分布情况来选择进行纵向还是横向划分；网格文件中的网格单元为大小不相同的矩形单元，多个网格单元可对应同一个磁盘

26、页。 （一）格网文件的数据结构 格网文件由三种数据结构来实现，索引目录DIR是一种与均匀网格中的索引目录类似的2D数组，差别是两个相邻单元可共享同一磁盘页；是两个线性数组，表示沿两坐标轴的划分。图7-5中的例子描述了这种结构，假设网格的最大容量M=4。图7-5均匀网格文件的插入（二）构建网格文件的步骤第一步：只有四个对象，目录中只有一个网格c指向p1页。第二步：插入点a、b、c。1、在网格c插入a时，p1溢出。2、在中的处将网格c垂直划分成两个单元和，将c中原有的4个点划分到和两个单元中。3、创建一个新磁盘页p2，指向 p1页，指向p2页。4、将a和b插入单元对应的p1页，c插入单元对应的p2

27、页。 第三步：插入d1、在单元中插入点d时p1溢出。2、在中的处将和单元进行水平划分，水平划分为和。3、创建一个新磁盘页p3，将p1中原有4个点划分到p1和p3中，指向p1，指向p3。将点d插入单元对应的p1页。此时，水平线将没溢出的单元也水平划分为两个单元和，和指向同一个磁盘页p2。第四步：插入e和f两点。1、将e和f分别插入和单元，和没溢出，而p2溢出。2、分配一个新页p4。存入p4，存入p2。 （三）插入一个点时可能的三种情况 1、网格单元不分裂：磁盘页没满，只需读入页，插入点。 2、网格单元不分裂但磁盘页溢出：点n插入单元c时，与c相关联的磁盘页p满了，但p由多个单元引用。此时分配一个

28、新页，将p页中含在c单元里的点和新点n分配给新页，c单元的索引目录指向。 3、单元分裂且磁盘页溢出：新点插入时磁盘页满，且该页只有一个网格单元引用，此时网格单元沿x或y分裂。以沿x轴分裂为例：（1）在处分成和（该列的所有单元均分为两个），将分裂点的位置插入中。（2）创建一个新物理页，将原来中的点和新插入的点分配到和中，分别指向p和。（3）DIR中所有列号> i的列，都将列号+1。创建一个索引列号为“i +1”的新索引项。对所有的行，新单元与指向相同的物理页。格网文件克服了均匀网格的主要缺陷，点查询通过两次I/O操作就可完成（访问目录对应的页和读页数据）。该结构是动态的，缺点是对于大数据集

29、，目录会大到内存放不下的程度。三、格网文件索引MBB用网格文件对MBB进行索引，最简单的情况是每个覆盖MBB的网格单元都保存该MBB的索引项。MBB与网格单元的关系有三种：MBB包含网格单元、网格单元与MBB相交、网格单元包含MBB。前两种情况，每个网格单元都建立MBB的索引项，一个MBB有多项索引。例子：有15个MBB，每页的最大容量为4。图7-6为用均匀网格建立的索引：图7-6 基于MBB的均匀网格索引图7-7为用网格文件建立的索引：图7-7 基于网格文件的MBB索引对象的插入、删除与点索引相同，只是一个MBB可能具有多个索引项，分裂会更频繁。（一）索引项插入1、插入对象14如图7-8，将

30、对象14插入图7-7中的索引单元DIR1，3时，DIR1，3中的索引项超过4项，对应的磁盘页p5也溢出。在处对DIR1，3进行水平分裂，将存入中，现有3*（2+1）= 9 个目录项。目录单元DIR1，1和DIR2，1 同指向p1页，DIR1，2和DIR2，2同指向p3页。原来p5页中的对象由于对象14的插入，分裂成了p5和p6两页，DIR1，3指向p5，DIR2，3指向p6。对象5有两个索引项分别存储在p5和p6两页中，对象6 有四个索引项分别存储在p5、p6和p3中。图7-8 对象14的插入2、插入对象15图7-9为目录不分裂而磁盘页溢出的情况。插入前DIR3，2和DIR3，3同指向p4，将

31、对象15分别插入DIR3，2和DIR3，3中。插入后DIR3，2和DIR3，3中的索引项均不超过4个，目录不用分裂，但磁盘页p4溢出。创建新页p7，DIR3，2 指向p4，DIR3，3 指向p7。图7-9 对象15的插入（二）点查询算法1、工作过程第一步：给定点坐标P(xp，yp)，查找含有P的网格单元。对于均匀网格索引来说是常数时间，若用网格文件则分X，Y两个方向查找，复杂度是对数函数。第二步：进行一次磁盘操作将这个索引单元对应的磁盘页调入内存，读取该页所存对象的(MBB，OID)，构成集合E。对E中的每个对象e，测试e.mbb是否含有点P。第三步：对于包含点P的e.mbb，通过e.oid获

32、取其几何边界数据，精确测试P是否位于e.oid的几何边界之内。2、例子图7-10为一个格网文件点查询的例子。点P位于DIR3，2范围之内，对应的磁盘页p4中含有4个索引项。将p4页调入内存，对其包含的4个mbb分别进行测试，其中8和12的mbb中包含了点P。根据对象标识8和12取出各自的几何边界数据，精确测试对象8和12，求出包含点P的对象。点查询的I/O数是常数。图7-10 基于网格文件的点查询（三）窗口查询算法工作过程如下：第一步：计算所有覆盖窗口的索引单元。第二步：扫描每一个索引单元，调入相应的磁盘页。读入每个磁盘页中的对象，排序并去掉重复对象。求出那些落入窗口中，或与窗口相交的mbb。

33、第三步：根据各自的对象标识取出这些mbb对应的几何边界，精确检测每个对象是否位于窗口中或与窗口相交。窗口查询的I/Os与窗口的面积成正比。（四）总结用网格文件索引MBB，大多数情况下比较理想，但也存在很多问题：1、对象的多重索引增加了索引表的容量，数据集越大越严重，索引单元接近MBB大小时，情况就更严重。2、索引表容量越大，查询重复项的代价越高。3、算法的效率依赖于索引表位于内存中的假设，如果索引表很大，一部分要存入磁盘，管理将变得复杂，效率会受影响。7. 3数据驱动的索引结构空间驱动的索引结构将整个空间划分成小区域，每个小区域定义为一个索引单元，直接索引其中的空间对象或索引对象的MBB。数据

34、驱动的索引结构则按照空间对象的位置、范围和分布，来确定索引单元的位置和范围，索引单元的全集不一定覆盖整个空间。这里主要介绍R树系列和划分树。7.3.1 R树 R树是一种数据驱动的索引结构，是B树的扩展。与B树相比，R树是一棵由多层嵌套的外接矩形构成的平衡树，即R树的每个结点以范围矩形mbb或目录矩形dr的形式表示一个空间范围，它界定了一个空间索引区域，定义为一个空间索引单元。R树的每个结点都是一个空间索引单元，非叶结点包含其多颗子树的索引项，叶结点包含多个数据对象的索引项，本结点的范围矩形作为自身索引项的一部分存储在它的上层结点中。R树的每个结点对应一个物理页，每个结点只能包含k个索引项，mk

35、M，M是R树结点中包含索引项的最大数目，m是R树结点中包含索引项的最小数目，并限制2 £ m £ M/2。一、原始的R树R树的基本结构是一棵多层嵌套的、由外接矩形构成的平衡树。每个结点的索引区域表示成一个范围矩形，每个结点为一个空间索引单元，每个索引单元有k个索引项。叶结点的范围矩形为其内部多个数据对象mbb的最小外接矩形，非叶结点的范围矩形为其多个子结点范围矩形mbb的最小外接矩形。叶结点中存放多个数据对象的索引项，每个索引项的形式为ptr，mbb，oid，其中oid是数据对象的标识，mbb是数据对象的外接矩形，ptr指向存储该对象几何形状数据的磁盘位置。非叶结点中存放多

36、个子结点索引项，每个索引项的形式为ptr，mbb，nodeid，其中nodeid是指向子结点的指针，mbb为子树的目录矩形dr，ptr是子结点对应的磁盘页地址。（一）R树的性质1、根结点至少有两个子结点；2、所有的叶结点都处于同一层；3、除根结点外，R树中所有结点包含的索引项数目均在m，M之间，并限制2 £m£M/2。图7-26显示一棵m=2，M=4的R树。M的大小取决于索引项大小Size(E)和磁盘页大小Size(P)，。通常oid大于nodeid，因而，非叶结点和叶结点的M不同。给定M和m后，一个深度为d的R树最少可索引个对象，至多可索引个对象。相反，要索引N个对象，R

37、树的深度最大为，最小为。假设页的大小为4K，索引项的大小为20B（16B为mbb，4B为oid），m设为页容量的40%，则，。这种情况下，深度为1时可索引至少81*81=6561个对象，深度为2可索引81*81*81=531441到204*204*204=8489664个对象。对于million个对象，只需要三层，即访问三个磁盘页就可到达树叶，再读取相应的对象即可。（二）R树查询效率的优化R树允许兄弟结点间有区域重叠，因此，查询一个对象可能要访问多个分支，这是影响R树查询效率的主要因素。对R树查询效率的优化可考虑如下参数：1、查询区域：查询条件所覆盖的区域。2、重叠区域：兄弟结点间范围矩形相互

38、重叠的区域。重叠区域减少时，查询区域与重叠区域相交的概率减少，可减少查询时访问的分支数。3、死区域：被结点范围矩形覆盖但不被其子结点范围矩形覆盖的区域。死区域减少时，属于结点范围内的查询区域与其子结点范围矩形相交的概率增大，在该分支上找到目标数据的概率也增大，提高了分支选择的准确性。4、范围矩形周长：结点范围矩形四边长度之和。对于面积固定的矩形，周长越小，其形状越接近正方形，正方形的空间聚簇性好，易于填满父结点的范围矩形，所以减少子结点的范围矩形周长可减少父结点的死区域。5、结点利用率：结点的实际子结点数（或数据对象数）与最大子结点数（或数据对象数）之比。提高结点利用率可降低树的平均高度，对于

39、大区域查询，满足条件的数据对象数目很大，结点利用率高可在很大程度上减少结点访问数，从而提高查询效率。上述优化参数有些相容，有些互斥。一般来说，减少死区域的同时可能也减少了重叠区域，两者是相容的。而为了减少死区域，则要求结点的子结点数目能更自由，结点利用率可能会降低。减少死区域和减少重叠区域都要求结点外接矩形的形状更自由，结点范围就可能无法接近正方形。对于任意几何形状，减少周长一般也会影响到结点利用率，接近正方形的外接矩形更容易填满父结点范围矩形，也容易提高结点利用率。对于大区域查询，结点利用率对查询的影响远远大于其他三个因素。（三）基于R树的查询点查询和窗口查询几乎完全一样，这里只介绍点查询。

40、函数RTpointQuery实现两步：1、在每一层中查找各结点中所有含P点的子结点，因为外接矩形可以重叠，满足条件的子结点可能有多个，相同的方法直到叶结点。访问每个结点时可能发生两种情况：（1）该结点不包含P，即P落在非叶结点范围矩形的死区域，查找终止。（2）P点包含在该结点多个子结点的mbb中，这时要搜索每一棵子树，直到叶结点。2、顺序扫描第一步得到的所有叶结点，所有包含P点的数据对象的索引项mbb即为所求。图7-26显示了点查询的例子，查询访问了R，b，c，d四个结点，P点含在对象8和12的mbb中。图7-26 基于R-树的点查询（三）R树的插入操作1、插入步骤（1）从根结点向叶子搜索，如

41、某个结点的范围矩形包含被插入对象的mbb，则继续查找其子树，如果不包含则终止，重复此过程直到叶结点。（2）如果叶结点未满，则将新对象的mbb，oid插入叶结点；如果叶结点已满，则将叶结点分为裂为两页（重构的范围矩形），将M+1个索引项分配到两页中，在父结点f中修改的索引项（的范围矩形有变化），并插入的索引项。如果父结点f也满了，则重复上述的分裂，最坏的情况是直到根，此时树的深度增加一级。图7-27 对象15的插入2、插入举例（设M=4）（1）在图7-26中插入对象15：叶结点d的范围矩形中包含对象15的mbb，d中原有的索引项为11，12，13，将对象15直接插入叶结点d中，重构d结点的范围矩形，并改变d结点在根结点R中的索引项，插入结果如图7-27所示。（2）在图7-27中插入对象16：叶结点b的范围矩形中包含对象16的mbb，将对象16插入到叶结点b中。b中原有的索引项为3，4，7，10，b结点满了，应分裂为b和e两个结点，将3，4，7分配在b中，10，16分配在e中。重构结点b的范围矩形，修改b在根结点R中的索引项。生成e的范围矩形，将e的索引项插入根结点R中。此时根结点R已满，将根结点R