B树和B+树

B 树

B 树，即多路平衡查找树。B 树的一个节点中的关键字可以有 $n$ 个，那这个节点的子节点的数量就是 $n+1$ 个，因此是多路的；B树是平衡树，且它的每个节点的平衡因子为0。

我们区分两个概念：终端节点与叶节点

B 树的所有节点的最大的子节点个数（也等于所有节点的最多的关键字的个数 + 1）称为 B 树的阶(order)。一个 $m$ 阶的 B 树具有以下的性质：

1. 每个节点中的各个关键字以升序排列
2. 每一个非根非叶节点都含有 $k$ 个子节点和 $k-1$ 个关键字，其中 $\lceil m/2 \rceil<=k<=m$，如果记节点有 $n$ 个关键字，则 $n$ 满足 $\lceil m / 2 \rceil - 1 <= n <= m - 1$
3. 若根节点不是终端节点，则至少含有2个子树
4. 所有的终端节点都位于同一层，所有叶子节点都位于同一层

性质推导

下面对于高度的定义中忽略叶子节点层（失败节点层）

一个总共含有 $n$ 个关键字，阶为 $m$ 的 B 树的最大高度和最小高度是多少？

• 最小高度

要使得 B 树的高度最小，那么每个节点要尽可能地塞满，即每个节点都有 $m-1$ 个关键字，也即每个节点都有 $m$ 个子节点。

对于第 1 层（根所在的层），只能有 1 个节点；

第 2 层有 $m$ 个节点；

第 3 层有 $m^2$个节点；

则 $h$ 层共有
$m^0 + m^1 + ...+ m^{h-1} = (m^h - 1) / (m - 1)$ 个节点，这些节点中都有 $m-1$ 个关键字。则一共有

$(m-1) * ((m^h - 1) / (m - 1)) = m^h - 1$ 个关键字。则又有：

$(m^h - 1) >= n$，变形得到 $n >= \log_m {(n+1)}$，即含有 $n$ 个关键字阶为 $m$ 的 B 树的最小高度为 $\log_m{(n+1)}$

• 最大高度

要使得 B 树的高度最大，那么每个节点要尽可能地塞不满，但是由于 B 树的性质规定了每个非根非叶节点中的子节点数最少为$\lceil m/2 \rceil$ 个。记为 $k$

第 1 层有 1 个节点（将根所在的那层规定为第 1 层）

第 2 层有 2 个节点（因为规定了根节点至少要有两个子节点，即第 1 层至少要有 2 个节点）

第 3 层有 $2k$ 个节点（第 1 层的 2 个节点，每个节点的子节点都取最小值 k）

第 h 层有 $2k^{h-2}$ 个节点（这一层已经是终端节点层了）

则第 $h+1$ 层共有 $2k^{h-1}$ 个节点。

我们知道共有 $n$ 个关键字的B树，失败节点的个数其实就是 $n+1$ 个，所以第 h + 1 层最多有 n + 1 个节点。所以有

$n+1>=2k^{h-1}$，变形得到 $h <= \log_k {(n+1)/2 + 1}$

B+树

叶子节点中的每个关键字就是数据库中的索引，它还持有相应记录（元组）的指针

B+树的所有节点的关键字的最大数目称为B+树的阶（同时也是节点的最大子节点数），它具有如下性质：

1. 每个分支节点最多有$m$棵子树
2. 非叶根节点至少有2根子树，其他分支节点最少有$\lceil m/2 \rceil$个子树
3. 每个节点的关键字数目和子树数目相同
4. 所有叶子节点包含全部关键字及指向相应记录的指针，叶子节点中关键字的大小依次升序排列，并且相邻叶子节点有指向下一个叶子节点的指针
5. 分支节点中的每个关键字是其子树中的最大关键字的副本。B+树的叶子节点包含全部的关键字及指向对应记录的指针，所有非叶节点仅起到索引作用，即索引的索引