概述#

B 树和 B+ 树是多路平衡查找树（Multi-way Balanced Search Tree），专为磁盘 I/O 设计的数据结构。折半查找和 BST/AVL 都是内存中的查找结构，而数据库索引动辄存储百万条记录，不可能全放内存。B 树/B+ 树的核心优势是：每个结点存储多个关键字，一次磁盘 I/O 读一个结点，大幅减少磁盘访问次数。

例如一棵 1001 阶 B 树，存储 10 亿个关键字只需要 3 层，最多 3 次磁盘访问即可完成查找。

相关概念页面：二叉排序树与 AVL 树、红黑树、查找算法。

m 阶 B 树的定义#

B 树是 m 阶多路平衡查找树，其结点结构如下：

1
┌──┬────┬──┬────┬──┬─ ... ─┬──────┬──┐
2
│P₀│ K₁ │P₁│ K₂ │P₂│       │Kₙ    │Pₙ│
3
└──┴────┴──┴────┴──┴─ ... ─┴──────┴──┘

其中 Kᵢ 为关键字（K₁ < K₂ < … < Kₙ），Pᵢ 为指向子树的指针，子树 Pᵢ 中所有关键字的值在 Kᵢ 和 Kᵢ₊₁ 之间。

B 树的性质#

一棵 m 阶 B 树满足以下性质：

B 树的查找#

B 树的查找是在结点间纵向移动（磁盘 I/O）与在结点内横向比较（内存操作）交替进行的过程：

1. 从根结点开始，将目标 key 与当前结点中的关键字顺序比较
2. 若 key = Kᵢ，查找成功
3. 若 Kᵢ < key < Kᵢ₊₁，沿指针 Pᵢ 进入子树（一次磁盘 I/O）
4. 若到达叶结点（空指针），查找失败

磁盘 I/O 次数 = 查找路径上的结点数 = 树的高度 h。结点内比较在内存中完成，不涉及磁盘访问。

B 树的插入#

插入总是发生在最底层的非叶结点（终端结点）：

1. 查找确定插入位置
2. 若插入后关键字数 ≤ m-1，直接插入，完成
3. 若插入后关键字数 = m（溢出），进行结点分裂

1
分裂前（溢出）:  [K₁ K₂ K₃ K₄ K₅]
2
                      ↑ 中间关键字 K₃ 上提
3

4
分裂后:    父结点 ← [..., K₃, ...]
5
              /              \
6
         [K₁ K₂]          [K₄ K₅]

B 树的删除#

删除后需保证每个结点的关键字数不低于 ⌈m/2⌉ - 1：

1
        [..., 35, ...]
2
        /          \
3
    [20]          [40, 50, 60]   当前结点下溢，右兄弟富余
4
                ↓
5
        [..., 40, ...]           35 下移，40 上提
6
        /          \
7
    [20, 35]      [50, 60]       恢复平衡

B+ 树#

1
         [30 | 60]              ← 内部结点（仅索引）
2
        /    |    \
3
   [10|20] [30|50] [60|80]      ← 内部结点（仅索引）
4
    / | \   / | \   / | \
5
  [叶] → [叶] → [叶] → [叶]    ← 叶结点（存数据，链表相连）

复杂度分析#

实际应用中 m 通常取较大值（几百到上千），使得树高 h 通常只有 3~4 层。

考研高频考点#

• m 阶 B 树非根结点关键字数范围：⌈m/2⌉ - 1 ~ m-1（选择题/填空题高频）
• 含 n 个关键字的 m 阶 B 树的最大高度公式推导（大题常考）
• 插入时结点分裂过程、中间关键字上提（手动建树题）
• 删除时借兄弟与合并操作的判断和执行（手动操作题）
• B 树 vs B+ 树的区别（简答题/选择题必考）
• B+ 树查找必须到叶结点（判断题高频陷阱）
• B+ 树中内部结点关键字个数 = 子树个数（与 B 树不同）
• B 树所有叶结点在同一层的原因（概念题）
• 磁盘 I/O 与 B 树阶数选择的关系（理解题）
• 给定关键字序列画出 B 树构造过程（综合应用题）