空间索引结构
3、区域（窗口）查询：查找含在区域内、
与区域相交或部分位于区域中的所有空间对象， 窗口是一个特殊的区域。
4、K-最邻近查询：给定一个参照对象（点、 线或区域），查询距离参照对象最近的K 1个 空间对象。 5、空间关系查询：相交、相邻、包含等拓 扑关系查询，方位关系和基于距离的各种查询。
可索引点对象和对象的MBB，能够与B+树简
单集成，在商用数据库Oracle中已实现。
均匀网格索引
一、均匀网格的特征
设几何对象均为点对象。研究区域为一个
[Sx*Sy]大小的空间，将其划分为nx*ny个相同大 小的网格，每个网格的边长为Sx/nx*Sy/ny，起始 坐标为(Xo,
物理页，每个网格中的点存入相应的磁盘页中。 每个索引单元包含的索引项数量是有限制的，
不能超过一个物理页的存储容量。
均匀网格索引
如图7-3，索引组织成2D数组DIR[1:nx,1:ny]形式的目 录表，每个目录项DIR[i，j] 对应一个索引单元。一个索引 单元包含形式为[OID, PageID]的多个索引项，存储为一个 物理页。OID为空间对象的主码，PageID为该索引单元对 应的物理页标识。
图7-8 对象14的插入
网格文件索引
2、插入对象15 图7-9为目录不分裂而磁盘页溢出的情况。 插入前DIR[3，2]和DIR[3，3]同指向p4，将对象15分别插入 DIR[3，2]和DIR[3，3]中。插入后DIR[3，2]和DIR[3，3]中的索引 项均不超过4个，目录不用分裂，但磁盘页p4溢出。创建新页p7， DIR[3，2] 指向p4，DIR[3，3] 指向p7。
Back
空间索引结构
空间索引技术是提高空间数据查询和各种
空间分析效率的关键技术。空间索引可缩小 空间数据的搜索范围，使访问不需要遍历整 个空间数据集。 索引文件中的数据称为索引数据，索引结 构是索引数据的数据结构及索引创建与维护 算法的总称。 空间索引结构是按照空间数据在空间分布 上的特性来组织和存储索引数据的索引结构。
空间索引结构
空间索引结构应满足下列三个要求： 一、存储效率高： 相对于被索引的数据集而言，索引数据的数 据量应尽量小。否则，访问索引数据可能成为数 据查询与更新的效率瓶颈。 二、查询效率高： 选择良好的索引数据结构，设计具体的基于 索引的空间访问方法（SAM Spatial Access Method），高效实现以下的查询： 1、点选择：从数据集中找出包含给定点的所 有空间对象。 2、范围查询：查询与给定对象间的距离小于 某个给定值的所有空间对象。
图7-9 对象15的插入
网格文件索引
（二）点查询算法 1、工作过程 第一步：给定点坐标P(xp，yp)，沿X，Y两个 方向在Sx和Sy中查找P(xp，yp)位置，得到含有P 的网格单元。 第二步：进行一次磁盘操作将这个索引单元对 应的磁盘页调入内存，读取该页所存对象的(MBB， OID)，构成集合E。对E中的每个对象e，测试 e.mbb是否含有点P。 第三步：对于包含点P的e.mbb，通过e.oid获取 其几何边界数据，精确测试P是否位于e.oid的几何 边界之内。
网格文件索引
图7-5均匀网格文件的插入
网格文件索引
网格文件索引
网格文件索引
三、格网文件索引MBB 用网格文件对MBB进行索引，最简单的情况是每个覆盖MBB的 网格单元都保存该MBB的索引项。MBB与网格单元的关系有三种： MBB包含网格单元、网格单元与MBB相交、网格单元包含MBB。前两 种情况，每个网格单元都建立MBB的索引项，一个MBB有多项索引。 例子：有15个MBB，每页的最大容量为4。图7-6为用均匀网格建 立的索引：
均匀网格索引
格网分辨率的选择取决于被索引点对象的数量。 假设共有N个点对象，每页存储的最大点数为M， 则至少需要有N/M个网格。如果某个网格中的点数 超过M，多出的点放到溢出区，溢出区与索引区域 用指针相连。 所有的网格共用一个溢出区，溢出区可能由多 个磁盘页连接成溢出区链。如果o点存储在溢出区链 的第q页，则点查询的I/O数为q。最坏的情况下，所 有点都位于同一网格中，索引结构为磁盘页的线性 列。点的频繁插入会导致较长的溢出链，而点删除 会导致空页。对于某些具体分布，这种索引不能满 足磁盘存储的要求。
网格文件索引
2、例子：图7-10为一个格网文件点查询的例子。点P位于 DIR[3，2]范围之内，对应的磁盘页p4中含有4个索引项。将p4 页调入内存，对其包含的4个mbb分别进行测试，其中8和12的 mbb中包含了点P。根据对象标识8和12取出各自的几何边界数 据，精确测试对象8和12，求出包含点P的对象12。
空间索引技术的基本原理
空间索引技术的基本原理是采用基于空间 位置或基于空间对象的分割方法，把研究空间 划分为若干区域，每个区域为一个索引单元， 存储多个空间索引项，按照空间位置邻近的对 象其索引项的位置也应该邻近的原则来组织空 间索引数据。 空间索引按照对空间的划分方式分为空间 驱动的索引和数据驱动的索引；按照索引文件 的数据结构又分为线性索引和非线性索引。
空间索引技术的基本原理
空间对象的几何形状错综复杂，表示几何形状的坐 标序列是变长的，直接以形状数据为索引字段将导致索 引项很复杂。为此，首先将空间对象的几何形状采用某 种近似的简单图形来表示，平行于坐标轴且包含特定空 间对象的最小外接矩形MBB（Minimal Bounding Box） 或MBR(Minimum Bounding Rectangle) 是空间对象几 何形状的一种近似表示。 以 [MBB，OID，PRT]为索引项建立空间索引，可 使每个空间索引项具有固定长度。其中：OID为对象标 识，MBB为对象的最小外接矩形，PRT为指向几何数据 的指针，OID直接将MBB映射到存放几何形状和属性的 物理页。
图7-3 均匀网格
均匀网格索引
（二）基于均匀网格索引的空间访问 1、插入新点：假设新点的坐标为（x，y），计算新点 所在网格（索引单元）的行列号。新点的索引目录项为 DIR[i，j]，假设对应的磁盘页DIR[i，j].PageID为(a，b)所 在的页P(a，b)，将新点插入P(a，b)页中。 2、点查询：假设鼠标当前位置的坐标为 (x，y)，计算 鼠标位置所属索引单元的行列号i=(X-Xo)/(Sx/nx)+1和j=(YYo)/(Sy/ny) +1，读入对应的磁盘页DIR[i，j].PageID，扫 描该页中所有点对象，判断哪些点对象与(x，y)点重叠。 3、窗口查询：计算窗口W覆盖的网格集合S={Ci,j}， 对S中的每个读取DIR[i，j].PageID，返回这些页中包含的 所有点对象，即为窗口W范围内包含的点对象。
图7-10 基于网格文件的点查询
网格文件索引
（三）窗口查询算法 工作过程如下： 第一步：计算所有覆盖窗口的索引单元。 第二步：扫描每一个索引单元，调入相应的磁盘页。读入每 个磁盘页中的对象，排序并去掉重复对象。求出那些落入窗口中， 或与窗口相交的mbb。 第三步：根据各自的对象标识取出这些mbb对应的几何边界， 精确检测每个对象是否位于窗口中或与窗口相交。 （四）总结 用网格文件索引MBB，大多数情况下比较理想，但也存在很 多问题： 1、对象的多重索引增加了索引表的容量，数据集越大越严 重，索引单元接近MBB大小时，情况就更严重。 2、索引表容量越大，查询重复项的代价越高。 3、算法的效率依赖于索引表位于内存中的假设，如果索引 表很大，一部分要存入磁盘，管理将变得复杂，效率会受影响。
网格索引
网格索引是一种空间驱动的非线性索引结 构，其基本特征是用正方形或矩形格网对研究 区域的2D空间进行划分，每个网格单元为一 个索引单元，索引多个空间对象，索引单元按 行列号组织成2D目录。 网格索引包括均匀网格索引和网格文件索 引，均匀网格适合于索引空间点对象；网格文 件是均匀网格的改进，是一种多关键字索引，
空间驱动的索引结构
空间驱动索引结构的主要特征是采用
某种格网对2D空间进行划分，将空间划分
成小区域，每个小区域为一个索引单元， 每个索引单元包含多个索引项，每个索引 项索引一个空间对象。 索引单元按照一定的数据结构来组织。
如果组织成线性结构，则相应的空间索引
为线性索引，如果组织成非线性结构，则
相应的空间索引为非线性索引。
6、其他查询：将满足一定空间条件的两个
空间对象集合进行空间连接，空间集合运算等也 是一种空间访问。
空间索引结构
三、更新效率高： 数据对象的增加、修改和删除将导致索引数据 更新，索引数据与被索引的数据集必须保持一致。 索引数据的更新操作包括：插入索引项、删除 索引项和修改索引项（先删除再增加）。数据集经 常变化时，需要考虑新增索引项和删除索引项时， 索引结构的快速更新能力。 很难设计一种空间索引结构同时能提供高效的 存储、高效的查询和高效的更新，实际应用中总是 牺牲某些方面的效率来换取另外方面的效率。 索引结构可分为静态索引和动态索引结构，还 分为内存索引和外存索引，外存索引需要考虑磁盘 页面访问的效率瓶颈问题。
均匀网格索引
如图7-4中例子，每个网格所存的最大点数M=4， k,l,m,n,o五个点对象位于同一个网格中，对应于磁盘 页P。将k,l,m,n四个点放入P页，o放入溢出区，将溢
出区与P页相连。
图7-4 均匀网格中的溢出页
网格文件索引
二、点对象的格网文件 格网文件与均匀格网的相同之处是采用平行于坐标轴的格网 对空间进行完全划分，每个网格单元为一个索引单元，索引单元 组织成2D目录形式。与均匀格网不同的是，每次发生溢出时，动 态的将网格单元在横向或纵向上分裂为两个单元，可根据网格单 元中点对象的分布情况来选择进行纵向还是横向划分；网格文件 中的网格单元为大小不相同的矩形单元，多个网格单元可对应同 一个磁盘页。 （一）格网文件的数据结构 格网文件由三种数据结构来实现，索引目录DIR是一种与均 匀网格中的索引目录类似的2D数组，差别是两个相邻单元可共享 同一磁盘页；Sx,Sy是两个线性数组，表示沿两坐标轴的划分。 图7-5中的例子描述了这种结构，假设网格的最大容量M=4。