🌳 408 B 树 / B+ 树 终极完整版笔记

核心痛点解决

B 树规则多、操作繁琐,极易混淆。本笔记按 408 考察频率 排序。 【口诀 + 可折叠手算例子 + 破局思路 + 避坑指南 + 高度计算】,帮你把 B 树的插入、删除、查找、高度彻底吃透。


0. B 树 vs B+ 树 核心区别(选择题必背)

一句话记忆

“B 树节点存数据,B+ 树叶子存数据;B 树查找到即止,B+ 树必须查到叶子”。

B 树与 B+ 树对比(408 高频)

对比项m 阶 B 树m 阶 B+ 树(408 教材标准)
数据存储位置所有节点(含非叶)都存数据(记录指针)只有叶子节点存数据(记录指针)
叶子节点没有链表相连叶子节点用链表相连,支持顺序查找与范围查找
查找过程找到关键字即可停止(可能停在非叶节点)必须查找到叶子节点才能确定
非叶节点作用存键值 + 数据 + 子树指针只存各子树最大关键字 + 子树指针(纯索引)
关键字与子树数n 个关键字对应 n+1 棵子树n 个关键字对应 n 棵子树
关键字重复性所有节点关键字互不重复非叶节点的关键字都是叶子节点最大值的副本(重复出现)
应用场景文件系统、少量数据库关系型数据库索引主流(如 MySQL InnoDB)

📌 极简口诀:“B 树到处存,B+ 树叶子存;B 树查一半,B+ 树查到底。”


1. B 树的定义与性质(基础必背)

408 最重要的术语区分:终端结点(叶结点) vs 失败结点!

在 408 考研(王道 & 严蔚敏教材)中,B 树底部有两层概念,做题时千万别搞混:

  1. 终端结点(真题中常直接称为“叶结点”):处于树的最下层、含有实际关键字的节点(也就是插入、删除真正操作的节点,在计算树高 时计入高度)。
  2. 失败结点(又称外部结点 / 虚设叶子):处于终端结点再往下一层的空指针(NULL),不带任何信息,表示查找失败的位置(在计算树高 时不计入高度!若含 个关键字,则必有 个失败结点)。 👉 做题铁律:当 408 真题说“插入到叶结点”、“删除导致叶结点变化”时,指的都是带关键字的终端结点!

m 阶 B 树的核心性质

  1. 每个节点最多有 m 棵子树(m-1 个关键字)。
  2. 根节点若不是终端结点(即高度 ),至少有 2 棵子树(1 个关键字)。
  3. 除根以外的所有非空节点(含内部节点与终端节点)至少有 ⌈m/2⌉ 棵子树(⌈m/2⌉ - 1 个关键字)。
  4. 所有的终端结点(叶结点)都在同一层;所有的失败结点也都在同一层(第 h+1 层)。
  5. 节点内的关键字严格递增有序排列。

📌 极简口诀:“根二,非根半,叶子同层,关键字有序。”


2. B 树“阶”与“关键字数量”对照表

m 阶 B 树的节点关键字数量范围

节点类型最少关键字数最多关键字数最少子树数(分叉数)最多子树数(分叉数)
根节点(至少 2 层时)1m - 12m
除根外的节点(含终端结点)⌈m/2⌉ - 1m - 1⌈m/2⌉m
失败节点(空指针层,不算高度)0000

📌 极简口诀:“根最少 1 个关键字,非根最少 ⌈m/2⌉-1 个;最多都是 m-1 个。”

示例:5 阶 B 树

  • 根节点:最少 1 个关键字,最多 4 个关键字。
  • 非根节点:最少 ⌈5/2⌉ - 1 = 2 个关键字,最多 4 个关键字。
  • 子树数 = 关键字数 + 1。

3. B 树高度计算公式(408 高频计算题)

m 阶 B 树的高度范围(含 n 个关键字,高度 h 不含失败结点层)

  • 最小高度:让每个节点尽可能满(每个节点都有 m-1 个关键字、m 棵子树)。
    • 公式:
  • 最大高度:让每个节点尽可能空(根 1 个关键字 2 分叉,其余节点 ⌈m/2⌉-1 个关键字 ⌈m/2⌉ 分叉)。
    • 破局记忆法(利用 失败结点数 = n + 1):第 h+1 层(失败结点层)最少有 个失败结点,因此:

📌 极简口诀:“最小高度看满树,最大高度用失败结点数 n+1 >= 2 * k^(h-1) 反推!”


4. B 树的查找

一句话记忆

“节点内二分(或顺序),节点间逐层(读磁盘)”。

