🌳 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 树底部有两层概念,做题时千万别搞混:
- 终端结点(真题中常直接称为“叶结点”):处于树的最下层、含有实际关键字的节点(也就是插入、删除真正操作的节点,在计算树高 时计入高度)。
- 失败结点(又称外部结点 / 虚设叶子):处于终端结点再往下一层的空指针(NULL),不带任何信息,表示查找失败的位置(在计算树高 时不计入高度!若含 个关键字,则必有 个失败结点)。 👉 做题铁律:当 408 真题说“插入到叶结点”、“删除导致叶结点变化”时,指的都是带关键字的终端结点!
m 阶 B 树的核心性质
- 每个节点最多有
m棵子树(m-1个关键字)。- 根节点若不是终端结点(即高度 ),至少有 2 棵子树(1 个关键字)。
- 除根以外的所有非空节点(含内部节点与终端节点)至少有
⌈m/2⌉棵子树(⌈m/2⌉ - 1个关键字)。- 所有的终端结点(叶结点)都在同一层;所有的失败结点也都在同一层(第
h+1层)。- 节点内的关键字严格递增有序排列。
📌 极简口诀:“根二,非根半,叶子同层,关键字有序。”
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 树的查找
一句话记忆
“节点内二分(或顺序),节点间逐层(读磁盘)”。
查找过程
- 从根节点开始(常驻内存)。
- 在节点内进行顺序或二分查找(在内存中进行)。
- 如果找到,返回;如果没找到,根据关键字大小沿着指针读磁盘进入对应的子树。
- 直到走到空指针(失败节点),查找失败。
5. B 树的插入(含分裂操作)
一句话记忆
“初始必插终端(叶)节点,满了就从 ⌈m/2⌉ 处分裂,中间上移”。
插入过程(3 步)
- 查找插入位置:先查找该关键字,若不存在,必定停在最底层的终端结点(叶结点)。
- 插入关键字:将关键字插入到该终端结点中。
- 判断是否溢出:
- 如果节点关键字数量
≤ m-1,插入完成。- 如果节点关键字数量
= m,溢出,需要分裂。分裂操作(关键!):
- 将节点中间的第
⌈m/2⌉个关键字上移到父节点。- 左边
[1 ... ⌈m/2⌉-1]留在原节点,右边[⌈m/2⌉+1 ... m]放入新节点。- 如果父节点也溢出,继续向上分裂;若根节点分裂,则树高 + 1(B 树唯一长高的方式:向上长高)。
📝 小题自测(点击展开看手算与破局)
题目:一棵 3 阶 B 树,插入关键字序列
[1, 2, 3, 4, 5],画出最终 B 树。手算步骤:
- 插入 1, 2:根节点
[1, 2]。- 插入 3:节点变成
[1, 2, 3],超过 3 阶上限(最多 2 个关键字),分裂。第⌈3/2⌉ = 2个元素(即2)上移,左右各一个 → 根[2],左[1],右[3]。- 插入 4:去右边的终端节点
[3, 4]。- 插入 5:右节点变成
[3, 4, 5],分裂。中间4上移,根变成[2, 4],左[1],中[3],右[5]。结果:根
[2, 4],叶子[1] [3] [5]。
6. B 树的删除(含借兄弟和合并)
一句话记忆
“非叶删转叶子删,不够先向兄弟借(父下移、兄上移),兄弟没得借就合并(连同父元素一起合)”。
删除的两种情况
情况 1:删除的关键字在非叶(非终端)节点
- 用直接前驱(左子树最右下元素)或直接后继(右子树最左下元素)替代该关键字。
- 然后转化为删除终端结点(叶结点)中的那个前驱或后继! 👉 重要推论:B 树的任何删除操作,最终都会转化为对最底层叶结点(终端结点)的删除,因此删除操作一定会导致叶结点发生变化!
情况 2:删除的关键字在叶结点(终端结点)
- 够删:若删除后,节点关键字数量
≥ ⌈m/2⌉ - 1,直接删除结束。- 不够删(下溢,
< ⌈m/2⌉ - 1):
- ① 兄弟够借(相邻左或右兄弟关键字数
≥ ⌈m/2⌉):父下移,兄上移(夹心饼干旋转)。
- 向右兄弟借:父节点分隔关键字下移到当前节点末尾;右兄弟的最小关键字上移到父节点。
- 向左兄弟借:父节点分隔关键字下移到当前节点开头;左兄弟的最大关键字上移到父节点。
- ② 兄弟不够借(左右兄弟关键字数均
= ⌈m/2⌉ - 1):合并。
- 将当前剩余关键字、父节点中的分隔关键字、以及相邻兄弟节点合并成一个新节点。
- 若导致父节点也下溢,继续向上传播;若根节点最后一个关键字被下移合并,则树高 - 1。
📝 3 阶 B 树删除实例(点击展开看手算与破局)
题目:一棵 3 阶 B 树,初始结构为:根
[4],左子[1, 2],右子[5, 6]。依次删除 2,再删除 1,画出最终 B 树。手算步骤: 第一步:删除 2
- 2 在叶节点
[1, 2]中,删后变成[1]。3 阶 B 树非根最少关键字数 =⌈3/2⌉ - 1 = 1,满足条件,直接结束。此时:根[4],左子[1],右子[5, 6]。第二步:删除 1
- 1 在叶节点
[1]中,删后变成[](0 个关键字 < 1),发生下溢。- 看右兄弟
[5, 6],有 2 个关键字 > 1,富余可借。- 向右兄弟借(父下移、兄最小上移):父节点
4下移到左子 → 左子变成[4];右兄弟最小的5上移到父节点 → 根变成[5],右子变成[6]。- 最终结构:根
[5],左子[4],右子[6]。
📋 B 树 / B+ 树 速查表(重点背诵)
| 对比项 | m 阶 B 树 | m 阶 B+ 树 |
|---|---|---|
| 数据位置 | 所有节点 | 只有叶子节点 |
| 叶子链表 | 无 | 有(支持顺序 + 随机查找) |
| 查找终点 | 找到即止 | 必须到叶子 |
| 节点关键字与子树 | n 个关键字,n+1 棵子树 | n 个关键字,n 棵子树 |
| 根节点关键字范围 | 1 ~ m-1 | 2 ~ 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
🧠 破局思路(题眼 + 步骤) 题眼:“非空 B 树”、“正确的”(注:本题中的“叶结点”即指最下层含关键字的终端结点)。 我的思路:
- I:插入可能导致节点一路向上分裂直到根节点分裂,增加树高。✅ 正确。
- II:删除操作如果发生在叶结点,叶结点直接变化;如果发生在非叶节点,必须用叶结点中的前驱/后继替代,然后转化为删除那个叶结点中的元素。所以叶结点一定变化。✅ 正确。
- III:B 树的查找在非叶节点命中时直接返回,不一定要查到叶结点(B+ 树才必须查到叶结点)。❌ 错误。
- IV:B 树的插入初始位置一定在叶结点,但如果发生分裂,新插入的关键字可能恰好是第
⌈m/2⌉个元素而被上移到父节点。所以最终不一定在叶结点中。❌ 错误。 结论:I、II 正确,选 B。
真题 2(B 树插入)
题目:在一棵 3 阶 B 树中,插入关键字 5 后,节点
[3, 4]变成[3, 4, 5],接下来应该( )。 A. 直接插入,结束 B. 分裂,中间元素上移 C. 删除一个元素 D. 必定增加树高🧠 破局思路(题眼 + 步骤)
- 3 阶 B 树每个节点最多
3 - 1 = 2个关键字。- 节点
[3, 4, 5]有 3 个关键字,发生溢出,需要将第⌈3/2⌉ = 2个元素(即4)上移分裂(只有导致根节点也分裂时才会增加树高,故 D 错)。 结论:选 B。
真题 3(B+ 树)
题目:下列关于 B+ 树的叙述中,错误的是( )。 A. B+ 树的所有数据都在叶子节点 B. B+ 树的叶子节点用链表相连 C. B+ 树的查找一定查到叶子节点 D. B+ 树的非叶节点也存数据记录
🧠 破局思路(题眼 + 步骤) 结论:选 D。
B+ 树非叶节点只存索引(子树最大关键字 + 指针),不存实际数据记录。
真题 4(B 树高度计算 · 经典必刷)
题目:一棵含 15 个关键字的 4 阶 B 树,含关键字的节点个数最多是多少?最大高度是多少?
🧠 破局思路(题眼 + 步骤)
- 求节点数最多:让每个节点里的关键字尽可能少!
- 4 阶 B 树,根节点最少 1 个关键字;非根节点最少
⌈4/2⌉ - 1 = 1个关键字!- 既然每个节点最少都可以只放 1 个关键字,那么 15 个关键字最多可以拆成 15 个节点!
- 求最大高度:直接套公式 。 结论:最多 15 个节点,最大高度 4。