考研全科复习资料

408

数据结构

B 树与 B+ 树

定位信息

项目	内容
章节	第六章查找 · 6.6
知识单元编号	DS-06-06
核心概念	B 树定义、B 树查找/插入/分裂、B+ 树定义与特点、B 树 vs B+ 树对比
前置知识	二叉搜索树、多路查找概念
考试权重	★★★★（高频重点，选择题和综合题常考）

知识点讲解

一、B 树（B-Tree）的定义

B 树是一种多路平衡查找树，适用于磁盘等外部存储。一棵 m 阶 B 树满足：

每个结点最多有 m 棵子树（即最多 m-1 个关键字）；
除根结点外，每个结点最少有 ⌈m/2⌉ 棵子树（即最少 ⌈m/2⌉-1 个关键字）；
根结点最少有 2 棵子树（即最少 1 个关键字，除非树只有根结点）；
所有叶子结点在同一层（即所有失败结点在同一层，B 树的高度只算到最下层内部结点）；
每个结点的结构为：(n, P₀, K₁, P₁, K₂, P₂, ..., Kₙ, Pₙ)，其中 n 为关键字个数，Kᵢ 递增排列，Pᵢ 为子树指针。

B 树的高度： 对于 n 个关键字、m 阶的 B 树，高度 h 满足： $\log_m(n+1) \leq h \leq \log_{\lceil m/2 \rceil} \frac{n+1}{2} + 1$

二、B 树的查找操作

B 树的查找类似 BST 的多路推广：

在当前结点中顺序查找（或折半查找）关键字 Kᵢ；
若找到，查找成功；
若未找到且 key < Kᵢ，沿 Pᵢ₋₁ 指针进入下一层；
若到达叶子层仍未找到，查找失败。

三、B 树的插入操作

插入步骤：

先在叶子层找到应插入的结点；
若该结点关键字数 < m-1，直接插入；
若该结点关键字数 = m-1（满），需分裂：
- 取中间关键字 Kₘᵢᵈ 上提到父结点；
- 原结点分裂为左（K₁~Kₘᵢᵈ₋₁）和右（Kₘᵢᵈ₊₁~Kₘ₋₁）两个结点；
- 若父结点也满，递归分裂，最坏情况增加一层（新根）。

四、B 树的删除操作

删除分两种情况：

删除非终端结点关键字： 用中序前驱（左子树最右）或后继（右子树最左）替代，转化为删除终端结点关键字；
删除终端结点关键字：
- 若删除后关键字数 ≥ ⌈m/2⌉-1，直接删除；
- 若关键字数不足：向兄弟借关键字（旋转），或与兄弟合并。

五、B+ 树的定义

B+ 树是 B 树的变体，主要用于数据库和文件系统索引。m 阶 B+ 树满足：

每个结点最多 m 棵子树；
非叶根结点至少 2 棵子树，其他内部结点至少 ⌈m/2⌉ 棵子树；
所有关键字都在叶子结点中出现，叶子结点包含全部关键字及指向记录的指针；
非叶结点仅起索引作用，包含子树中最大（或最小）关键字；
叶子结点用链表串联，支持范围查找。

六、B 树 vs B+ 树对比表（重要！）

对比维度	B 树	B+ 树
关键字位置	所有结点都存关键字	仅叶子结点存关键字
非叶结点作用	既索引又存数据	仅起索引作用
叶子结点链表	无	有，支持顺序/范围查找
查找路径	不同关键字在不同层找到	所有关键字都在叶子层找到
查找稳定性	不稳定（可能在任意层命中）	稳定（一定在叶子层命中）
范围查找	效率低	高效（沿叶子链表遍历）
适合场景	文件系统索引	数据库索引（MySQL InnoDB）

七、B 树插入分裂伪代码（C 风格）

// m 阶 B 树结点定义
#define MAX_KEYS (m - 1)
#define MIN_KEYS ((m + 1) / 2 - 1)  // ⌈m/2⌉ - 1

typedef struct BTreeNode {
    int n;                          // 当前关键字个数
    KeyType keys[MAX_KEYS + 1];     // 关键字数组（多留一个用于分裂）
    struct BTreeNode* children[MAX_KEYS + 2]; // 子树指针数组
    bool isLeaf;                    // 是否为叶子结点
} BTreeNode;

// 在未满的结点 x 中插入关键字 key
void BTree_InsertNonFull(BTreeNode* x, KeyType key) {
    int i = x->n - 1;
    if (x->isLeaf) {
        // 叶子结点：直接找到位置插入
        while (i >= 0 && key < x->keys[i]) {
            x->keys[i + 1] = x->keys[i]; // 后移关键字
            i--;
        }
        x->keys[i + 1] = key;
        x->n++;
    } else {
        // 内部结点：找到合适的子树继续插入
        while (i >= 0 && key < x->keys[i])
            i--;
        i++;
        if (x->children[i]->n == MAX_KEYS) {
            // 子树已满，先分裂
            BTree_SplitChild(x, i);
            if (key > x->keys[i])
                i++;
        }
        BTree_InsertNonFull(x->children[i], key);
    }
}

