B树

概述

B树是一种平衡的多路搜索树，专为磁盘等外存设备设计，能有效减少I/O次数。与二叉搜索树不同，B树的每个节点可以包含多个关键字和多个孩子，使得树的高度非常低，从而在磁盘访问代价远高于内存访问的场景下获得极高的查询效率。

定义

B树的严格定义

一棵最小度为 $t\ge 2$ 的B树满足以下五条性质：

1. 每个节点最多有 $2t-1$ 个关键字
2. 根节点至少有 $1$ 个关键字（若树非空）
3. 非根的内部节点至少有 $t-1$ 个关键字
4. 所有叶子节点在同一层（深度相同），且不携带信息（可作为哨兵）
5. 关键字有序：设节点 $x$ 有 $n$ 个关键字 $k_1,k_2,\dots ,k_n$，则满足
   • $k_1<k_2<\cdots <k_n$
   • 子树 $c_i$ 中所有关键字满足：k_{i-1} < \text{（c_i中所有关键字）} < k_i（约定 $k_0=-\infty$，$k_{n+1}=+\infty$）

节点结构示意

一个包含 $n$ 个关键字的B树节点具有如下结构：

$\underset{\text{子树指针}}{\underbrace{[c_1]}}\underset{\text{关键字}}{\underbrace{[k_1]}}\underset{\text{子树指针}}{\underbrace{[c_2]}}\underset{\text{关键字}}{\underbrace{[k_2]}}\cdots \underset{\text{关键字}}{\underbrace{[k_n]}}\underset{\text{子树指针}}{\underbrace{[c_{n+1}]}}$

其中 $n$ 满足 $t-1\le n\le 2t-1$（根节点除外），子树数量为 $n+1$。

核心性质

1. 高度上界

由B树高度定理，含 $n$ 个关键字的B树高度满足：

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

这意味着B树非常”矮胖”——即使存储海量数据，树的高度也非常小。

2. 操作复杂度

• 搜索：$O(h)$ 次磁盘I/O，$O(t{\log }_{t}n)$ CPU时间
• 插入：$O(h)$ 次磁盘I/O（单次向下遍历 + 至多一次分裂向上传播）
• 删除：$O(h)$ 次磁盘I/O（单次向下遍历 + 至多一次合并向上传播）

3. 平衡性

B树始终保持严格平衡——所有叶子节点始终位于同一层。这与AVL树、红黑树等通过旋转维护平衡的二叉搜索树不同，B树通过分裂和合并操作来维持平衡。

4. 与二叉搜索树的关系

当 $t=2$ 时，B树退化为一种特殊的二叉搜索树（2-3-4树）。B树可以看作是二叉搜索树向多路搜索树的自然推广。

发明历史

B树由 Rudolf Bayer 和 Edward M. McCreight 于 1972年 在 Boeing Scientific Research Labs 发明。关于”B”的含义，两位发明者说法不一——可能是 “Boeing”、“Bayer”、“balanced” 或 “broad”，至今没有定论。

参见

• 最小度 — B树的核心参数定义
• B树高度定理 — B树高度上界的严格证明
• B树的插入操作 — 分裂策略与插入流程
• B树的删除操作 — 借关键字与合并策略
• B树节点的磁盘表示 — 磁盘I/O优化的底层设计
• B+树 — B树的重要工程变体
• 二叉搜索树 — B树的基础前置概念