二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(17)

另一种是从根结点开始，进行自顶向下，直到叶结点的随机查找。在B + 树进行随机查找、插入和删除的过程基本上与B-树类似。需要注意的一点是：在查找过程中，如果非叶结点的关键字与给定值相等，查找并不停止，而是继续沿着右指针向下行进，一直查到在叶结点上的这个关键字，然后才能根据相应的指针找到其记录。因此，在B + 树中，无论查找成功与否，每次查找都是走了一条从根到叶结点的路径。B + 树上的插入仅在叶结点上进行。当插入后结点中的子树棵数nj m1时，需要将叶结点为两个结点，它们所包含的关键字分别为 m1+1 /2 和 m1+1 /2 。并且它们的双亲结点中应同时包含这两个结点的最小关键字和指向这两个结点的指针。剩下的工作就是在非叶结点中的插入了。在非叶结点中，关键字的插入与叶结点的插入类似，当非叶结点中的子树棵数j m时，也需要将进行结点。当根结点时，由于它再没有双亲结点，因此必须创建一个新的双亲结点作为树新的根。这样树的高度就增加了一层。B + 树的建立可以从空树开始，通过不断插入关键字来完成。例9.17 图9-32是在一棵4阶B + 树中插入关键字为24的记录的例子，这里仍假设叶结点最多可容纳4 m1 个关键字。

如图9-32 a 所示，插入时首先从根开始向下搜索，找到关键字24应插入的叶结点，这时该叶结点已有4个关键字 满额 ，需要为两个结点：一个结点含有3个关键字15，17，22；另一个结点含有2个关键字24，26。接下来的处理是把这两个结点中的最小关键字15和24及指向这两个结点的指针传到上层的双亲结点中，由于最小关键字15和指向它所在结点的指针已存在双亲结点中，所以只需把最小关键字24和它所在的结点地址插入父结点中。但这时双亲结点中关键字有了3个，已为满额 m阶B + 树的非叶结点的关键字最多可有m-1个 ，再插入也要进行结点，而双亲结点又是根结点，所以后树长高了一层，如图9-32 b 所示。B + 树的删除也是在叶结点上进行。若在叶结点中删除一个关键字后，其关键字的个数仍不少于 m1/2 ，则可直接删除，其上层索引可以不改变。例如在图9-32所示的4阶B + 树里，从叶结点中删除关键字30，虽然它为该结点的最小关键字，但因其上层的关键字30只是起到一个引导查找的“分界关键字”的作用，所以即使树中已经删除了关键字30，但上层结点中的关键字30仍可保留。若在叶结点中删除一个关键字后，其关键字的个数小于结点关键字的个数的下限值 m1/2 ，则必须做结点的调整和合并工作。

例如，在图9-32所示的4阶B + 树中删除关键字9，后，该结点的关键字个数为1，小于结点的关键字个数的下限2，这时它右兄弟结点中的关键字个数为3，大于结点的关键字个数的下限，因此可以从其右兄弟结点中最左关键字15移到这个被删关键字所在的结点中，使得两个结点中关键字的个数都在允许的范围之内。移动后，右兄弟结点中的最小关键字为17，其上层双亲结点中的“分界关键字”不能再为15了，必须把新的“分界关键字”17送到上层双亲结点中去。若右兄弟结点中的关键字的关键字个数已达到下限值 m1/2 ，即没有多余的关键字可以移入被删关键字所在的结点，此时需进行两个结点的合并：将右兄弟结点中的所有关键字和记录指针移入被删关键字所在的结点，再将右兄弟结点删掉。这种结点合并将导致双亲结点中“分界关键字”的减少，有可能引起非叶结点的调整或合并。如果是根结点的两个子女结点需要合并，则树的层数就会减少一层。例如在图9-32所示的4阶B + 树里，从关键字为15,17和22的叶结点中连续删除两个关键字时，就会出现这种情况。9.4 散列表的查找9.4.1 基本概念散列表 hash table 又称为哈希表，它是一种重要的存储方式。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-17.html