// 分裂 x 的第 i 个子结点（已满）
void BTree_SplitChild(BTreeNode* x, int i) {
    BTreeNode* y = x->children[i];    // 待分裂的子结点
    BTreeNode* z = CreateNode();       // 新建右半部分结点
    z->isLeaf = y->isLeaf;
    int mid = (m - 1) / 2;            // 中间位置
    
    // 复制右半部分关键字到 z
    z->n = y->n - mid - 1;
    for (int j = 0; j < z->n; j++)
        z->keys[j] = y->keys[mid + 1 + j];
    
    // 如果不是叶子，复制对应的子树指针
    if (!y->isLeaf) {
        for (int j = 0; j <= z->n; j++)
            z->children[j] = y->children[mid + 1 + j];
    }
    y->n = mid;                       // 左半部分关键字数
    
    // 将中间关键字上提到父结点 x
    // 在 x 中腾出位置
    for (int j = x->n; j > i; j--) {
        x->children[j + 1] = x->children[j];
        x->keys[j] = x->keys[j - 1];
    }
    x->keys[i] = y->keys[mid];       // 中间关键字上提
    x->children[i + 1] = z;           // z 成为 x 的新子树
    x->n++;
}

记忆辅助

"B 树所有结点都存数据，B+ 树只有叶子存数据" — 最核心区别。
"B+ 叶子串成链，范围查询它最强" — B+ 树叶子链表是范围查询高效的根本原因。
"插入满了就分裂，中间上提父结点" — B 树插入分裂的核心步骤。
"删除不够就借或合并，先借兄弟再合并" — B 树删除的调整策略。
"m 阶 B 树，最多 m-1 个关键字，最少 ⌈m/2⌉-1 个" — 关键字数量的上下界。

例题精解

例题 1：B 树插入与分裂

在一棵 3 阶 B 树中依次插入 {10, 20, 30, 15, 25}，画出最终 B 树。

解题四步法：

① 审题： 3 阶 B 树，每个结点最多 2 个关键字，最少 ⌈3/2⌉-1 = 1 个关键字（非根）。

② 分析： 按插入规则逐步操作，满时分裂。

③ 过程：

插入 10：根结点 [10]
插入 20：根结点 [10, 20]（未满，直接插入）
插入 30：根结点 [10, 20, 30]（3 个关键字，超过 m-1=2，需分裂）
- 中间关键字 20 上提为新根
- 分裂为 [10] 和 [30]

      [20]
     /    \
  [10]    [30]

插入 15：15 < 20 → 进入左子 [10]，插入后 [10, 15]（未满）

      [20]
     /    \
 [10,15]  [30]

插入 25：25 > 20 → 进入右子 [30]，插入后 [25, 30]（未满）

      [20]
     /    \
 [10,15] [25,30]

④ 结论： 最终 3 阶 B 树如上图所示，根结点 1 个关键字，两个子结点各 2 个关键字，高度为 2。

例题 2：B 树 vs B+ 树性质辨析

判断以下说法的正误： (1) B 树和 B+ 树的所有结点都存储关键字。 (2) B+ 树的叶子结点用链表连接。 (3) B 树适合范围查找。 (4) 3 阶 B 树的每个结点最多有 3 个关键字。

解题四步法：

① 审题： 四个关于 B 树和 B+ 树的说法判断正误。

② 分析： 逐条依据定义验证。

③ 验证：

(1) ❌ 错误。B 树所有结点存关键字，但 B+ 树只有叶子结点存完整关键字，内部结点只存索引。
(2) ✅ 正确。B+ 树的叶子结点用链表串联，支持高效范围查找。
(3) ❌ 错误。B 树不支持高效范围查找（叶子不在同一层且无链表），B+ 树才适合范围查找。
(4) ❌ 错误。m 阶 B 树每个结点最多 m-1 = 2 个关键字（不是 m 个）。

④ 结论： (1) 错 (2) 对 (3) 错 (4) 错。关键区分：m 阶 B 树最多 m-1 个关键字，B+ 树叶子链表支持范围查找。

考情分析

维度	说明
考频	高频，选择题必考，综合题常考
题型	选择题（B 树/B+ 树性质、关键字数量计算、高度计算）、综合题（插入/删除过程）
命题趋势	B 树与 B+ 树的区别是必考知识点；插入分裂过程的模拟
常见陷阱	m 阶 B 树最多 m-1 个关键字（不是 m 个）；B 树和 B+ 树叶子层的差异

易错点

m 阶 B 树每个结点最多 m-1 个关键字、m 棵子树，不是 m 个关键字！ 这是最常见的错误。
B 树所有叶子结点在同一层（指失败结点），不代表数据只存叶子。 B 树的关键字分布在所有层次，B+ 树才集中在叶子。
B+ 树的内部结点不存数据指针，只存索引。 因此同样的磁盘页，B+ 树的内部结点可以容纳更多关键字，树更矮，I/O 更少。
B 树插入分裂时，中间关键字是"上提"到父结点，不是"复制"。 原结点中该关键字不再保留（在父结点中）。
B+ 树的查找路径长度一致（都在叶子层命中），查找时间稳定。 B 树可能在任意层命中，时间不稳定。

来源标注

来源	说明
王道考研	2026 版数据结构讲义 · 第六章查找
天勤考研	数据结构高分笔记 · 查找部分
严蔚敏	《数据结构（C 语言版）》第 9 章
教材参考	《数据结构》（第 5 版）李春葆；《数据库系统概引》B+ 树部分

408 ​

数据结构 ​

B 树与 B+ 树 ​

408

数据结构

B 树与 B+ 树