B树

警告

代码一般不要求掌握

所谓 $m$ 阶 $\mathrm{B}$ 树是所有结点的平衡因子均等于 0 的 $m$ 路平衡查找树。
一棵 $m$ 阶 $\mathrm{B}$ 树或为空树, 或为满足如下特性的 $m$ 叉树:

1. 树中每个结点至多有 $m$ 棵子树, 即至多含有 $m-1$ 个关键字。
2. 若根结点不是叶结点, 则至少有两棵子树。
3. 除根结点外的所有非叶结点至少有 $\lceil m / 2\rceil$ 棵子树, 即至少含有 $\lceil m / 2\rceil-1$ 个关键字。
4. 所有非叶结点的结构如下:

$n$	$P_{0}$	$K_{1}$	$P_{1}$	$K_{2}$	$P_{2}$	$\dots$	$K_{n}$	$P_{n}$

其中, $K_{i}(i=1,2, \cdots, n)$ 为结点的关键字, 且满足 $K_{1}<K_{2}<\cdots<K_{n} ; P_{i}(i=0,1, \cdots, n)$ 为指向子树根结点的指针, 且指针 $P_{i-1}$ 所指子树中所有结点的关键字均小于 $K_{i}, P_{i}$ 所指子 树中所有结点的关键字均大于 $K_{i}, n(\lceil m / 2\rceil-1 \leqslant n \leqslant m-1)$ 为结点中关键字的个数。
5. 所有的叶结点都出现在同一层次上, 并且不带信息 (可以视为外部结点或类似于折半查 找判定树的查找失败结点, 实际上这些结点不存在, 指向这些结点的指针为空)。

image.png

终端结点和叶结点

• 终端结点指的是最底层的非叶结点
• 叶结点指的是所谓的查找失败节点，实际并不存在，在计算树高时一般也不将其计算在内

注意

注意区分结点个数和关键字个数，他们是不一样的，一个结点可能包含多个关键字，且下面算高度公式中的n是关键字个数

高度

注意

B树的高度不包括最后的不带任何信息的叶结点所处的那一层

$$n\leqslant(m-1)(1+m+m^2+\cdots+m^{h-1})=m^h-1$$

$$n+1\geqslant2(\lceil m/2\rceil)^{h-1}$$

即

$$\log_m(n+1)\leq h\leq \log_{\lceil m/2\rceil}((n+1)/2)+1$$

查找

B树的查找包含两个基本操作:

1. 在B树中找结点
2. 在结点内找关键字

插入

分裂

分裂

取一个新结点, 在插入 key 后的原结点,从中间位置 ( $\lceil m / 2\rceil)$ 将其中的关键字分为两部分：

• 左部分包含的关键字放在原结点中,
• 右部分包含的关键字放到新结点中,
• 中间位置 $(\lceil m / 2\rceil)$ 的结点插入原结点的父结点。

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

删除

image.png

image.png

image.png

B+树的基本概念

警告

考研对B+树考的不深，就考一些基本概念

$\mathrm{B}+$ 树是应数据库所需而出现的一种 $\mathrm{B}$ 树的变形树。
一棵 $m$ 阶的 $\mathrm{B}+$ 树需满足下列条件:

1. 每个分支结点最多有 $m$ 棵子树（孩子结点）。
2. 非叶根结点至少有两棵子树, 其他每个分支结点至少有 $\lceil m / 2\rceil$ 棵子树。
3. 结点的子树个数与关键字个数相等。
4. 所有叶结点包含全部关键字及指向相应记录的指针, 叶结点中将关键字按大小顺序排列, 并且相邻叶结点按大小顺序相互链接起来。
5. 所有分支结点 (可视为索引的索引) 中仅包含它的各个子结点 (即下一级的索引块) 中 关键字的最大值及指向其子结点的指针。

$m$ 阶的 $\mathrm{B}+$ 树与 $m$ 阶的 $\mathrm{B}$ 树的主要差异:

1. 在 $\mathrm{B}+$ 树中, 具有 $n$ 个关键字的结点只含有 $n$ 棵子树, 即每个关键字对应一棵子树; 而在 $\mathrm{B}$ 树中, 具有 $n$ 个关键字的结点含有 $n+1$ 棵子树。
2. 在 $\mathrm{B}+$ 树中, 每个结点 (非根内部结点) 的关键字个数 $n$ 的范围是 $\lceil m / 2\rceil \leqslant n \leqslant m$ (而根结 点: $1 \leqslant n \leqslant m$ ); 而在 $\mathrm{B}$ 树中, 每个结点 (非根内部结点) 的关键字个数 $n$ 的范围是 $\lceil m / 2\rceil-1$ $\leqslant n \leqslant m-1$ (根结点: $1 \leqslant n \leqslant m-1$ )。
3. 在 $\mathrm{B}+$ 树中, 叶结点包含了全部关键字, 非叶结点中出现的关键字也会出现在叶结点中; 而 在 B 树中, 最外层的终端结点包含的关键字和其他结点包含的关键字是不重复的。
4. 在 B+树中, 叶结点包含信息, 所有非叶结点仅起索引作用, 非叶结点中的每个索引项只 含有对应子树的最大关键字和指向该子树的指针, 不含有该关键字对应记录的存储地址。

可以对B+ 树进行两种查找运算:

1. 一种是从最小关键字开始的顺序查找,
2. 另一种是从根结点开始的多路查找。

image.png