《空间数据组织与分析》

结课论文

题目：多级空间索引算法分析

学 院： 研究生学院

专 业： 大地测量学与测量工程

班 级： 硕研12级3班

姓 名： 张鼎凯

学 号： 2012020344

日 期： 2012年12月05日

摘要：空间数据库的索引是提高空间数据库存储效率和空间检索性能的关键技术。介绍了空间数据库中建立索引的常用技术，给出了一种多级空间索引，详细讨论了该索引的建立算法以及应用该索引的检索算法，并进行了算法分析。

关键词：计算机软件；间数据库；空间索引；空间检索；算法分析

1 空间索引技术简介

空间索引是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。空间数据一般是是多维的，在此主要介绍二维空间数据的索引。近年来，国外学者提出应用空间基数分区对空间数据进行管理，已得出了几种空间数据索引结构。例如 Robinson提出的 K-D-B 树[2] ，Guttman 提出 R 树结构[3]，Freeston 提出的 BANG 文件[4]，Beckmann 提出的 R*树结构[5]等。国内则学者提出了 QR-树[6]，网格索引[7][8]等索引结构，并进行了有关索引结构的性能分析和查询优化研究[8][9]。众多的索引结构可以说各有优缺点。总的来说，可分为以四叉树为代表的网格文件结构和以 R 树及其变种为代表的动态索引技术。

1.1四叉树结构

四叉树索引是栅格文件索引技术的代表。栅格文件索引技术的基本思想是将一张地图规则地划分成多个互不相交的栅格，且要求所有栅格覆盖全地图，然后再利用栅格对地图上的空间对象进行索引。如 K-D树、K-D-B 树、四叉树、八叉树等均基于此思想。我们在此主要介绍一下四叉树空间索引技术。四叉树空间索引是将一张地图逐步四等分，且依次编号，如图 1（a）所示，其层次由用户依需要而定。划分的结果可生成如图 1（b）的四叉树结构。从此结构中可确定被索引类中每个对象实例的被索引属性值属于那一个最小范围块，并将其 ID

加到该最小范围块所带的链表中。查询时根据用户关心的区域，选中区域所在最小范围块中的对象。四叉树的查询在最坏情况下效率较低，而且四叉树的动态性较差。建立索引后，如果又扩大地图范围增加新对象时，必须重新建立四叉树索引，因而缺乏灵活性。

图 1 四叉树结构

Fig.1 the structure of quartered tree

1.2 R 树结构

R 树是在 B 树的基础上通过对空间数据递推分区，并以分区后的区域作为关词建立起的一种层次结构。它不对地图预先划分，可随着地图中空间对象的增加而使原有的范围块分裂，具有 B 树的动态平衡性。其中叶结点包含指向数据库中实际几何物体的指针，所有叶结点都在同一层上，且可以实现多维索引。非

叶结点完全包含了子结点的区域。图 2（a）表示了地图上的两个范围 A、B（用虚线框起），相互有覆盖。图 2（b）是与之对应的一个 4 阶 R 树结构。当空间对象加入 B 范围时，R 树会相应分裂。同样，当删除空间对象时，会引起

R

图 2 R 树结构

Fig.2 the stucture of R-Tree

树结点的合并。R 树结构的主要优点在于空间利用率高，每个空间对象在树中只表示一次。R 树的查询效率较高，但分区可能产生重叠。在 R 树结构中频繁插入或删除对象时，由于要动态地保持树的平衡，可能会产生震荡而降低效率。

2 多级空间索引的基本结构

多级空间索引实质上仍属于网格索引结构[7][8]，其基本思想是将整个空间纵横分成若干个均等的小块，每个小块都作为一个桶，将落在该小块内的实体对象的标识号放入该小块对应的桶中。为适应精度要求，小块还可以再细分，直到不可分为止。设将空间分成 m*n 个小块，左下角为坐标原点，则每个小块可表示为 Block[i, j]，0≤i

mod n]；其中 0≤i

假设桶 Buck[i]中存放的实体集合为 Set_Buck[i], 其中 0≤i

1）对于任一点实体 D_Obj，设所在桶为 Buck[i]，则有 D_Obj∈Set_Buck[i]；

2）对于任一线实体 L_Obj，设该线实体所占桶号集合为{k1, k2,… ,kp}，则对于

i∈{k1, k2,… ,kp}，有 L_Obj∈Set_Buck[i]；

