B树和B+树

B 树

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

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

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

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

性质推导

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

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

• 最小高度

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

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

第 2 层有 个节点；

第 3 层有 个节点；

则 层共有 个节点，这些节点中都有 个关键字。则一共有

个关键字。则又有：

，变形得到 ，即含有 个关键字阶为 的 B 树的最小高度为

• 最大高度

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

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

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

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

第 h 层有 个节点（这一层已经是终端节点层了）

则第 层共有 个节点。

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

，变形得到

B+树

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

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

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