一、换一个计算模型
第 1 讲的 RAM 模型假设"所有内存访问代价相同"。当数据在磁盘上时，这个假设错得离谱：
L1 缓存 ~1 ns
L2 缓存 ~4 ns
L3 缓存 ~40 ns
主存 ~100 ns
NVMe SSD ~100 μs = 主存的 1000 倍
机械硬盘寻道 ~10 ms = 主存的 100 000 倍
外存模型（External Memory Model / DAM 模型）
- 内存容量 M，磁盘无限大
- 数据以大小为 B 的块（block） 为单位在磁盘与内存间传输
- 代价 = 块传输次数（I/O 次数），CPU 计算免费
⭐ 在这个模型里，“读 1 个字节"和"读 B 个字节"代价相同——只要它们在同一块里。所以算法的目标从"少做计算"变成了**“少访问不同的块，且每次访问尽量用满整块”**。
红黑树在外存模型下有多糟
存 10⁹ 条记录的红黑树，树高约 2 log₂ 10⁹ ≈ 60 层。每个节点是独立的堆分配，查一次要 60 次随机 I/O。按 SSD 100 μs 算，一次查询 6 毫秒——完全不可接受。
问题的本质：二叉树每次比较只排除一半，每次 I/O 只获得 1 比特信息，而一个 4 KB 的块能装几百个键。我们浪费了 99.9% 的带宽。
解法很直接：把节点做成一整个块那么大。
二、B 树
B 树（度为 t，t ≥ 2）：
- 每个节点最多 2t−1 个键、2t 个孩子
- 除根外，每个节点至少 t−1 个键、t 个孩子（半满约束）
- 节点内的键有序排列
- 所有叶子在同一深度
[ 30 | 70 ]
╱ │ ╲
[10|20] [40|50|60] [80|90]
╱ │ ╲ ╱ │ │ ╲ ╱ │ ╲
… … … … … … … … … …
t = 2 的 B 树就是 2-3-4 树（第 17 讲）。B 树是它的推广。
高度分析
由半满约束，深度 i 的节点至少有 2t^{i−1} 个：
n ≥ 1 + (t−1)·Σ_{i=1}^{h} 2t^{i−1} = 2t^h − 1
⟹ h ≤ log_t((n+1)/2)
代入真实数字：4 KB 的块，键 + 指针约 16 字节 ⟹ 每节点约 250 个键，t ≈ 128：
| n | 二叉树高（≈2log₂n） | B 树高（log₂₅₀ n） |
|---|---|---|
| 10⁶ | 40 | 3 |
| 10⁹ | 60 | 4 |
| 10¹² | 80 | 5 |
⭐ 10 亿条记录，4 次磁盘 I/O。而且根节点（还常有第二层）必定在内存缓存中，实际磁盘 I/O 通常只有 1–2 次。
这就是 B 树统治数据库索引 50 年的全部理由：它把树高这个变量本身消灭了。
三、插入：先分裂后下降
关键设计：向下查找的路上，遇到满节点（2t−1 个键）就提前分裂。这样保证到达叶子时它一定不满，插入不会向上传播。
分裂满节点（t=3，5 个键）：
父 [ … ] 父 [ … | 30 | … ]
│ ╱ ╲
[10|20|30|40|50] ⟹ [10|20] [40|50]
中间键 30 升到父节点
const t = 128 // 度
type Node struct {
keys []int
children []*Node
leaf bool
}
// 分裂 x 的第 i 个孩子（该孩子必须是满的）
func (x *Node) splitChild(i int) {
y := x.children[i]
mid := y.keys[t-1] // 中间键，将升到 x
z := &Node{leaf: y.leaf}
z.keys = append(z.keys, y.keys[t:]...) // 后 t-1 个键给 z
if !y.leaf {
z.children = append(z.children, y.children[t:]...)
y.children = y.children[:t]
}
y.keys = y.keys[:t-1] // 前 t-1 个键留给 y
x.keys = slices.Insert(x.keys, i, mid)
x.children = slices.Insert(x.children, i+1, z)
}
func (tr *BTree) Insert(k int) {
r := tr.root
if len(r.keys) == 2*t-1 { // 根满了，树长高一层
s := &Node{leaf: false, children: []*Node{r}}
s.splitChild(0)
tr.root = s
s.insertNonFull(k)
return
}
r.insertNonFull(k)
}
func (x *Node) insertNonFull(k int) {
i, _ := slices.BinarySearch(x.keys, k)
if x.leaf {
x.keys = slices.Insert(x.keys, i, k)
return
}
if len(x.children[i].keys) == 2*t-1 { // 提前分裂
x.splitChild(i)
if k > x.keys[i] {
i++
}
}
x.children[i].insertNonFull(k)
}
⭐ “提前分裂"是一个非常聪明的设计：它把插入变成单趟向下（single pass），不需要回溯。对磁盘结构这至关重要——回溯意味着重新读已经写出去的块。
和 2-3-4 树一样，树长高的唯一方式是根分裂，所以所有叶子始终同深度。
删除：借用与合并
删除时若节点键数降到 t−1 以下（下溢），有两种修复：
① 向兄弟借（兄弟键数 > t−1）： ② 与兄弟合并（兄弟也只有 t−1 个）：
父 [ … | 50 | … ] 父 [ … | 50 | … ]
╱ ╲ ╱ ╲
[30] ← 下溢 [60|70|80] [30] ← 下溢 [60]
父 [ … | 60 | … ] 父 [ … ] ← 50 下沉
╱ ╲ │
[30|50] [70|80] [30|50|60]
同样采取提前处理策略：向下查找时若下一个要进入的孩子只有 t−1 个键，先补足再进入，从而保证删除也是单趟向下。
摊还结论：一次插入/删除引起的分裂或合并次数摊还是 O(1)（第 4 讲），虽然最坏可能一路到根。
四、B+ 树：数据库真正用的那个
B 树的两个不足：
- 数据存在内部节点，占用了本可以存更多键的空间 ⟹ 扇出变小 ⟹ 树变高
- 范围扫描要中序遍历，在树上跳来跳去，随机 I/O
B+ 树的两个改动：
[ 30 | 70 ] ← 内部节点只存键（路标），不存数据
╱ │ ╲
[10|20] [40|50|60] [80|90]
│ │ │
▼ ▼ ▼
┌──────────┐ ┌──────────┐ ┌──────────┐
│10 20 30 …│─▶│40 50 60 …│─▶│80 90 … │ ← 所有数据在叶子，
└──────────┘ └──────────┘ └──────────┘ 叶子用链表串起来
| 改动 | 收益 |
|---|---|
| 数据只存在叶子 | 内部节点纯索引，扇出更大（一块能放更多键），树更矮 |
| 叶子之间用链表相连 | 范围查询变成顺序 I/O：定位一次 + 顺序扫描 |
⭐ 第二点是 B+ 树相对 B 树的决定性优势。SELECT * FROM t WHERE id BETWEEN 1000 AND 2000 在 B+ 树上是"一次 O(log n) 定位 + 沿链表顺序读”，而顺序 I/O 比随机 I/O 快两个数量级。数据库的绝大多数查询是范围查询，所以这个优化几乎决定了一切。
使用者：MySQL InnoDB、PostgreSQL、Oracle、SQL Server、SQLite、几乎所有关系数据库；文件系统 NTFS、ext4、Btrfs、XFS。
聚簇索引与回表
InnoDB 的主键索引是聚簇索引：叶子节点直接存整行数据。二级索引的叶子只存主键值，因此按二级索引查询需要回表——先查二级索引拿主键，再查聚簇索引拿行。
⭐ 这解释了两个常见的数据库优化：
- 覆盖索引：如果查询要的列都在二级索引里，就不用回表。
- 主键应当短且单调递增：短 → 二级索引更小；单调递增 → 插入总在最右侧叶子，不引起页分裂。用随机 UUID 做主键会导致大量页分裂和碎片——这是一条非常实际的教训。
五、LSM 树：写密集场景的另一个答案
B+ 树的问题：每次写入都要更新树上的页，是随机写。SSD 的随机写有写放大问题，机械盘更是灾难。
LSM 树（Log-Structured Merge Tree） 反其道而行：
写入 ──▶ MemTable（内存中的跳表/红黑树）
│ 写满后冻结、顺序刷盘
▼
Level 0: [SSTable][SSTable][SSTable] ← 每个 SSTable 内部有序
│ 后台归并压实（compaction）
▼
Level 1: [────── SSTable ──────] ← 层内全局有序
│
Level 2: [──────────── … ────────────] ← 每层容量 ×10
| 维度 | B+ 树 | LSM 树 |
|---|---|---|
| 写 | 随机写，就地更新 | 顺序写，追加 |
| 读 | 1 次查找 | 可能查多个 SSTable（用布隆过滤器筛，见第 8 讲） |
| 写放大 | 中 | 高（compaction 反复重写） |
| 读放大 | 低 | 高 |
| 空间放大 | 中（页碎片） | 低（压缩率高） |
| 使用者 | MySQL、PostgreSQL | RocksDB、LevelDB、Cassandra、HBase、TiKV、ClickHouse |
⭐ 这是一个纯粹的取舍，没有对错：读多写少选 B+ 树，写多读少选 LSM 树。这也解释了为什么布隆过滤器在 LSM 系统里是标配——它是把"读放大"压下来的关键手段。
六、缓存无关（cache-oblivious）的思路
B 树需要知道块大小 B 来选择度 t。但现代系统有多级缓存（L1/L2/L3/内存/SSD），每级 B 都不同，没有一个 t 能同时最优。
缓存无关算法在不知道 B 和 M 的情况下，仍能达到最优的 I/O 复杂度。核心技巧是 van Emde Boas 布局：递归地把树按高度对半切，每半棵子树连续存放。
┌──────────────┐
│ 上半棵子树 │ 高度 h/2
└──────────────┘
╱ ╱ … ╲ ╲
┌────┐┌────┐ ┌────┐
│下半 ││下半 │… │下半 │ 各高度 h/2
└────┘└────┘ └────┘
内存布局：[上半整块][下半1][下半2]…[下半k] 递归地这样排
效果：无论 B 是多少，任意一条根到叶的路径都只跨越 O(log_B n) 个块——与知道 B 的 B 树同阶。
⚠️ 实践中缓存无关结构常数较大、实现复杂，主要用于研究和少数专门系统（如 TokuDB 的分形树）。但它的思想值得知道：递归的自相似布局可以同时适配所有层级的缓存。
七、选型总结
| 数据位置 | 主要负载 | 选择 |
|---|---|---|
| 内存，读多 | 点查 | 散列表 |
| 内存，需有序 | 点查 + 范围 | B 树（缓存友好）、跳表、红黑树 |
| 磁盘/SSD | 读多写少 | B+ 树 |
| 磁盘/SSD | 写多 | LSM 树 |
| 多级缓存、追求理论最优 | — | 缓存无关 B 树 |
⭐ 注意第二行：即使全部数据在内存里，B 树往往也优于红黑树。因为内存也有块结构——缓存行是 64 字节，页是 4 KB。取 t 使一个节点恰好占几条缓存行的 B 树（有时叫 cache-conscious B-tree），在内存中通常比红黑树快 2–3 倍。这就是为什么 Go 生态里流行的有序 map 实现（google/btree、tidwall/btree）都是 B 树而不是红黑树。
随堂自测
- 外存模型与 RAM 模型的关键差别是什么？为什么在它下面"读 1 字节"和"读 B 字节"代价相同？
- 存 10⁹ 条记录，红黑树和 B 树（t=128）各需要几次磁盘 I/O？请算出来。
- B 树的半满约束（至少 t−1 个键）保证了什么？没有它会怎样？
- 推导 B 树高度上界
h ≤ log_t((n+1)/2)。 - 为什么 B 树插入采用"向下时提前分裂满节点"而不是"插完再向上修复”？
- B+ 树相对 B 树的两个改动分别解决了什么问题？哪一个对数据库更关键？
- 为什么用随机 UUID 做 InnoDB 主键是个坏主意？换成自增 ID 好在哪？
- 什么是回表？覆盖索引为什么能避免它？
- LSM 树用什么换什么？为什么它必须配布隆过滤器？
- 数据全在内存中，为什么 B 树可能仍然优于红黑树？