B树高度定理

概述

B树高度定理给出B树高度的上界，证明B树非常”矮胖”。这是B树作为外存数据结构的核心优势——即使存储海量数据，树的高度仍然很小，从而保证每次操作只需要极少次数的磁盘I/O。

定理陈述

B树高度定理

设一棵最小度为 $t\ge 2$ 的B树包含 $n$ 个关键字，则其高度 $h$ 满足：

$h\le {\log }_t\frac{n+1}{2}$

证明

采用数学归纳法，从B树的最底层向上计数节点数。

第一步：确定第 $h$ 层（叶子层）的节点数

第 $h$ 层是叶子层。根据B树的定义，叶子节点不携带信息，但它们作为哨兵存在。第 $h-1$ 层（最底层的内部节点）的每个节点至少有 $t$ 个子节点（即至少指向 $t$ 个叶子），因此第 $h$ 层至少有 $t^{h-1}\cdot 1$ 个叶子节点。

但我们换一种更直接的方式——从根向下计数：

第二步：确定各层最少节点数

• 第 1 层（根）：至少 $1$ 个节点
• 第 2 层：根至少有 $2$ 个子节点（根至少 $1$ 个关键字，至少 $2$ 个子树），所以至少 $2$ 个节点
• 第 3 层：第 2 层每个节点至少有 $t$ 个子节点，所以至少 $2t$ 个节点
• 第 $j$ 层（$j\ge 2$）：至少 $2t^{j-2}$ 个节点

第三步：计算最少关键字总数

第 $1$ 层（根）至少有 $1$ 个关键字。

第 $2$ 层到第 $h-1$ 层（所有内部节点）的每个节点至少有 $t-1$ 个关键字。

因此，关键字总数 $n$ 满足：

$n\ge 1+(t-1){\sum }_{j=2}^{h-1}2t^{j-2}$

计算求和部分：

${\sum }_{j=2}^{h-1}2t^{j-2}=2{\sum }_{k=0}^{h-3}{t}^k=2\cdot \frac{t^{h-2}-1}{t-1}$

代入得：

$n\ge 1+(t-1)\cdot 2\cdot \frac{t^{h-2}-1}{t-1}=1+2(t^{h-2}-1)=2t^{h-2}-1$

第四步：解出高度上界

由 $n\ge 2t^{h-2}-1$，得：

$n+1\ge 2t^{h-2}$

$t^{h-2}\le \frac{n+1}{2}$

两边取以 $t$ 为底的对数：

$h-2\le {\log }_t\frac{n+1}{2}$

$\boxed{h\le {\log }_t\frac{n+1}{2}+2}$

CLRS的更紧上界

CLRS通过更精细的分析（考虑根节点可以只有 $1$ 个关键字的情况），给出了更紧的上界： $h\le {\log }_t\frac{n+1}{2}$ 这个更紧的界可以通过考虑：当根只有 $1$ 个关键字时，它只有 $2$ 个子节点，从第 $2$ 层开始每层至少 $t$ 个子节点，从而得到 ${\sum }_{j=1}^{h}2t^{j-1}\ge n+1$，即 $2\cdot \frac{t^h-1}{t-1}\ge n+1$，化简后得到 $h\le {\log }_t\frac{n+1}{2}$。

核心性质

1. 高度增长极其缓慢

由于对数函数增长极慢，B树的高度随数据量的增长非常缓慢：

最小度 $t$	关键字数 $n$	高度上界 $h$
2	1,000	$\le 10$
10	1,000,000	$\le 4$
100	10,000,000	$\le 3$
200	$10^9$	$\le 3.15$
501	$10^{12}$	$\le 4$

2. 实际意义：磁盘I/O次数

B树的每次操作（搜索、插入、删除）都需要 $O(h)$ 次磁盘I/O。以实际参数为例：

典型场景

设最小度 $t=200$，存储 $n=10^9$（十亿）个关键字：

• 高度 $h\le {\log }_{200}\frac{10^9+1}{2}\approx {\log }_{200}(5\times 10^8)\approx 3.15$
• 因此 $h\le 4$，即最多只需 4 次磁盘I/O即可定位任意关键字

对比：如果使用平衡二叉搜索树（如AVL树），高度约为 ${\log }_2(10^9)\approx 30$，需要约 30 次磁盘I/O。B树将I/O次数减少了近一个数量级。

3. 最小度与高度的权衡

• $t$ 增大 $\Rightarrow$ 高度 $h$ 减小 $\Rightarrow$ 磁盘I/O次数减少
• $t$ 增大 $\Rightarrow$ 每个节点变大 $\Rightarrow$ 单次磁盘读取时间可能增加（但通常一个节点恰好对应一个磁盘页，读取时间不变）
• $t$ 增大 $\Rightarrow$ 节点内搜索时间增加（从 $O(t)$ 增长），但通常 $t$ 远小于磁盘I/O代价，可以忽略

参见

• B树 — 高度定理所分析的核心数据结构
• 最小度 — 决定高度上界的关键参数
• B树节点的磁盘表示 — 高度定理的工程意义所在——减少磁盘I/O