3）对于任一面实体 A_Obj，不妨设该面实体所覆盖的桶号集合为{L1,

L2,… ,Lq}，则对于 i∈{L1, L2,… ,Lq}，有 A_Obj∈Set_Buck[i]。这种索引结构的数据结构由一个桶的数组和一组单链表组成。其中，各桶都有指向第一个实体结点的指针。若该指针为空，则表示该桶内没有实体。实体结点内除了有实体标识号之外，还有指向下一个实体的指针以及表示实体下级空间索引的其它一些信息。下面介绍各类实体所包含多级空间索引的表示形式。

3 多级空间索引的表示

在应用中，用户提出的查询既有非精确查询，也有精确查询。对于精确查询，如果只分成 m×n 个小块往往达不到查询要求。例如，查询点实体与线实体是否相交，如图 3 所示。点实体和线实体有一个共同的存储桶，但这并不能说明它们相交，只能表明二者比较接近而已。为了达到精确查询的要求，除非 m 和 n

足够大，以至小块不可再分。显然，当 m 和 n 过大时，空间和时间效率将都变得较低。所以为了效率，我们采用多级网格策略，使小块仍可再分。块的划分

图 3 一个桶中实体不相交的情况

Fig.3 entities in a bucket disjoint 可分为若干等级，但等级过多，就会带来存储空间过多的开销以及降低时间效率。我们实现的网格索引支持三级划分。第一级网格即为对整个空间范围第一次划分得到的块 Block[i, j](0≤i

图 4 多级空间索引结构

Fig.4 the structure for Spatial Multilevel Index

对于第二级和第三级块，如果也采用桶结构，势必占用大量存储空间。因此，为了提高效率，实体的二级和三级空间索引由一个动态链表来表示。实体的多

级空间索引结构如图 4 所示。

对于点实体来说，多级空间索引的表示比较简单。点实体在二级划分中，必定对应一个二级小块。该二级块在所属的一级块内具有一个相对编号。对三级块也是同样，有一个三级块的编号。所以，点实体的多级空间索引可以表示为两部分，即二级块号和三级块号。

线实体的多级空间索引比较复杂一些。设线实体在某个一级块 i 内经过 p

个二级块，块号为{L1, L2,… … , Lp}，记为 Set2i，表示第 i 个一级块中该地物对应的二级块集合。同样，对于 j∈{L1, L2,… … , Lp}，Set3j 表示第 j 个二级块中该地物对应的三级块的集合。所以在桶 i 内，线状实体的空间索引可以表示为{L1.Set3L1，L2.Set3L2, … ,Lp.Set3Lp},一般可记为 Objx_INFOi, 其中

Objx 表示某个线实体 x，INFOi 表示为该实体在第 i 个桶中的全部空间索引。

面实体的多级空间索引与线实体类似，但有些区别。面实体所占的一级块分为两种情况。有的一级块完全在面实体的覆盖区域内，而有的只是部分落在面实体区域内。我们称完全落在区域内的块叫内块，其它为边块。很显然对内块无需细分，只需做个标记即可。而对边块必须细分，面实体边块的多级空间索引同线实体的表示方式一样。对于不同的实际应用，需要不同的划分级数，这可以由用户指定，或按照某种条件进行优选。 4 多级空间索引的相关算法

4.1面实体多级空间索引建立算法

建立面实体的多级空间索引，关键在于判断内块、边块和外块。若是内块，则不用再细分下去，只需在其多级空间索引结构内作上内块标记即可；若是边块，则需要进一步细分和判断；若是外块，则也不用细分，直接排除即可。为了提高效率，在建立多级空间索引之前采取最小约束框方法进行一次过滤，排除掉大部分无需进一步判断的外块。

图 5 边界号对应关系

Fig.5 boundary correspondence

算法输入：面实体 Area{(x1, y1),(x2, y2),… ,(xn, yn)}

算法输出：该面实体的多级空间索引 B_Set

1）求出外接矩形所占一级块的左右上下边界号 nl，nr，nt，nb，如图 5 所示。

2）判断在(nl，nb)，(nr，nt)矩形区域上各网格点是否在面实体内。若在面内，则一级标记数组中相对应的元素值赋为 1，否则赋为-1。

3）判断在(nl，nb)，(nr，nt)矩形区域上各块的性质：若块 Block[i，j]的四个顶点都在面内，则为内块，在多级索引结构中做上内块标记；若有一到三个顶点在面内，则为边块。

4）若块 Block[i，j]为边块，则判断其中的各二级块的内外块性质。

5）若二级块为边块，则判断其中的各三级块的性质。

6）根据各级块的性质，把得到的多级索引信息存入空间索引结构中。

7）算法结束返回。

4.2 面检索算法（检索与某面相交或包含在面内的实体）

算法输入：面实体 Objx，索引 SDB_idx，检索精度