空间数据库索引技术

1、第5章 空间数据库索引技术1空间数据索引技术1B树索引2可扩展的哈希索引3空间填充曲线455.1 空间数据索引技术空间索引是指根据空间要素的地理位置、形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构，一般包括空间要素标识，外包络矩形以及指向空间要素的指针。空间索引的理解：可以想象一本书，其中书的内容就相当于表里的数据，而书前面的目录就相当于该表的索引。空间索引目的是为了在GIS系统中快速定位到所选中的空间要素，从而提高空间操作的速度和效率。5.2 B树索引B树索引是一个典型的树结构，始终是平衡的，也就是说从Root节点到Leaf节点的任何一个路径都是等距离的。其包含的组件主要是

2、： 叶子节点（Leaf node）：包含的条目直接指向表里的数据行。 分支节点（Branch node）：包含的条目指向索引里其他的分支节点或者是叶子节点。 根节点（Root node）：一个B树索引只有一个根节点，它实际就是位于树的最顶端的分支节点。5.2.1 B树索引的结构5.2.2 B树索引的性质1.每个结点的关键字是升序排列2.含有n个关键字的结点,都包含n+1个指针指向其孩子4.父结点中第i个关键字 第i个孩子的所有关键字 父结点中第i个关键字 第i+1个孩子的所有关键字3.叶子结点没有孩子,所有的叶子都处在同一层5. 1 根结点的关键字的个数2t 1 t - 1非根结点的关键字的个

3、数2t - 1最小度最小度用用t(t=2)t(t=2)来表示，来表示，最小度数即内结点中结最小度数即内结点中结点点最小最小孩子数目孩子数目例子：查找例子：查找215.2.3 B树的操作1.搜索B树612磁盘块磁盘块568磁盘块磁盘块61011磁盘块磁盘块71618磁盘块磁盘块82123磁盘块磁盘块92932磁盘块磁盘块103637磁盘块磁盘块1140 43磁盘磁盘1256 60磁盘磁盘13磁磁盘盘块块11535p1p2p3磁磁盘盘块块43944p1p2p3磁磁盘盘块块31928p1p2p3磁磁盘盘块块239p1p2p32.B树的插入 G M P XA C D EJ K N O R S T U

4、VY Z初始初始B树树( t = 3)插入插入BG M P XA C D EJ K N O R S T U VY Z1=根结点的关键字个数根结点的关键字个数=52=非根结点的关键字个数非根结点的关键字个数=5 范围范围B7未超出范围，直接插入。未超出范围，直接插入。插入插入Q 超出范围分裂，超出范围分裂，分裂为各含有分裂为各含有t-1t-1个关键字的结点个关键字的结点, ,中间关键字提升到其双亲结点中，然后将关键字插入。中间关键字提升到其双亲结点中，然后将关键字插入。8U V R SG M P XA B C D EJ K N O Y ZR S T U VTQ1=根结点的关键字个数根结点的关键字

5、个数=52=非根结点的关键字个数非根结点的关键字个数=5 范围范围9G M P T XA B C D EJ K N O Y ZR S U V插入插入W自顶向下进行插入，分裂沿途中的每个满结点自顶向下进行插入，分裂沿途中的每个满结点xG M T X PxxxW103.B树的删除B B树的删除树的删除关键字在终端结点中，直接删除关键字在终端结点中，直接删除关键字在内结点关键字在内结点x中中够借，够借，借调借调左孩子够借，左孩子够借，借调借调直接前驱直接前驱左孩子不够借，右孩子左孩子不够借，右孩子够借，借调够借，借调直接后继直接后继不够借不够借合并合并关键字不在内结点关键字不在内结点x中，中，在子树

6、中在子树中左右兄弟够借，借调左右兄弟够借，借调左右兄弟不够借，合并左右兄弟不够借，合并自顶向下的方式进行删除自顶向下的方式进行删除需要借需要借不需要借不需要借 C G M A B J K L N O Y ZQ R S U VT X P D E F初始初始B树树（t=3）删除删除F C G M A B J K L N O Y ZQ R S U VT X P D E F 1=根结点的关键字个数根结点的关键字个数=52=非根结点的关键字个数非根结点的关键字个数=511关键字在叶结点中，直接删除关键字在叶结点中，直接删除删除删除G1=根结点的关键字个数根结点的关键字个数=52=非根结点的关键字个数非根

