四章 空间数据库索引技术3.pptVIP

空间数据库索引技术 一、DBMS索引技术 1.索引顺序存取方法 2.多层索引树 （1）B-树 （2）B＋-树 1.索引顺序存取方法 存储结构： 分为三个区，索引页、数据页和溢出页。 记录是按照关键字值排序。 数据页存储数据，数据页可以分块，每块包含多个记录，一个块包含一个索引项，不是每个记录都有索引项。 溢出页解决插入问题。因为记录是按照顺序排放，所以如果插入新的数据，就必须调整所有记录。为了解决这个问题，设置溢出页存放插入的数据。 索引页指向数据页和溢出页，每个索引项包含两个部分：基本索引项和指针。数据页每一块设置一个索引项，溢出页中的记录用指针串联起来，同一数据块中的记录链为一个链表。 缺点： 静态结构。在建立索引树之前已经知道了有多少数据块。 如果大量插入操作作用于同一个数据块（叶子），则产生很长的溢出页链，降低效率。 即树变的不平衡了。 2.B-树 动态结构，能够随插入和删除而调整的树。 多层索引结构包含2m个数据域和2m+1个指针域。 定义： 一棵2m+1阶的B树，或为空，或为满足： （1）树中每个节点最多有2m+1棵子树，且除根节点外，所有非叶子节点的子树数量至少有m+1，而根节点至少有两棵子树。 （2）所有叶子节点均在最后一层上。 （3）除叶子节点外每个结点结构如下： LINKi为指针，指向各子树根节点，KEYi为关键字，存放关键字及数据有关信息。 要求，KEY有序，而且所对应子树之间也是有序的。 （4）所有叶子节点指针为空，叶子节点的元素数量大于m。 （1）检索 从根节点开始，进行关键字的比较。 （2）插入 如果在找到的插入位置叶子节点的元素个数不足2m个，直接插入。 如果在插入的位置叶子节点已经有2m个，则进行分裂。 分裂过程： 将数据按顺序插入，然后将该叶子结点对分，其中前半部分仍然存放原来结点中，后面的放在一个新申请的结点中，并将中间一个元素放在父结点中。 如果父结点中的元素也已经满了，则父结点必须进行分裂。 插入27，分裂后，22加入到父结点中。 （3）删除x 检索到后，如果在叶子节点上，则进行删除，如果不在叶子节点上，则要用一个比x大的元素y代替x。 y即x右边指针所指路径最左边叶子节点的第一个元素。然后在叶子节点中删除y。 删除y后，如果叶子节点元素数量小于m，则与它相邻的左（右）结点借一个元素；如果兄弟结点元素数量正好为m，则进行叶子节点的合并。 合并完成后，父结点少了一个子树，则也可能存在合并的问题。 3.B+树 B树随机检索效率很高，但是遍历所有元素却不方便。 这是因为，B树的非叶子节点同样存储数据。 B+树是B树的变形，在非叶子节点中存放的不是数据。 定义： 一个2m+1阶的B树满足， （1）每个结点至多有2m+1棵子树 （2）除根节点外，其他每个分支至少有m+1棵子树。 （3）非叶子节点的根节点至少有两个子树。 （4）有n棵子树的非叶节点有n-1个关键码。 （5）叶节点都在同一个层上，存放了数据文件中记录关键码以及指针。叶节点按照关键码值排序链接。 （6）所有分支结点可看成是索引的索引。仅存放各子节点的最大（最小）关键码的分界值及指针。 B+树包含两部分： 首先是B树索引。 然后链接各叶子节点的顺序链。 即包含两个指针。 在插入和删除的方式上，与B树不同。 B+树在插入时，与B树类似，不同在于分裂时，不仅要把元素上升到父节点中，并且在叶子节点中也要保留。 插入8 叶结点保留原来元素，但是中间节点分裂时不保留。 B+树删除时比较简单。只需要删除叶子节点上的数值，而中间节点不需要改变。 但是，这中间存在合并的过程。 上为删除19，20后，下为进一步删除24后。 二、空间数据库索引 传统的数据库索引技术包括了B树、B+树、二叉树、哈希索引等，都是针对一维属性数据的主关键字索引而设计的。 空间数据库索引基于这些技术分别取得了发展。 基于哈希表的检索 空间索引大致分为四大类： 1.基于二叉树的索引技术 2.基于B树的索引技术 3.基于哈希的格网技术 4.空间目标排序法 1.基于二叉树的索引技术 主要有Kd树、KDB树等。 其中，典型的Kd树是一种二分索引树结构，主要用于索引多维数据点，但对于复杂的空间目标，如折线、多边形等必须采用近似方法和空间映射技术。 为了能索引复杂的空间目标，Mkd树被提出；为了将Kd树存储到外存，将Kd树与B树结合，