Appearance
B 树与 B+ 树
概念
B 树（B-Tree，注意不是"二叉"的 B）是一种多路平衡查找树，专为磁盘等外存设计。一棵 m 阶 B 树满足：
- 每个结点最多 m 个子树，即最多 m − 1 个关键字；
- 非根非叶结点至少
- 根结点若非叶子，至少 2 个子树（至少 1 个关键字）；
- 所有叶结点都在同一层（它们是不含信息的"失败结点"，代表查找失败的位置）；
- 结点内的关键字递增有序，第 i 个关键字把第 i 与第 i+1 棵子树的值域分隔开。
一句话理解：二叉搜索树让树变矮的办法是"二叉"，B 树让树变矮的办法是"多叉"——一个结点塞满几十上百个关键字，一次磁盘 I/O 就能读入几十个关键字，于是几百万条记录也只要三四层。
结点逻辑结构：
┌────┬────┬───────┬────┬───────┬────┐
│ n │ P0 │ K1 │ P1 │ K2 │ P2 │
└────┴────┴───────┴────┴───────┴────┘
│ │
(指针 Pi 所指子树中所有关键字介于 Ki 与 K(i+1) 之间)原理
关键字个数的约束（记牢这两条）
对 m 阶 B 树，设
| 结点类型 | 最少孩子数 | 最少关键字数 | 最多孩子数 | 最多关键字数 |
|---|---|---|---|---|
| 根（非叶） | 2 | 1 | m | m − 1 |
| 非根（内结点/叶） | m | m − 1 |
树高范围
设树高
（1）含 n 个关键字时，h 的上界（尽量"挤满"）：
- 第 i 层最少有
解得
（2）h 的下界（尽可能"塞满"）：
每层最多
解得
m = 5、n = 2000 的实例见后面示例。
插入：只在溢出时分裂
插入 key：
先查找到最底层的某个叶上层结点（终端结点），把 key 有序插入
while 该结点关键字数 > m-1: /* 溢出，必须分裂 */
mid = ⌈len/2⌉ 位置的关键字
把它上移到父结点中间位置
左右剩余关键字拆成两个兄弟结点，各自保留原有子指针
若父结点也随之溢出 → 继续向上处理
若分裂传到根并使根溢出 → 新建根，树高 +1 /* B 树唯一的长高方式 */关键理解：B 树是"向上生长"的——它只会通过根的分裂长高，且每次长高时所有叶子同步下移一层，因此天然保持平衡。
删除：下溢时借或并
删除 key：
若 key 在非终端结点：用它左子树的最大值（前驱）或右子树的最小值（后继）替代，
问题转化为删除某个终端结点的关键字
删除后若该结点关键字数 < d-1（下溢）：
a. 兄弟结点关键字数 > d-1（够借）：从兄弟借，经由父结点"旋转"下来
b. 兄弟也不够借：把本结点、兄弟、以及夹在中间的父结点关键字合并成一个结点
若父结点因此下溢 → 继续向上传播，必要时缩减树高B+ 树与 B 树的区别
| m 阶 B 树 | m 阶 B+ 树 | |
|---|---|---|
| 关键字分布 | 全树每个关键字只出现一次 | 非叶结点的关键字都重复出现在叶子里 |
| 叶子内容 | 叶子是失败结点，不含信息 | 叶子含全部关键字 + 记录指针，叶间有序链表相连 |
| 非叶结点 | 既是索引也带关键字 | 纯索引，关键字 = 子树中的最大值（复本） |
| 孩子数与关键字数 | 孩子数 = 关键字数 + 1 | 孩子数 = 关键字数 |
| 查找终止 | 命中即可返回，路径长度不定 | 必须走到叶子，路径长度恒定 |
| 顺序/范围查找 | 要中序遍历整棵树 | 沿叶子链表直接扫 |
| 典型用途 | 早期文件系统 | 数据库索引、现代文件系统（MySQL InnoDB 索引即 B+ 树） |
为什么数据库偏爱 B+ 树？一是非叶结点不存记录指针，同样大小的磁盘块能塞更多索引项，树更矮；二是叶子链表让范围扫描（BETWEEN、ORDER BY）变成顺序读。
示例
例 1：3 阶 B 树的插入全过程
3 阶 B 树 → 每结点最多 2 个关键字（3 个孩子），非根结点最少 1 个关键字（2 个孩子）。依次插入：20, 50, 30, 60, 70, 52, 68, 90
| 步 | 插入 | 是否溢出 | 结果（方括号为一个结点，缩进表示层次） |
|---|---|---|---|
| 1 | 20 | 否 | [20] |
| 2 | 50 | 否 | [20 50] |
| 3 | 30 | 是（3 个 > 2） | [30]├ [20]└ [50] |
| 4 | 60 | 否 | [30]├ [20]└ [50 60] |
| 5 | 70 | 是（[50 60 70]） | [30 60]├ [20]├ [50]└ [70] |
| 6 | 52 | 否 | [30 60]├ [20]├ [50 52]└ [70] |
| 7 | 68 | 否 | [30 60]├ [20]├ [50 52]└ [68 70] |
| 8 | 90 | 是（双重：叶子 → 根） | 见下 |
第 8 步拆开看：
插入 90：落到 [68 70] → [68 70 90]，3 个关键字 > 2，溢出
取中间关键字 70 上移到父结点
├─ 左：[68]
└─ 右：[90]
父结点原为 [30 60]，加入 70 → [30 60 70]，仍是 3 个，溢出
取中间关键字 60 上移 → 新建根 [60]
├─ 左：[30] （孩子 [20] 与 [50 52]）
└─ 右：[70] （孩子 [68] 与 [90]）
最终树（高 3）：
┌────────────[60]────────────┐
│ │
[30] [70]
┌─────┴─────┐ ┌─────┴─────┐
[20] [50 52] [68] [90]
└ 叶子 └ 叶子 └ 叶子 └ 叶子注意第 8 步：叶子溢出 → 父溢出 → 根分裂产生新根，树高从 2 变 3。这是 B 树长高的唯一途径。
例 2：删除演示（借不到 → 连续合并 → 树变矮）
从例 1 的最终树出发，先删 52：52 在终端结点 [50 52]，删后剩 [50]，关键字数 1 ≥
┌────────────[60]────────────┐
[30] [70]
┌─────┴─────┐ ┌─────┴─────┐
[20] [50] [68] [90]再删 50：删后该结点变空（0 < 1）→ 下溢。
第 1 步：左兄弟 [20] 只有 1 个关键字（= d-1，借不了），右兄弟 [68] 同样只有 1 个
⟹ 只能合并：[20] + 父结点关键字 30 + 空结点 → [20 30]
父结点 [30] 因此失去关键字与一个孩子 → 变空且只剩 1 个孩子 → 父也下溢
第 2 步：[30]（已空，带 1 个孩子 [20 30]）的兄弟是 [70]，只有 1 个关键字，仍借不了
⟹ 再次合并：[20 30] + 父结点关键字 60 + [70](带 [68][90]) → [60 70]
根结点随之被撤销，树高从 3 降为 2最终结果（8 个关键字删去 52、50 后剩 6 个）：
┌──────────[60 70]──────────┐
│ │ │
[20 30] [68] [90]
└ 叶 └ 叶 └ 叶
校验：关键字 = 20,30,60,68,70,90 共 6 个 ✓
根 2 个关键字 3 个孩子 ✓；叶子同层且每个 1~2 个关键字 ✓ —— 是一棵合法的 3 阶 B 树做题要点：先尝试向兄弟借；兄弟处在最小值（
）就借不了，只能合并。本例连续两次合并一路传到根，最终根被撤销——这是 B 树变矮的唯一途径，与"根分裂变高"正好对称。
例 3：m = 5、n = 2000 的树高范围
5 阶 B 树：
下界（尽可能塞满，
上界（尽可能稀疏，
结论：含 2000 个关键字的 5 阶 B 树，树高在 5 ~ 7 层之间。校验：h = 7 时最少关键字数
各层关键字数上下界速查（m = 5）：
| 树高 h | 最少关键字数 | 最多关键字数 |
|---|---|---|
| 1 | 1 | 4 |
| 2 | 5 | 24 |
| 3 | 17 | 124 |
| 4 | 53 | 624 |
| 5 | 161 | 3124 |
C 语言：B 树查找
#include <stdio.h>
#define M 5 /* 5 阶 B 树 */
#define MAXK (M - 1) /* 每个结点最多 4 个关键字 */
typedef struct BTNode {
int keynum; /* 实际关键字个数 */
int key[MAXK + 1]; /* 关键字，key[1] 起用 */
struct BTNode *child[M + 1]; /* 子树指针 */
int isLeaf;
} BTNode, *BTree;
/* 在结点 t 中查找 key：返回 key 所在结点指针，*pos 为下标；找不到时 *pos 为应落入的分支 */
BTNode *search(BTree t, int key, int *pos) {
BTNode *p = t, *q = NULL;
while (p) {
int i = 1;
while (i <= p->keynum && key > p->key[i]) i++;
if (i <= p->keynum && key == p->key[i]) { *pos = i; return p; } /* 命中 */
q = p;
p = p->isLeaf ? NULL : p->child[i - 1]; /* 沿分支下降 */
}
*pos = 0;
return q; /* 返回最后访问到的结点（可供插入使用） */
}
/* 构造一棵演示用的树：[30 60] 根，孩子 [20]、[50 52]、[70]（3 阶示例简化为静态结构） */
static BTNode make(int keys[], int n, int leaf) {
BTNode x; x.keynum = n; x.isLeaf = leaf;
for (int i = 0; i <= M; i++) x.child[i] = NULL;
for (int i = 1; i <= n; i++) x.key[i] = keys[i - 1];
return x;
}
int main(void) {
int k0[2] = {30, 60}, k1[1] = {20}, k2[2] = {50, 52}, k3[2] = {68, 70};
BTNode leaf0 = make(k1, 1, 1), leaf1 = make(k2, 2, 1), leaf2 = make(k3, 2, 1);
BTNode root = make(k0, 2, 0);
root.child[0] = &leaf0; root.child[1] = &leaf1; root.child[2] = &leaf2;
int pos, *p;
BTNode *r = search(&root, 52, &pos);
printf("search(52): 命中结点首关键字 = %d, pos = %d\n", r->key[1], pos); /* 50, 2 */
r = search(&root, 99, &pos);
printf("search(99): 落到结点首关键字 = %d, pos = %d\n", r->key[1], pos); /* 68, 0 */
r = search(&root, 30, &pos);
printf("search(30): 命中根结点, pos = %d\n", pos); /* 1 */
(void)p;
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
Python 对照：完整插入（含分裂）
class Node:
def __init__(self, leaf=True):
self.keys = []; self.child = []; self.leaf = leaf
class BTree:
def __init__(self, m):
self.m = m # 阶：最多 m 个孩子
self.maxk = m - 1 # 最多关键字数
self.minchild = (m + 1) // 2 # ceil(m/2)
self.root = Node()
def find_child(self, x, k):
i = 0
while i < len(x.keys) and k > x.keys[i]: i += 1
return i
def insert(self, k):
path, x = [], self.root
while not x.leaf:
path.append(x); x = x.child[self.find_child(x, k)]
x.keys.insert(self.find_child(x, k), k)
while len(x.keys) > self.maxk: # 溢出 → 分裂
mid = len(x.keys) // 2
up, right = x.keys[mid], Node(x.leaf)
right.keys = x.keys[mid + 1:]; x.keys = x.keys[:mid]
if not x.leaf:
right.child = x.child[mid + 1:]; x.child = x.child[:mid + 1]
if not path: # 根分裂 → 树高 +1
nr = Node(False); nr.keys = [up]; nr.child = [x, right]
self.root = nr; break
p = path.pop()
j = self.find_child(p, up)
p.keys.insert(j, up); p.child.insert(j + 1, right)
x = p
def dump(self, node=None, level=0):
node = node or self.root
print(" " + " " * level + "L%d: %s" % (level, node.keys))
if not node.leaf:
for c in node.child: self.dump(c, level + 1)
bt = BTree(3) # 3 阶：最多 2 个关键字
for k in [20, 50, 30, 60, 70, 52, 68, 90]:
bt.insert(k); print("insert %d ->" % k); bt.dump()
# 最终：L0 [60] / L1 [30],[70] / L2 [20],[50,52],[68],[90]
# ---- 树高范围 ----
import math
def key_count_range(m, h):
d = (m + 1) // 2
mn, nodes = 1, 2
for _ in range(2, h + 1):
mn += nodes * (d - 1); nodes *= d
return mn, m ** h - 1
m, n = 5, 2000
print("\nm=5 n=2000 树高范围: [%d, %d]" % (
math.ceil(math.log(n + 1, m)),
math.floor(1 + math.log((n + 1) / 2, (m + 1) // 2))))
for h in range(1, 9):
lo, hi = key_count_range(m, h)
print(" h=%d 关键字数 [%d, %d]%s" % (h, lo, hi,
" ← 装得下 2000" if lo <= n <= hi else ""))
# h=5..7 三个档位都装得下，结论一致
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
考点
考点
1. 必背结论
- m 阶 B 树：每结点最多 m 个孩子 / m − 1 个关键字；非根结点至少
- 所有叶结点在同一层；叶子是失败结点（不含信息）。
- 含有 n 个关键字的 m 阶 B 树，树高满足
- 插入：关键字数达到 m 才溢出分裂；根分裂是树长高的唯一途径（会长高也是保持平衡的原因）。
- 删除：非终端结点用前驱/后继顶替；下溢时"能借则借（经父旋转），不能借则合并"，并向上传播。
- B+ 树：关键字数 = 孩子数；非叶纯索引；叶子含全部关键字且链表相连；查找必到叶子（路径恒定）。
2. 解题套路
- 求树高范围：记住"结点尽可能稀疏（最少关键字数）→ 推出 h 的上界"、"结点尽可能塞满（最多关键字数）→ 推出 h 的下界"，别用反。
- 手算插入：每次只做一件事——插入 → 若溢出就取出中间关键字上移、左右各半，然后检查父结点。
- 手算删除：先判"有没有下溢"，没有就结束；有就看兄弟够不够借（够借走旋转，不够借走合并）。
- 判断树是否合法：逐结点检查"孩子数 = 关键字数 + 1"、每个非根结点的关键字数 ≥
3. 易错点
- 混淆"最多关键字数 m − 1"与"最多孩子数 m"。判断溢出要看关键字数是否达到 m（即比上限 m − 1 多一个）。
- 记错
- 把 B 树的高度定义搞混：本题约定
- 认为 B 树的查找一定走到叶子。不是：命中非终端结点的关键字即可返回；只有 B+ 树才必须走到叶子。
- 认为 B+ 树里关键字只出现一次。错：内部结点的关键字都是叶子里最大值的复本，整棵树关键字总数多于实际记录数。
- 忽略"叶子链表"这个关键点：它能回答"B+ 树为什么适合范围查询"。
- 删除时只记得"合并"忘了"借"的顺序。正确顺序：先借，借不到才合并。
小结
- B 树是多路平衡查找树，靠"一个结点塞很多关键字"压缩树高，服务于磁盘 I/O；外科树高范围由最少/最多关键字数夹出来。
- 插入靠分裂、删除靠借或并，树只在根分裂时变高，因此天然平衡。
- B+ 树把关键字全部下推到叶子并在叶子间拉链表：查询路径恒定、适合范围扫描、同样的盘块能装更多索引项是它取代 B 树成为数据库索引标配的原因。
- 下一步：查找的最后一站——散列表，它跳过比较，直接由关键字算出存储地址。
下一篇：散列表：构造、冲突处理、性能分析
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。