空间数据库索引技术

第5章空间数据库索引技术1空间数据索引技术1B树索引2可扩展的哈希索引3空间填充曲线455.1空间数据索引技术空间索引是指根据空间要素的地理位置、形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构，一般包括空间要素标识，外包络矩形以及指向空间要素的指针。空间索引的理解：可以想象一本书，其中书的内容就相当于表里的数据，而书前面的目录就相当于该表的索引。空间索引目的是为了在GIS系统中快速定位到所选中的空间要素，从而提高空间操作的速度和效率。5.2B树索引B树索引是一个典型的树结构，始终是平衡的，也就是说从Root节点到Leaf节点的任何一个路径都是等距离的。其包含的组件主要是：叶子节点（Leafnode）：包含的条目直接指向表里的数据行。分支节点（Branchnode）：包含的条目指向索引里其他的分支节点或者是叶子节点。根节点（Rootnode）：一个B树索引只有一个根节点，它实际就是位于树的最顶端的分支节点。5.2.1B树索引的结构5.2.2B树索引的性质1.每个结点的关键字是升序排列2.含有n个关键字的结点,都包含n+1个指针指向其孩子4.父结点中第i个关键字≥第i个孩子的所有关键字父结点中第i个关键字≤第i+1个孩子的所有关键字3.叶子结点没有孩子,所有的叶子都处在同一层5.1≤根结点的关键字的个数≤2t–1t-1≤非根结点的关键字的个数≤2t-1最小度用t(t>=2)来表示，最小度数即内结点中结点最小孩子数目例子：查找21

5.2.3B树的操作1.搜索B树612磁盘块568磁盘块61011磁盘块71618磁盘块82123磁盘块92932磁盘块103637磁盘块114043磁盘125660磁盘13磁盘块11535p1p2p3磁盘块43944p1p2p3磁盘块31928p1p2p3磁盘块239p1p2p32.B树的插入

GMPXACDEJKNORSTUVYZ初始B树(t=3)插入BGMPXACDEJKNORSTUVYZ1<=根结点的关键字个数<=52<=非根结点的关键字个数<=5范围B7未超出范围，直接插入。插入Q

超出范围分裂，分裂为各含有t-1个关键字的结点,中间关键字提升到其双亲结点中，然后将关键字插入。8UV

RSGMPXAB

CDEJKNOYZRSTUVTQ1<=根结点的关键字个数<=52<=非根结点的关键字个数<=5范围9GMPTXAB

CDEJKNOYZRSU

V插入W自顶向下进行插入，分裂沿途中的每个满结点xG

M

T

X

PxxxW103.B树的删除B树的删除关键字在终端结点中，直接删除关键字在内结点x中够借，借调◆左孩子够借，借调直接前驱◆左孩子不够借，右孩子够借，借调直接后继不够借合并关键字不在内结点x中，在子树中左右兄弟够借，借调左右兄弟不够借，合并自顶向下的方式进行删除需要借不需要借CGMAB

JKLNOYZQRSUVTXPDEF初始B树（t=3）删除FCGMAB

JKLNOYZQRSUVTXPDEF

1<=根结点的关键字个数<=52<=非根结点的关键字个数<=511关键字在叶结点中，直接删除删除G1<=根结点的关键字个数<=52<=非根结点的关键字个数<=5

若左右孩子不够借,将右孩子合并到左孩子中去，并将所删关键字做为左孩子的中间关键字，删除关键字，释放右孩子。CGLAB

NOYZQRSUVTXPJKDEDEGJK12关键字在内结点x中够借，借调◆左孩子够借，借调直接前驱◆左孩子不够借，右孩子够借，借调直接后继不够借合并x13关键字不在内结点x中，在子树中左右兄弟够借，借调左右兄弟不够借，合并AB

NOYZQRSUVEJKCL

PTX

x删除By左右够借,借调CE代表未画出的子树14左右兄弟够借，借调左右兄弟不够借，合并CL

AB

NOYZQRSUVTXPDEJK删除D左右不够借，合并CL

PTX

xy关键字不在内结点x中，在子树中5.3可扩展的哈希索引网格文件是一种典型的基于哈希的存取方式，它是由包含很多与数据桶相联系的单元的网格目录来实现的。对于二维空间为平行于x或y轴的直线，这一超平面将数据空间划分为两个子空间。所有的边界一起将整个数据空间划分成许多k维的矩形子空间，这些矩形子空间称为网格目录，由一个k维的数组表示。目录项（即网格目录数组的元素）和网格单元之间具有一对一的关系。网格目录的每一网格单元包含一个外存页的地址，对应着一个数据桶，一般一个数据桶为硬盘上一个磁盘页，这一外存页存储了包含了网格单元的数据目标，称为数据页。数据页所对应的一个或多个网格单元称之为存储区域,存储区域两两不相交。每个数据桶往往可以包含着几个相邻的单元，存储多个网格单元的目标，只要这几个网格单元一起形成一矩形的区域。5.3可扩展的哈希索引网格文件查找先找到涉及网格单元，并提取相应的数据页，然后比较数据页的牧鞭是否满足查询要求即可。网格文件插入

先进行一次精确查询定位该数据项插入的网格单元，提取对应的数据页（数据桶存放的磁盘页）。若该磁盘页有空间，将数据插入。若没有足够空间，则要根据与该页的联系的单元的数目来分裂该数据页。网格文件删除

在网格文件中删除一个数据，也要进性一次精确查找确定该数据所在正确的网格单元，提取对应数据页，从数据页中删除该目标。D5D4D6网格文件插入目录示意图5.4空间填充曲线空间填充曲线是一种重要的近似表示方法，将数据空间划分成大小相同的网格，再根据一定的方法将这些网格编码，每个格指定一个唯一的编码，并在一定程度上保持空间邻近性，即相邻的网格的标号也相邻，一个空间对象由一组网格组成。

这样可以将多维的空间数据降维表示到一维空间当中。理想的空间映射方法是：在多维空间中聚集的空间实体，经过填充曲线编码以后，在一维空间中仍然是聚集的。

（a）行排序（b）Hilbert排序（c）Z排序

图5-30几种常用的空间填充编码方法1)Z-ordering曲线（peano曲线）Z-排序（Z-ordering）技术将数据空间循环分解到更小的子空间（被称为PeanoCell），每个子空间根据分解步骤依次得到一组数字，称为该子空间的Z-排序值。子空间有不同的大小，Z-排序有不同的长度，显然，子空间越大，相应的Z-排序值越短。这里，分辨率（resolution）是指最大的分解层次，它决定了Z-排序值的最大长度。

图5-31Z-排序示例2n×2n个分区，编号为0~2n×2n-12)H