B+树 (B+ Tree) 深度解析

B+树本质上是一种多路平衡查找树（N-ary Balanced Search Tree），它是为了在磁盘（或其他直接存取辅助设备）上存储和检索大量数据而专门设计的。

1. 核心数据结构定义

一个 $m$ 阶（Order）的 B+树满足以下严格性质：

节点结构：
- 根节点：至少有两个子节点（除非树只有一层）。
- 内部节点（Internal Nodes）：存储 Key 和 Pointer。不存储数据。
  - 如果一个内部节点有 $k$ 个子节点，它包含 $k-1$ 个 Key。
  - 关键点：内部节点的 Key 仅仅是路由路标（Router），用于指示搜索方向。
- 叶子节点（Leaf Nodes）：存储所有的 Key 和对应的 Value（或数据指针）。
  - 树中所有的 Key 最终都会出现在叶子节点中。
  - 叶子节点之间通过双向链表（Next/Prev 指针）连接，形成一个有序链表。
填充因子（Fill Factor）：
- 为了保持树的平衡，节点（除根节点外）必须至少半满。
- 内部节点至少有 $\lceil m/2 \rceil$ 个子节点。
- 叶子节点至少包含 $\lceil m/2 \rceil$ 个记录。
高度平衡：所有叶子节点都在同一层级（Depth 相同）。

2. 为什么 B+ 树比 B 树更适合数据库？

很多人知道 B+ 树好，但不知道具体好在这个数理推导上。

假设我们需要存储 $N$ 条记录，磁盘页（Page Size）大小为 $P$ 。

Key 大小： $k$ 字节
指针大小： $p$ 字节
数据记录大小： $v$ 字节

差异点 1：出度（Fan-out）与树高

B-树（B-Tree）：
- 内部节点既存 Key 也存 Value。
- 一个节点能存的元素数量 $M_{B} \approx P / (k + v + p)$ 。
- 因为 $v$ （数据）通常很大（比如一行数据 1KB），导致 $M_{B}$ 很小。树会变得很高。
B+树：
- 内部节点只存 Key 和指针。
- 一个节点能存的元素数量 $M_{B+} \approx P / (k + p)$ 。
- 因为没有 $v$ ，且 $k+p$ 通常很小（比如 ID 8字节 + 指针 6字节 = 14字节）， $M_{B+}$ 极大（通常 > 1000）。

结论：在同样的 Page Size 下，B+ 树的**扇出（Fan-out）**远大于 B- 树。

\text{Height} = \log_{\text{Fan-out}}(N)

扇出越大，底数越大，树的高度 $H$ 就越低。

实例：千万级数据，B- 树可能需要 4-5 层（4-5 次 I/O），而 B+ 树通常只需要 3 层（3 次 I/O）。I/O 性能呈指数级差异。

差异点 2：CPU 缓存友好性（Cache Locality）

B+ 树的内部节点紧凑，一个内存页（Page）可以加载大量的 Key。在进行节点内二分查找时，缓存命中率极高。

3. 核心算法操作细节

A. 查找 (Search)

点查询：从根开始，根据 Key 大小比较，选择子节点指针，直到叶子节点。在叶子节点内部进行二分查找。
- 复杂度： $O(\log_m N)$
范围查询：
1. 先做一次点查询找到 Start Key 所在的叶子节点。
2. 利用叶子节点的 Next 指针直接遍历链表，直到遇到 End Key。
3. 优势：这是 B+ 树的杀手锏，复杂度接近 $O(N)$ 的线性扫描，且完全是顺序 I/O（Sequential I/O），磁盘吞吐量极大。

B. 插入 (Insertion) - “分裂（Split）”机制

当插入一个新的 Key-Value 到叶子节点：

若叶子节点未满：直接插入并排序。
若叶子节点已满：
- 分裂：将叶子节点一分为二。
- 提升（Copy Up）：将中间的 Key 复制一份，放入父节点（内部节点）作为索引。
- 注意：如果是内部节点满而分裂，是将中间 Key 上移（Push Up），而不是复制（因为内部节点不存数据，Key 也是唯一的路标）。
递归：如果父节点也满了，继续分裂，直到根节点。如果根节点分裂，树的高度 $+1$ 。

C. 删除 (Deletion) - “合并（Merge）/ 借位（Rotate）”机制

当删除一个 Key：

若节点利用率 >= 50%：直接删除。
若节点利用率 < 50%（Underflow）：
- 借位（Rotate）：看兄弟节点是否富余？如果富余，把兄弟的一个 Key 挪过来，并更新父节点的索引。
- 合并（Merge）：如果兄弟也穷，则将两个节点合并。合并后，父节点会少一个子节点（少一个 Key）。
递归：如果父节点因为子节点合并而 Underflow，继续向上合并。如果根节点没有任何 Key 了，树的高度 $-1$ 。

4. 真实世界中的 B+ 树：MySQL InnoDB 实现

理论结合工程，MySQL 的 InnoDB 引擎对 B+ 树做了一些微调：

1. 聚簇索引 (Clustered Index)

InnoDB 的主键索引就是 B+ 树本身。
叶子节点 = 整行数据。
也就是说，SELECT * FROM table WHERE id = 1 找到叶子节点时，数据已经拿到手了，不需要回表。

2. 辅助索引 (Secondary Index)

如果我们给 name 字段建索引。
叶子节点 = name 的值 + 主键 ID。
查找流程：先在辅助索引树中找到 name 对应的主键 ID，然后再去主键索引树（聚簇索引）中查具体数据。这叫回表（Index Lookup）。

3. 页填充率 (Page Fill Factor)

InnoDB 默认不会把页填满到 100%，而是保留约 1/16 的空间用于未来的 UPDATE 或 INSERT，以减少频繁的分裂操作。

导航