空间数据库索引技术

《空间数据库索引技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、空间数据库索引技术一、DBMS索引技术1.索引顺序存取方法2.多层索引树（1）B-树（2）B＋-树1.索引顺序存取方法存储结构：分为三个区，索引页、数据页和溢出页。记录是按照关键字值排序。数据页存储数据，数据页可以分块，每块包含多个记录，一个块包含一个索引项，不是每个记录都有索引项。溢出页解决插入问题。因为记录是按照顺序排放，所以如果插入新的数据，就必须调整所有记录。为了解决这个问题，设置溢出页存放插入的数据。索引页指向数据页和溢出页，每个索引项包含两个部分：基本索引项和指针。数据页每一块设置一

2、个索引项，溢出页中的记录用指针串联起来，同一数据块中的记录链为一个链表。缺点：静态结构。在建立索引树之前已经知道了有多少数据块。如果大量插入操作作用于同一个数据块（叶子），则产生很长的溢出页链，降低效率。即树变的不平衡了。2.B-树动态结构，能够随插入和删除而调整的树。多层索引结构包含2m个数据域和2m+1个指针域。定义：一棵2m+1阶的B树，或为空，或为满足：（1）树中每个节点最多有2m+1棵子树，且除根节点外，所有非叶子节点的子树数量至少有m+1，而根节点至少有两棵子树。（2）所有叶子节点均

3、在最后一层上。（3）除叶子节点外每个结点结构如下：LINKi为指针，指向各子树根节点，KEYi为关键字，存放关键字及数据有关信息。要求，KEY有序，而且所对应子树之间也是有序的。（4）所有叶子节点指针为空，叶子节点的元素数量大于m。（1）检索从根节点开始，进行关键字的比较。（2）插入如果在找到的插入位置叶子节点的元素个数不足2m个，直接插入。如果在插入的位置叶子节点已经有2m个，则进行分裂。分裂过程：将数据按顺序插入，然后将该叶子结点对分，其中前半部分仍然存放原来结点中，后面的放在一个新申请的结

4、点中，并将中间一个元素放在父结点中。如果父结点中的元素也已经满了，则父结点必须进行分裂。插入27，分裂后，22加入到父结点中。（3）删除x检索到后，如果在叶子节点上，则进行删除，如果不在叶子节点上，则要用一个比x大的元素y代替x。y即x右边指针所指路径最左边叶子节点的第一个元素。然后在叶子节点中删除y。删除y后，如果叶子节点元素数量小于m，则与它相邻的左（右）结点借一个元素；如果兄弟结点元素数量正好为m，则进行叶子节点的合并。合并完成后，父结点少了一个子树，则也可能存在合并的问题。3.B+树B树

5、随机检索效率很高，但是遍历所有元素却不方便。这是因为，B树的非叶子节点同样存储数据。B+树是B树的变形，在非叶子节点中存放的不是数据。定义：一个2m+1阶的B树满足，（1）每个结点至多有2m+1棵子树（2）除根节点外，其他每个分支至少有m+1棵子树。（3）非叶子节点的根节点至少有两个子树。（4）有n棵子树的非叶节点有n-1个关键码。（5）叶节点都在同一个层上，存放了数据文件中记录关键码以及指针。叶节点按照关键码值排序链接。（6）所有分支结点可看成是索引的索引。仅存放各子节点的最大（最小）关键码的

6、分界值及指针。B+树包含两部分：首先是B树索引。然后链接各叶子节点的顺序链。即包含两个指针。在插入和删除的方式上，与B树不同。B+树在插入时，与B树类似，不同在于分裂时，不仅要把元素上升到父节点中，并且在叶子节点中也要保留。插入8叶结点保留原来元素，但是中间节点分裂时不保留。B+树删除时比较简单。只需要删除叶子节点上的数值，而中间节点不需要改变。但是，这中间存在合并的过程。上为删除19，20后，下为进一步删除24后。二、空间数据库索引传统的数据库索引技术包括了B树、B+树、二叉树、哈希索引等，都

7、是针对一维属性数据的主关键字索引而设计的。空间数据库索引基于这些技术分别取得了发展。基于哈希表的检索空间索引大致分为四大类：1.基于二叉树的索引技术2.基于B树的索引技术3.基于哈希的格网技术4.空间目标排序法1.基于二叉树的索引技术主要有Kd树、KDB树等。其中，典型的Kd树是一种二分索引树结构，主要用于索引多维数据点，但对于复杂的空间目标，如折线、多边形等必须采用近似方法和空间映射技术。为了能索引复杂的空间目标，Mkd树被提出；为了将Kd树存储到外存，将Kd树与B树结合，得到KDB树。所有的

8、方法对于非点状空间目标的索引效率都很低。2.基于B树的索引技术目前很多空间数据索引技术，都是B树发展来的。例如R树、R+树、R*树等。利用最小外包矩形表示空间目标。3.基于哈希的格网技术基本思路是将索引空间划分为相等或不相等的一些小方格网，与每个格网相关连的空间目标则存在同一磁盘页，而格网的访问地址则可以直接通过求数组下标或某种算法得到。4.空间目标排序法将多维空间映射为一维空间，包括了Z序、Hilbert排序等。（一）Kd树1.定义Kd树的每个节点表示K维空间的一个点，并且树的每一层都根据这层