7、结点的关键字个数=5 若左右孩子不够借若左右孩子不够借, 将右孩子合并到左孩子中去，并将所删关将右孩子合并到左孩子中去，并将所删关键字做为左孩子的中间关键字，删除关键字，释放右孩子。键字做为左孩子的中间关键字，删除关键字，释放右孩子。 C G L A B N O Y ZQ R S U VT X P J K D E D E G J K 12关键字在内结点关键字在内结点x中中够借，够借，借调借调左孩子够借，左孩子够借，借调借调直接前驱直接前驱左孩子不够借，右孩子左孩子不够借，右孩子够借，借调够借，借调直接后继直接后继不够借不够借合并合并x13关键字关键字不在内结点不在内结点x中，在子树中中，在子树

8、中左右兄弟够借，借调左右兄弟够借，借调左右兄弟不够借，合并左右兄弟不够借，合并A B N O Y ZQ R S U V E J K C L P T X x删除删除B By左右够借,借调CE 代表未画出的子树14左右兄弟够借，借调左右兄弟够借，借调左右兄弟不够借，合并左右兄弟不够借，合并 C L A B N O Y ZQ R S U VT X P D E J K删除删除D左右不够借，合并 C L P T X xy关键字关键字不在内结点不在内结点x中，在子树中中，在子树中5.3 可扩展的哈希索引网格文件是一种典型的基于哈希的存取方式，它是由包含很多与数据桶相联系的单元的网格目录来实现的。对于二维空

9、间为平行于x或y轴的直线，这一超平面将数据空间划分为两个子空间。所有的边界一起将整个数据空间划分成许多k维的矩形子空间，这些矩形子空间称为网格目录，由一个k维的数组表示。 目录项（即网格目录数组的元素）和网格单元之间具有一对一的关系。网格目录的每一网格单元包含一个外存页的地址，对应着一个数据桶，一般一个数据桶为硬盘上一个磁盘页，这一外存页存储了包含了网格单元的数据目标，称为数据页。 数据页所对应的一个或多个网格单元称之为存储区域,存储区域两两不相交。每个数据桶往往可以包含着几个相邻的单元，存储多个网格单元的目标，只要这几个网格单元一起形成一矩形的区域。 5.3可扩展的哈希索引网格文件查找先找到

10、涉及网格单元，并提取相应的数据页，然后比较数据页的牧鞭是否满足查询要求即可。网格文件插入 先进行一次精确查询定位该数据项插入的网格单元，提取对应的数据页（数据桶存放的磁盘页）。若该磁盘页有空间，将数据插入。若没有足够空间，则要根据与该页的联系的单元的数目来分裂该数据页。网格文件删除 在网格文件中删除一个数据，也要进性一次精确查找确定该数据所在正确的网格单元，提取对应数据页，从数据页中删除该目标。D5D4D6网格文件插入目录示意图网格文件插入目录示意图5.4 空间填充曲线 空间填充曲线是一种重要的近似表示方法，将数据空间划分成大小相同的网格，再根据一定的方法将这些网格编码，每个格指定一个唯一的编

11、码，并在一定程度上保持空间邻近性，即相邻的网格的标号也相邻，一个空间对象由一组网格组成。 这样可以将多维的空间数据降维表示到一维空间当中。 理想的空间映射方法是：在多维空间中聚集的空间实体，经过填充曲线编码以后，在一维空间中仍然是聚集的。 （a a）行排序 （b b）HilbertHilbert排序 （c c）Z Z排序 图5-30 5-30 几种常用的空间填充编码方法1) Z-ordering曲线（peano曲线） Z-排序（Z-ordering）技术将数据空间循环分解到更小的子空间（被称为Peano Cell），每个子空间根据分解步骤依次得到一组数字，称为该子空间的Z-排序值。 子空间有不同的大小，Z-排序有不同的长度，显然，子空间越大，相应的Z-排序值越短。这里，分辨率（resolution）是指最大的分解层次，它决定了Z-排序值的最大长度。 图5-31 Z-5-31 Z-排序示例2n 2n个分区，