写在前面

B树

定义

一棵B树$T$是具有以下性质的有根树(根为$T.root$)

1. 每个结点$x$有以下属性:

   • $x.n$: 当前存储在节点$x$中的关键字个数

   • $x.n$个关键字本身: $x.key_1$, $x.key_2$, … $x.key_{x.n}$, 以非降顺序存放, 即 \(x.key_1\leq x.key_2\leq ...\leq x.key_{x.n}.\)

   • $x.leaf$, 布尔值, 如果$x$是叶结点, 为true, 内部节点为false;

2. 内部节点$x$还包含$x.n+1$个指向其孩子的指针 $x.c_1, x.x_2, …,x.c_{x.n+1}$ .叶结点没有孩子, 所以$c_i$无定义.

3. 关键字$x.key_i$ 对存储在各子树中的关键字范围加以分割, 如果$k_i$ 为任意一个存储在以 $x.c_i$ 为根的子树中的关键字, 那么 \(k_1\leq x.key_1\leq k_2\leq x.key_2\leq ...\leq x.key_{x.n}\leq x.key_{x.n+1}.\)

4. 每个叶结点都有相同的深度, 树的高度为$h$.

5. 每个结点所包含的关键字个数有上界和下界, 用最小度数$t\geq2$ 表示

   • 除了根节点以外的每一个节点必须至少有$t-1$个关键字, 所以除了根节点以外的每个内部节点至少有 $t$个孩子, 树非空, 则至少有一个关键字.
   • 每个结点至多可包含 $2t-1$个关键字, 因此, 一个内部节点至多可有 $2t$ 个孩子, 当一个节点恰好有 $2t-1$ 个关键字时, 称该节点是满的
   • $t=2$时候, B树是简单的, 内部节点有2,3,4个孩子, 成为2-3-4树.
   • 树的高度和$t$成反比.

树高

如果 $n\geq1$, 那么对任意一棵包含 $n$ 个关键字, 高度为 $h$ , 最小度 $t\geq 2$ 的 B 树 $T$, 有

\[h\leq \log_t \frac{n+1}2\]

证明:

B 树 $T$ 的根至少包含一个关键字, 而且所有其他节点至少包含 $t-1$个关键字, 所以高度为 $h$ 的 B 树 $T$ 在深度 $1$ 至少包含 $2$ 个节点, 在深度 $2$ 至少包含 $2t$ 个节点, 深度 $3$ 至少包含 $2t^2$个节点, 直到深度为$h$ , 包含$2t^{h-1}$ 个节点. 于是有(其中乘的$t-1$是叶节点的数量)

\[n\geq 1+(t-1)\sum_{i=1}^h2t^{i-1}=1+2(t-1)\left( \frac{t^h-1}{t-1}\right)=2t^h-1,\]

即

\[t^h\leq \frac{n+1}2\iff h\leq\log_t\frac{n+1}2.\]