数据结构 408-7-4

# B 树

五叉查找树

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

最少 1 个关键字，2 个分支

最多 4 个关键字，5 个分叉

若每个结点内关键字太少，导致树变高，要查更多层结点，效率低

策略：

m 叉查找树，规定除了根结点外，任何结点至少有$\lceil m/2\rceil$ 个分支，即至少含有$\lceil m/2\rceil$-1 个关键字

m 叉查找树中，规定对于任何一个结点，其所有子树的高度都要相同

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

• 树中每个结点至多有 m 棵子树，即至多含有 m-1 个关键字
• 若根节点不是终端节点，则至少有两棵子树
• 除根节点外的所有非叶结点至少有$\lceil m/2\rceil$ 棵子树，即至少含有$\lceil m/2\rceil$-1 个关键字
• 所有的叶节点都出现在同一层次上，并且不带信息 (可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些节点不存在，指向这些节点的指针为空)

m 阶 B 树的核心特性：

• 根节点的子树$\in[2,m]$，关键字数$\in[1,m-1]$，其他结点的子树数如上述第三条
• 对任一结点，其所有子树高度都相同
• 关键字的值：子树 0 < 关键字 1 < 子树 1 < 关键字 2 < 子树 2<...（类比二叉查找树左 < 中 < 右）

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

• 最小高度$h\ge log_m(n+1)$

• n 个关键字的 B 树必有 n+1 个叶子节点，$h\le log_{\lceil m/2\rceil}\frac{n+1}{2}+1$

# B 数的插入和删除

# B 数的插入

在插入 key 值后，若导致原节点关键字数超过上限，则从中间位置 ($\lceil m/2\rceil$) 将其中的关键字分为两部分，左部分包含的关键字放在原始结点中，右部分包含的关键字放到新结点中，中间位置 ($\lceil m/2\rceil$) 的结点插入原节点的父节点。

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

新元素一定是插入到最底层 "终端节点"，用 "查找" 来确定插入位置

# B 树的删除

若被删除关键字在终端节点，则直接删除该关键字 (要注意结点关键字个数是否低于下限$\lceil m/2\rceil-1$)

若被删除关键字在非终端节点，则用直接前驱或直接后继来替代被删除的关键字

直接前驱：当前关键字左侧指针所指子树中最右下的元素

直接后继：当前关键字右侧指针所指子树中最左下的元素

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

若被删除关键字所在节点删除前的关键字个数低于下限，且与此结点右 (或左) 兄弟结点的关键字个数还很宽裕，则需要调整该结点、右 (或左) 兄弟结点及其双亲结点 (父子换位法)

若被删除关键字所在节点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点关键字个数均 = 下限，则将关键字删除后与左 (或右) 兄弟及双亲中的关键字进行合并

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

# B + 树

一棵 m 阶 B + 树需要满足下列节点：

• 每个分支结点最多有 m 棵子树 (孩子结点)
• 非叶根节点至少有两颗子树，其他每个分支结点至少有$\lceil m/2\rceil$ 棵子树
• 结点的子树个数与关键字个数相等
• 所有的叶子结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶节点按大小顺序连接起来
• 所有分支结点中仅包含它的各个子节点中关键字的最大值及指向其子节点的指针

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

m 阶 B + 树与 m 阶 B 树对比：

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