B树高度定理
概述
B树高度定理（B-Tree Height Theorem）：一棵有 个关键字、最小度数 的 B 树，其高度 满足 。该定理是 B 树作为高效磁盘数据结构的核心保证，确保磁盘 I/O 次数为 。
定理陈述
形式化陈述
定理（CLRS Theorem 18.1）：设 是一棵最小度数为 的 B 树，包含 个关键字，高度为 （根所在层为第 0 层，叶子层为第 层），则
前提条件：
- 是一棵合法的 B 树，满足 B 树的五条性质
- 最小度数 （即每个非根内部结点至少有 个关键字、 个子结点）
- 为 B 树中存储的关键字总数
证明概要
证明思路
证明的核心是利用 B 树的最小度数性质，建立各层关键字数的下界，从而推导出高度的上界。
步骤 1：分析根结点的关键字数下界
B 树性质 1a（根至少有 1 个关键字）和性质 1b（若根非叶子则至少有 2 个子结点）：
- 若树的高度 （仅有根结点），则根至少有 1 个关键字
- 若 ，则根至少有 2 个关键字（因为根至少有 2 个子结点，每个子结点对应一个分隔关键字）
统一表述：根至少有 2 个关键字（当 时； 时定理显然成立）
步骤 2：分析第 1 层至第 层的结点数下界
根至少有 2 个子结点（ 时）。对于深度 的每个结点，由 B 树性质 3（非根内部结点至少有 个子结点），每个结点至少产生 个子结点。
因此各层的结点数下界为：
- 第 0 层（根）： 个结点
- 第 1 层： 个结点
- 第 2 层： 个结点
- 第 层（）： 个结点
步骤 3：分析第 层（叶子层）的关键字数下界
第 层是叶子层，所有叶子结点都在同一层（B 树性质 4）。叶子层至少有 个结点。
每个叶子结点至少有 个关键字（B 树性质 3），因此叶子层至少包含： 个关键字。
步骤 4：建立总关键字数的下界
非叶子层（第 0 层到第 层）的关键字数下界：
- 第 0 层（根）： 个关键字
- 第 1 层到第 层：每层至少 个结点，每个结点至少 个关键字
为简化推导，使用更紧的下界。注意到第 层至少有 个叶子结点，而 B 树中所有 个关键字分布在所有层中。利用叶子层的下界直接得到：
步骤 5：解出高度上界
由 ：
更精确的分析（考虑所有层的贡献）可得：
证毕。
关键推论
- 磁盘 I/O 次数：B 树的搜索、插入、删除操作需要访问 个结点。若每个结点恰好对应一次磁盘读取，则磁盘 I/O 次数为
- 与红黑树的高度对比：当 时，B 树退化为 2-3-4 树（与红黑树等价），高度上界为 ，与 红黑树高度定理 一致
- 增大 的效果： 越大，B 树越”矮胖”，高度越小，磁盘 I/O 次数越少。但每个结点更大，单次磁盘读取的数据量增加
- 实际选择 ：通常选择 使得一个结点恰好填满一个磁盘块（如 4KB），以最大化磁盘带宽利用率
应用场景
- 算法导论 Ch18：B 树高度定理是 B 树作为高效外部存储数据结构的理论保证，直接决定了数据库索引的性能
- 数据库系统：MySQL InnoDB 引擎使用 B+ 树（B 树的变体）作为索引结构，高度通常为 3-4 层，即可管理数十亿条记录
- 文件系统：NTFS、ext4 等文件系统使用 B 树或其变体管理文件目录和磁盘块分配
- 键值存储：LevelDB、RocksDB 等 LSM-Tree 存储引擎在内存中使用类似 B 树的结构进行快速查找