考研笔记

B 树及其基本操作

教材原话：「考研大纲对 B 树和 B+树的要求各不相同，重点在于考查 B 树，不仅要求理解 B 树的基本特点，还要求掌握 B 树的建立、插入和删除操作，而对 B+树则只考查基本概念。」

这句话直接决定了 7.4 两节的写法：B 树要练手，B+树只要背清楚差异。

B 树是 二叉排序树 的多路化版本。动机不是「更快」，而是减少磁盘存取次数——B 树常存储在磁盘上，在磁盘上进行查找的次数即目标结点在 B 树上的层次数，决定了 B 树的查找效率。把二路变成 路，树高从 掉到 ，磁盘 I/O 就同比例下降。

口径差异：

教材在 7.4.1 的脚注里留了一句必须知道的话： 「多数教材将 B 树的叶结点定义为失败结点，本书也采用这种定义， 但 408 真题将 B 树的叶结点定义为最底层的终端结点。」 同一个词，教材和真题指的不是同一层。 做真题时看到「叶结点」要按真题口径（最底层有关键字的那层）， 读教材时按教材口径（不带信息的外部结点）。这是本章最容易被无声扣分的一处。 另外，B 树也可写成「B-树」，这里的「-」是连接词，不能读作「减」。

机制

定义

所谓 阶 B 树是所有结点的平衡因子均等于 0 的 路平衡查找树。

一棵 阶 B 树或为空树，或为满足如下特性的 叉树：

  1. 树中每个结点至多有 棵子树，即至多有 个关键字。
  2. 若根结点不是叶结点，则至少有 2 棵子树，即至少有 1 个关键字。
  3. 除根结点外的所有非叶结点至少有 棵子树，即至少有 个关键字。
  4. 所有非叶结点的结构为 。其中 为关键字且 ； 为指向子树根结点的指针，且 所指子树中所有结点的关键字均小于 ， 所指子树中所有结点的关键字均大于 ； 为结点中关键字的个数，。
  5. 所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的失败结点，实际上这些结点并不存在，指向这些结点的指针为空）。

边界辨析：

「 阶」的 是子树数，不是关键字数。 关键字数的上限是 。 这一条错了，后面每一个 都会跟着错。 记忆抓手：结点的孩子个数 该结点中关键字个数 ——关键字是「隔板」，子树是「格子」，格子总比隔板多一个。

以一棵 5 阶 B 树为例（教材图 7.28）：

flowchart TD
    R["22"] --- A["5   11"]
    R --- B["36   45"]
    A --- A1["1   3"]
    A --- A2["6   8   9"]
    A --- A3["13   15"]
    B --- B1["30   35"]
    B --- B2["40   42"]
    B --- B3["47   48   50   56"]
    A1 --- L1["□ 外部结点（第 4 层）"]
    A2 --- L2["□"]
    A3 --- L3["□"]
    B1 --- L4["□"]
    B2 --- L5["□"]
    B3 --- L6["□"]

    classDef inner fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef leaf fill:#ffe0b2,stroke:#e65100,stroke-dasharray:4 3
    class R,A,B,A1,A2,A3,B1,B2,B3 inner
    class L1,L2,L3,L4,L5,L6 leaf

对照定义验算：

  • 结点的孩子个数等于该结点中关键字个数加 1：根结点 1 个关键字 → 2 个孩子；5 11 有 2 个关键字 → 3 个孩子。
  • 除根外的非叶结点至少有 棵子树（至少 个关键字），至多 5 棵子树（至多 4 个关键字）。
  • 结点中的关键字从左到右递增有序，关键字两侧的指针所指子树的关键字落在它划分出的区间内。第二层最左结点的 2 个关键字把值域划分成 3 个区间 、、。
  • 所有叶结点均在第 4 层，代表查找失败的位置。

查找

在 B 树上进行查找与二叉排序树很相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。

B 树的查找包含两个基本操作：

操作在哪里做用什么方法
① 在 B 树中找结点磁盘上沿指针下降，次数 = 结点的层次数
② 在结点内找关键字内存中顺序查找法或折半查找法

这一分工是 B 树全部设计意图的所在：磁盘操作慢，所以要少；内存操作快，所以每个结点可以塞很宽。在磁盘上进行查找的次数即目标结点在 B 树上的层次数，决定了 B 树的查找效率。

查找到叶结点时（对应指针为空），则说明树中没有对应的关键字，查找失败。

高度：两个方向的界

首先要明确：B 树的高度不包括最后的不带任何信息的叶结点所处的那一层（有些书对 B 树的高度的定义中包含最后那一层）。

对任意一棵包含 个关键字、高度为 、阶数为 的 B 树（）：

最小高度（每个结点塞满）：因为每个结点最多 棵子树、 个关键字，所以

