二叉树的应用---4.B+树

（一）B+树及其查找：

B+数可以保持数据的稳定有序，其插入和修改具有较稳定的时间复杂度，在B+树中，对数据的引用指向叶子结点，内部结点的关键字只是充当划分子树的分界值：

其定义和B-树相同：

• 树中每个结点最多有m个子树
• 根结点最少有两个子树
• 除了根结点以外的非叶子结点最少有m/2个子树
• 所有叶子结点都出现在同一层
• 其中有n+1个子树的非叶子结点的信息如下图：

  

通常B+树上有两个指针，一个指向根结点，另一个指向关键字最小的叶子结点，如图所示：

B+树查找的过程和b-树相似，但查找时，无论非叶子结点的关键字是否和给定关键字相同，都要沿着相应子树向下查找，一直找到叶子结点；因此，每次查找都是从根结点到叶子结点的一条路径；

（二）B+树的插入和删除：

与B-树相似，B+树的插入和删除均是在叶子结点上进行；

插入：

• （1）当插入后关键字数目满足条件时：

  

• （2）当结点中的关键字数目大于m个时要分裂为两个结点，每个结点的关键字数目分别为m/2，（m+1）/2；

  与B+树不同的是:如图，插入23后，关键字数目超过3，则将叶子结点分裂为两部分q和p，把前两个关键字和指针移动到新结点q，同时把q的最后一个关键字复制到双亲结点，

  

删除：

（1）在删除叶子结点的最大关键字后，其在非终端结点的副本仍可以作为一个分解关键字使用

如图，若删除25，则只删除25即可，其余无需变化；

和B-树类似：（2），当删除的结点的兄弟结点关键字数目大于m/2，则将叶子结点个兄弟结点的关键字重新分配

（3）否则删除叶子结点，将剩余关键字合并到兄弟结点中

如图为（2）情况：

如图为（3）的情况：