查找过程

  1. 从根节点开始(常驻内存)。
  2. 在节点内进行顺序或二分查找(在内存中进行)。
  3. 如果找到,返回;如果没找到,根据关键字大小沿着指针读磁盘进入对应的子树。
  4. 直到走到空指针(失败节点),查找失败。

5. B 树的插入(含分裂操作)

一句话记忆

“初始必插终端(叶)节点,满了就从 ⌈m/2⌉ 处分裂,中间上移”。

插入过程(3 步)

  1. 查找插入位置:先查找该关键字,若不存在,必定停在最底层的终端结点(叶结点)。
  2. 插入关键字:将关键字插入到该终端结点中。
  3. 判断是否溢出:
    • 如果节点关键字数量 ≤ m-1,插入完成。
    • 如果节点关键字数量 = m,溢出,需要分裂。

分裂操作(关键!):

  • 将节点中间的第 ⌈m/2⌉ 个关键字上移到父节点。
  • 左边 [1 ... ⌈m/2⌉-1] 留在原节点,右边 [⌈m/2⌉+1 ... m] 放入新节点。
  • 如果父节点也溢出,继续向上分裂;若根节点分裂,则树高 + 1(B 树唯一长高的方式:向上长高)。

6. B 树的删除(含借兄弟和合并)

一句话记忆

“非叶删转叶子删,不够先向兄弟借(父下移、兄上移),兄弟没得借就合并(连同父元素一起合)”。

删除的两种情况

情况 1:删除的关键字在非叶(非终端)节点

  • 用直接前驱(左子树最右下元素)或直接后继(右子树最左下元素)替代该关键字。
  • 然后转化为删除终端结点(叶结点)中的那个前驱或后继! 👉 重要推论:B 树的任何删除操作,最终都会转化为对最底层叶结点(终端结点)的删除,因此删除操作一定会导致叶结点发生变化!

情况 2:删除的关键字在叶结点(终端结点)

  • 够删:若删除后,节点关键字数量 ≥ ⌈m/2⌉ - 1,直接删除结束。
  • 不够删(下溢,< ⌈m/2⌉ - 1):
    • ① 兄弟够借(相邻左或右兄弟关键字数 ≥ ⌈m/2⌉):父下移,兄上移(夹心饼干旋转)。
      • 向右兄弟借:父节点分隔关键字下移到当前节点末尾;右兄弟的最小关键字上移到父节点。
      • 向左兄弟借:父节点分隔关键字下移到当前节点开头;左兄弟的最大关键字上移到父节点。
    • ② 兄弟不够借(左右兄弟关键字数均 = ⌈m/2⌉ - 1):合并。
      • 将当前剩余关键字、父节点中的分隔关键字、以及相邻兄弟节点合并成一个新节点。
      • 若导致父节点也下溢,继续向上传播;若根节点最后一个关键字被下移合并,则树高 - 1。

📋 B 树 / B+ 树 速查表(重点背诵)

对比项m 阶 B 树m 阶 B+ 树
数据位置所有节点只有叶子节点
叶子链表无有(支持顺序 + 随机查找)
查找终点找到即止必须到叶子
节点关键字与子树n 个关键字,n+1 棵子树n 个关键字,n 棵子树
根节点关键字范围1 ~ m-12 ~ m(若非叶)
非根节点关键字范围⌈m/2⌉ - 1 ~ m-1⌈m/2⌉ ~ m
树高公式(408 只考 B 树)不考公式(每个节点最多 m 个键值)

📝 历年真题精选(实战演练·破局版)

真题 1(2009 年 408 真题 · B 树性质)

题目:下列关于非空 B 树的叙述中,正确的是( )。 I. 插入操作可能增加树的高度 II. 删除操作一定会导致叶结点的变化 III. 查找某关键字一定是要查找到叶结点 IV. 插入的新关键字最终位于叶结点中 A. 仅 I B. 仅 I、II C. 仅 III、IV D. 仅 I、II、IV

真题 2(B 树插入)

题目:在一棵 3 阶 B 树中,插入关键字 5 后,节点 [3, 4] 变成 [3, 4, 5],接下来应该( )。 A. 直接插入,结束 B. 分裂,中间元素上移 C. 删除一个元素 D. 必定增加树高

真题 3(B+ 树)

题目:下列关于 B+ 树的叙述中,错误的是( )。 A. B+ 树的所有数据都在叶子节点 B. B+ 树的叶子节点用链表相连 C. B+ 树的查找一定查到叶子节点 D. B+ 树的非叶节点也存数据记录

真题 4(B 树高度计算 · 经典必刷)

题目:一棵含 15 个关键字的 4 阶 B 树,含关键字的节点个数最多是多少?最大高度是多少?