最大高度（每个结点最少）：第一层至少 1 个结点；第二层至少 2 个结点；除根外每个非叶结点至少 棵子树，则第三层至少 个结点……第 层至少 个结点。注意到第 层是不包含任何信息的叶结点，对于关键字个数为 的 B 树，叶结点即查找不成功的结点为 个，由此有

例：一棵 3 阶 B 树共有 8 个关键字，则 ，，高度范围为 ，取整数即 。

关联对照：

「叶结点（失败结点）有 个」这条又出现了——折半查找判定树 是 个方形结点， 红黑树 是 个外部 NULL 结点，B 树也是 个失败结点。 本章第三次。 上面最大高度的推导正是靠这一条把「层数」和「关键字数」接起来的。

插入：定位 + 分裂

与二叉排序树的插入操作相比，B 树的插入操作要复杂得多。在 B 树中查找到插入的位置后，并不能简单地将其添加到终端结点（最底层的非叶结点）中，因为此时可能会导致整棵树不再满足 B 树定义中的要求。

  1. 定位。 利用 B 树查找算法，找出插入该关键字的终端结点。（在 B 树中查找 key 时，会找到表示查找失败的叶结点，因此插入位置一定是最底层的非叶结点。）
  2. 插入。 每个非根结点的关键字个数都在 。若结点插入后的关键字个数小于 ，可以直接插入；若插入后的关键字个数大于 ，必须对结点进行分裂。

分裂的方法：取一个新结点，在插入 key 后的原结点，从中间位置 将其中的关键字分为两部分——左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置 的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致 B 树高度增 1。

flowchart LR
    A["(a) 插入前<br/><b>30</b><br/>20 &nbsp;|&nbsp; 50 52"] -->|"插入 60 后，溢出"| B["(b) 结点溢出<br/><b>30</b><br/>20 &nbsp;|&nbsp; <b>50 52 60</b>"]
    B -->|"结点分裂"| C["(c) 分裂后<br/><b>30 52</b><br/>20 &nbsp;|&nbsp; 50 &nbsp;|&nbsp; 60"]

    classDef ok fill:#c8e6c9,stroke:#1b5e20
    classDef bad fill:#ffcdd2,stroke:#b71c1c,stroke-width:2px
    class A,C ok
    class B bad

上图是 的情形：所有结点中最多有 个关键字，插入 60 后 50 52 60 有 3 个关键字，超限。中间位置 即关键字 52 上升到父结点，左边 50 留在原结点，右边 60 进新结点。

分裂是唯一能让 B 树长高的操作，而且它只从根部长高——所以 B 树永远是所有叶结点在同一层的。

删除：三种情况

B 树的删除操作与插入操作类似，但要稍微复杂一些，即要使得删除后的结点中的关键字个数 ，因此将涉及结点的「合并」问题。

第 0 步：把非终端结点的删除转化为终端结点的删除。 当被删关键字 不在终端结点中时，可以用 的前驱（或后继）——即 的左侧子树中「最右下」的元素（或右侧子树中「最左下」的元素）——来替代 ，然后在相应的结点中删除 。 必定落在某个终端结点中，于是转换成了被删关键字在终端结点中的情形。

然后只需讨论终端结点的三种情况：

情况判据动作
① 直接删除所在结点删除前的关键字个数 直接删去该关键字
② 兄弟够借所在结点删除前关键字个数 ，且相邻的右（或左）兄弟结点关键字个数 调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法）
③ 兄弟不够借所在结点删除前关键字个数 ，且相邻的左、右兄弟结点关键字个数都 将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并

情况 ③ 的连锁反应：在合并过程中，双亲结点中的关键字个数会减 1。

  • 若双亲结点是根结点且关键字个数减少至 0（根结点关键字数为 1 时，有 2 棵子树），则直接将根结点删除，合并后的新结点成为根——这是 B 树唯一变矮的方式。
  • 若双亲结点不是根结点，且关键字个数减少到 ，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合 B 树的要求为止。
flowchart TD
    S["删除关键字 k"] --> Q0{"k 在终端结点？"}
    Q0 -->|"否"| P["用前驱/后继 k′ 替代 k<br/>转为删除 k′"]
    P --> Q1
    Q0 -->|"是"| Q1{"该结点关键字数<br/>≥ ⌈m/2⌉ ？"}
    Q1 -->|"是"| C1["① 直接删除<br/>结束"]
    Q1 -->|"否"| Q2{"兄弟关键字数<br/>≥ ⌈m/2⌉ ？"}
    Q2 -->|"是"| C2["② 兄弟够借<br/>父子换位法<br/>结束"]
    Q2 -->|"否"| C3["③ 兄弟不够借<br/>与兄弟 + 双亲关键字合并"]
    C3 --> Q3{"双亲关键字数<br/>减到 ⌈m/2⌉−2 ？"}
    Q3 -->|"根且减到 0"| C4["删根，新结点成为根<br/>树高 −1，结束"]
    Q3 -->|"非根且不足"| Q2
    Q3 -->|"仍合法"| C5["结束"]

    classDef done fill:#c8e6c9,stroke:#1b5e20
    classDef loop fill:#ffcdd2,stroke:#b71c1c,stroke-width:3px
    classDef norm fill:#e3f2fd,stroke:#1565c0
    class C1,C2,C4,C5 done
    class C3,Q3 loop
    class S,Q0,P,Q1,Q2 norm

