【数据结构】B树和B+树

1. B树

1. B树的定义

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或满足如下特性的m叉树：

1. 树中每个结点至多有m棵子树，即至多含有m-1个关键字。
2. 若根结点不是终端结点，则至少有两棵子树。
3. 除根结点外的所有非叶结点至少有m/2向上取整棵子树，即至少含有m/2向上取整-1个关键字。
4. 所有非叶结点的结构如下： 其中，Ki(i=1,2,...,n)为结点的关键字，且满足K1<K2<...<Kn；Pi(i=1,2,...,n)为指向子树根结点的指针，且指针Pi-1所指子树中所有结点的关键字均小于Ki，Pi所指子树中所有结点的关键字均大于Ki，n(m/2向上取整-1<=n<=m-1)为结点中关键字的个数。
5. 所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些节点并不存在，指向这些节点的指针为空）

5叉排序树的结点定义

struct Node{
    ElemType keys[4];  // 最多4个关键字
    struct Node *child[5];  // 最多5个孩子
    int num;  // 结点中有几个关键字
};

说明：此图为5阶B树。

2. m阶B树的核心特性

1. 根结点的子树数∈[2,m]，关键字数∈[1,m-1]。 其他节点的子树数∈[m/2向上取整，m]；关键字数∈[m/2向上取整-1,m-1]。
2. 对任一结点，其所有子树高度相同。
3. 关键字的值：子树0<关键字1<子树1<关键字2<子树2<…（类比二叉查找树 左<中<右）

说明：第一条保证了m叉树尽可能“满”，第二条保证了m叉树尽可能“平衡”。

思考：

含n个关键字的m阶B树，最小高度、最大高度是多少？

3. B树的插入

5阶B树—结点关键字个数m/2向上取整-1<=n<=m-1 即：2<=n<=4

在插入key后，若导致原结点关键字数超过上限，则从中间位置（m/2向上取整）将其中的关键字分成两部分，做部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（m/2向上取整）的结点插入原结点的父结点。依次类推。

若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树的高度加1。

注意：新元素一定是插入到最底层“终端结点”，用“查找”来确定插入位置。

4. B树的删除

若被删除关键字在终端节点，则直接删除该关键字(要注意节点关键字个数是否低于下限m/2向上取整- 1)

若被删除的关键字在非终端结点，则用直接前驱或直接后继来替代被删除的关键字。直接前驱：当前关键字左侧指针所指子树中“最右下”的元素。直接后继：当前关键字右侧所指子树中“最左下”的元素。

对非终端结点关键字的删除，必然可以转化为对终端结点的删除操作。

删除的结点关键字低于下限：

• 若兄弟够借，则需要调整该结点左或右兄弟终端及其双亲结点（父子换位法）。
• 若兄弟不够借，则将关键字删除后与其左或右兄弟结点及其双亲结点的关键字进行合并。

在合并过程中，双亲结点中的关键字会减1，若其双亲结点是根结点且关键字减少至0，则直接将根结点删除，合并后的新结点称为根；若双亲结点不是根结点，且关键字个数少下限，则又要与它自己的兄弟结点进行调整或合并操作，重复上述操作，直至符合B树的要求为止。

示例：

2. B+树

1. B+树的定义

一棵m阶的B+树需满足下列条件：

1. 每个分支结点最多有m棵子树（孩子结点）。
2. 非叶根结点至少有两棵子树，其他每个分支结点至少有m/2向上取整棵子树。
3. 结点的子树个数与关键字个数相等。
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点将关键字按大小顺序排序，并且相邻叶结点按大小顺序相互链接起来。
5. 所有分支结点中仅包含它的各个子节点中关键字的最大值及指向其子结点的指针。

说明：相邻叶结点按大小顺序相互链接起来说明支持顺序查找。

2. B+树的查找

B+树中，无论查找成功与否，最终一定都要走到最下面一层结点。

3. 典型应用

关系型数据库的“索引”（如MySql）

在B+树中，非叶结点不含有该关键字对应记录的存储地址，可以使一个磁盘快包含更多的关键字，使得B+树的阶更大，树更矮。读磁盘次数更少，查找更快。

3. 小结