层次辨析：

插入只会让树长高，删除只会让树变矮，而且都只发生在根。 这是 B 树「所有叶结点在同一层」的维持机制： 中间层永远不会单独增减一层。与 AVL 树 的旋转对比着看—— AVL 是局部换形状，B 树是整层地长和缩。

手算模板

判定合法性（ 阶）：

位置子树数关键字数
根（非叶）
其他非叶结点

插入 key：

  1. 从根查到最底层的非叶结点（终端结点）。
  2. 按序插进去。
  3. 数关键字： → 完； → 分裂。
  4. 分裂：取第 个关键字上升给父亲，左边留原结点，右边进新结点。
  5. 父亲若也满了，回第 3 步。传到根就长高一层。

删除 key：

  1. 不在终端结点 → 用前驱（左子树最右下）或后继（右子树最左下）替代，转为删那个。
  2. 删除前数一下本结点的关键字个数： → 直接删。
  3. 否则看相邻兄弟： → 借（父子换位：兄弟的关键字上去顶父亲，父亲的下来补自己）。
  4. 兄弟也只有 → 合并：自己 + 双亲的分隔关键字 + 兄弟，并成一个结点。
  5. 双亲少了一个关键字，回第 2 步检查双亲。根空了就删根，树矮一层。

记忆抓手：够就直接删，不够先借，借不到再并；并完往上再查一遍。

边界

说法判断说明
「 阶 B 树每个结点有 个关键字」❌至多 棵子树、至多 个关键字
「B 树的叶结点是最底层的终端结点」⚠️教材：叶结点 = 失败结点（不带信息）；408 真题：叶结点 = 最底层终端结点。 看语境切换
「B 树的高度包含叶结点那一层」❌教材定义不包含；有些书包含，做题按教材
「根结点至少有 棵子树」❌根至少 2 棵； 是除根外的非叶结点
「B 树中所有结点的关键字数下限都是 」❌根结点是 1
「插入时新关键字可能插到非终端结点」❌一定插在最底层的非叶结点，因为查找失败必然停在叶结点上方
「分裂时中间关键字留在原结点」❌中间关键字上升到父结点
「B 树可以从中间层长高」❌只能从根长高，所以叶结点永远同层
「删除非终端结点的关键字要重建子树」❌用前驱或后继替代，转为删终端结点
「兄弟够借时只调整两个结点」❌要调三个：本结点、兄弟、双亲（父子换位法）
「合并后一定结束」❌双亲可能因此不足，需逐层上溯
「B 树查找失败时比较次数等于树高」⚠️磁盘存取次数等于层次数；结点内还要再做一次顺序/折半查找

口径差异：

算法竞赛几乎不写 B 树——它的收益在磁盘 I/O，而竞赛全程在内存里跑， 路分支反而不如二叉快。 所以「B 树是为了减少磁盘存取次数」这个动机在算竞视角里是看不见的， 容易把 B 树当成「另一种平衡树」来记，从而记不住为什么结点要那么宽。 这一节的所有数量约束（、分裂点、高度公式）都是从「一个结点 = 一个磁盘块」推出来的， 先接受这个前提，后面的式子才不是死记。

对照速查

量式子
关键字数范围（非根非叶）
子树数范围（非根非叶）
根结点（非叶）子树 ，关键字
最小高度
最大高度
失败结点数
孩子数与关键字数孩子数 关键字数
关键字下限关键字上限
3212
4213
5324
6325

考点

  • 是子树数，关键字数 子树数 。
  • 教材与 408 真题对「叶结点」的定义不同（脚注原文）。
  • 高度的上下界公式及「高度不含叶结点层」。
  • 插入的分裂点是 ，中间关键字上升（2020 命题追踪）。
  • 删除的三种情况与判据（2012、2022 命题追踪），尤其「删除前的关键字个数」这个时点。
  • 父子换位法要动三个结点。
  • 合并会向上传播，根空则树矮一层（2023 命题追踪）。
  • 孩子数 = 关键字数 + 1（2013、2014、2018、2021 反复考）。

链接

反向链接