O(log n) 查找结构：深度分析与场景决策
#数据结构 · #二叉树 · #AVL · #红黑树 · #B树 · #跳表 · #LSM树
当数据需要动态插入、删除且要求有序查找/遍历时，O(log n) 的平衡树是核心武器。本文逐一深入：红黑树、AVL、跳表、B/B+ 树、LSM 树，并从单读、读写混合、并发读写等维度做场景决策矩阵。
1. BST 退化问题
1.1 退化的本质
顺序插入 1,2,3,4,5:
1
\
2
\
3
\
4
\
5
查找 5 → 需要 5 次比较 = O(n)！根本原因：BST 不保证任何平衡性。树的形状完全取决于插入顺序。随机插入 →
解决方案：强制平衡。
2. AVL 树 — 严格平衡
2.1 平衡条件
每个节点的平衡因子 BF = height(left) - height(right) ∈ {-1, 0, 1}。
定理：高度为 h 的 AVL 树至少有
2.2 四种失衡情形与旋转（完整版）
LL 型: 左子树的左子树插入导致失衡 → 右旋
─────────────────────────────────────
z (BF=2) y (BF=0)
/ 右旋(z) / \
y (BF=1) ───────→ x z
/
x
代码: right_rotate(z) // y 成为新 root, z 成为 y 的右儿子
RR 型: 右子树的右子树插入导致失衡 → 左旋
─────────────────────────────────────
z (BF=-2) y (BF=0)
\ 左旋(z) / \
y (BF=-1) ───────→ z x
\
x
代码: left_rotate(z)
LR 型: 左子树的右子树插入导致失衡 → 先左旋后右旋
─────────────────────────────────────
z (BF=2) z (BF=2) x (BF=0)
/ 左旋(y) / 右旋(z) / \
y (BF=-1) ───────→ x (BF=?) ──────→ y z
\ /
x y
代码: left_rotate(y); right_rotate(z)
RL 型: 右子树的左子树插入导致失衡 → 先右旋后左旋
─────────────────────────────────────
z (BF=-2) z (BF=-2) x (BF=0)
\ 右旋(y) \ 左旋(z) / \
y (BF=1) ─────→ x (BF=?) ────→ z y
/ \
x y
代码: right_rotate(y); left_rotate(z)2.3 旋转前后的 BF 更新
LR 型旋转后 BF 更新（关键！）:
设旋转前 x 的 BF 为 old_bf_x:
old_bf_x == 0: y.bf=0, z.bf=0, x.bf=0
old_bf_x == 1: y.bf=0, z.bf=-1, x.bf=0
old_bf_x == -1: y.bf=1, z.bf=0, x.bf=0这是 AVL 实现中最容易出 bug 的地方。
2.4 删除的复杂度
AVL 删除后可能需要 O(log n) 次旋转——从删除位置一直回溯到根，每一层都可能失衡。
删除叶子节点 → 父节点 BF 可能变化 → 祖父也可能失衡 → ... → 根
每次回溯最多 1 次旋转（但旋转后子树高度可能-1，导致上层继续失衡）这就是 AVL 在写密集场景下不如红黑树的根本原因。
2.5 AVL 的适用场景
| 场景 | 是否适合 | 原因 |
|---|---|---|
| 读多写少 | ✅ 最佳 | 树最矮 → 查找最快 |
| 读写均衡 | ⚠️ 一般 | 删除代价高 |
| 写多读少 | ❌ | O(log n) 次旋转不可接受 |
| 内存受限 | ⚠️ | 需要存储 BF（2 bit，可用指针低位偷） |
3. 红黑树 — 实用主义王者
3.1 五条性质的直观理解
- 节点是红色或黑色
- 根节点是黑色
- 叶子（NIL）是黑色
- 红色节点的子节点必须是黑色（无连续红色）
- 从任意节点到叶子的每条路径上黑色节点数相同（黑高相等）
推论：最长路径（红黑交替）≤ 2 × 最短路径（全黑）→
严格性排序: AVL > 红黑树 > 无约束 BST
树高排序: AVL < 红黑树 < BST (退化为链表)3.2 插入修复：6 种 Case（完整版）
插入节点设为红色（不影响黑高），然后修复可能违反的性质 4。
插入节点为 z，父节点为 z.p，祖父为 z.p.p，叔叔为 y
═══════════════════════════════════════════
父节点是左儿子的情况:
═══════════════════════════════════════════
Case 1: 叔叔 y 是红色
───────────────────────
B(z.p.p) R(z.p.p)
/ \ 变色 / \
R R(y) ───────→ B B
/ /
R(z) R(z)
操作: z.p.color=BLACK, y.color=BLACK, z.p.p.color=RED, z=z.p.p(上行)
→ 可能引发新问题，while 循环继续
Case 2: 叔叔 y 是黑色，z 是右儿子 (LR)
─────────────────────────────────────
B(z.p.p) B(z.p.p)
/ \ 左旋(z.p) / \
R B(y) ───────→ R B(y)
\ /
R(z) R(z.p)
操作: z = z.p; left_rotate(z)
→ 转为 Case 3
Case 3: 叔叔 y 是黑色，z 是左儿子 (LL)
─────────────────────────────────────
B(z.p.p) R(z.p) B(z.p)
/ \ 右旋(z.p.p) / \ 变色 / \
R B(y) ──────────→ R B ────→ R R(z.p.p)
/ / \
R(z) R(z) B(y)
操作: z.p.color=BLACK, z.p.p.color=RED, right_rotate(z.p.p)
→ 修复完成，while 循环结束
═══════════════════════════════════════════
父节点是右儿子的情况 (对称):
═══════════════════════════════════════════
Case 4: 叔叔 y 是红色 → 变色上行 (对称于 Case 1)
Case 5: 叔叔 y 是黑色，z 是左儿子 (RL) → 右旋转 Case 6
Case 6: 叔叔 y 是黑色，z 是右儿子 (RR) → 左旋 + 变色3.3 删除修复：最复杂的部分
删除后的关键: 被删除或被移动的节点如果是黑色 → "少了一个黑节点"
→ 把它缺失的黑色"借"给替代它的节点 → 变成"双黑"节点
→ 在树上传播双黑，直到遇到红色节点或到达根
双黑 = 该节点多承担了一个黑色（颜色还是黑的，但计数时是双层）
完整 case 列表 (双黑节点为 x):
────────────────────────────────────────
x 是左儿子:
Case A: 兄弟 w 是红色 → 左旋父 + 变色 → w 变成黑色 (转为 B/C/D)
Case B: 兄弟 w 黑色，w 的两个儿子都黑 → w 变红，x 上移到父节点
Case C: 兄弟 w 黑色，w 的左儿子红，右儿子黑 → w 左儿子黑，w 红，右旋 w (转为 D)
Case D: 兄弟 w 黑色，w 的右儿子红 → w 颜色=父颜色，父黑，w 右儿子黑，左旋父
x 是右儿子: 对称处理复杂度：插入最多 2 次旋转；删除最多 3 次旋转（Case D 1 次）。与 AVL 的删除 O(log n) 次旋转形成鲜明对比。
3.4 红黑树 vs AVL：实验数据
来自实际 benchmark（插入/删除/查找 100 万随机整数）：
| 操作 | AVL | 红黑树 | 差值 |
|---|---|---|---|
| 插入 | 1.0× | 0.85× | RB 快 15% |
| 删除 | 1.0× | 0.65× | RB 快 35% |
| 查找 | 0.90× | 1.0× | AVL 快 10% |
| 混合(50%查/30%插/20%删) | 1.0× | 0.80× | RB 快 20% |
结论：除非场景是极端读多写少（>90% 读），否则红黑树更优。
3.5 红黑树的范围查找——为什么不如跳表和 B+ 树？
红黑树做范围查询（如"找所有 key ∈ [100, 200]"）需要中序遍历，效率分析如下：
红黑树范围查找的步骤:
1. 定位起点: O(log n) — 从根向下找到第一个 ≥ 100 的节点
2. 中序遍历: 从起点开始，逐个访问后继节点
中序遍历的"后继查找"代价:
给定节点 x，找中序后继:
Case A: x 有右子树 → 后继 = 右子树的最左节点
代价: O(1) ~ O(log n)，平均 O(1)
Case B: x 没有右子树 → 后继 = 向上回溯到"第一个左转的祖先"
代价: O(1) ~ O(log n)，平均 O(1)
单次后继查找的均摊代价 = O(1)
（因为 n 个节点的中序遍历总共只经过 n-1 条边，每条边最多走 2 次）
所以范围查询 k 个元素: O(log n + k) — 理论上和跳表/B+树相同
但实际性能差在哪？
问题 1: 指针跳转不连续
红黑树节点分散在堆上 → 中序遍历时每访问一个后继都是一次指针跳转
→ cache miss 频繁
对比跳表: Level 0 是连续链表 → 顺序遍历 → prefetch 有效
对比 B+ 树: 叶子节点是连续页 + 双向链表 → 顺序扫描
问题 2: 回溯操作的 cache 代价
Case B 的"向上回溯"需要访问 parent 指针
→ parent 节点可能早已不在 cache 中
→ 每次回溯都可能触发 L2/L3 cache miss
问题 3: 无法利用 SIMD/预取
红黑树的遍历方向不可预测（左→右→上→右→左...）
→ CPU 预取器无法学习访问模式
→ 预取命中率极低
实测对比 (范围查询 1000 个元素, n=100万):
红黑树中序遍历: ~25μs (大量 cache miss)
跳表 Level 0 遍历: ~15μs (链表顺序访问)
B+ 树叶子链表扫描: ~8μs (连续页 + 预取)
红黑树比 B+ 树慢 3× → 这就是为什么数据库索引不用红黑树红黑树的平均查找速度——为什么比 AVL 慢 10%？
AVL 树高: h_AVL ≤ 1.44 × log₂(n)
红黑树高: h_RB ≤ 2 × log₂(n+1)
n = 100万时:
AVL 最大高度: 1.44 × 20 = 28.8 → 最多 29 次比较
红黑树最大高度: 2 × 20 = 40 → 最多 40 次比较
实际平均高度（随机插入）:
AVL: ~1.01 × log₂(n) ≈ 20.2
红黑树: ~1.02 × log₂(n) ≈ 20.4
差距很小！但 AVL 的树更"紧凑" → 更多节点在浅层
→ 平均查找路径短 ~5-10%
这 10% 的差距在大多数场景下被红黑树更快的插入/删除抵消3.5 各系统中的红黑树
| 系统 | 使用位置 | 关键场景 | 为何选红黑树 |
|---|---|---|---|
| Linux 内核 | CFS 调度器、epoll、VMA | 频繁插入/删除 | 删除 O(1) 旋转 |
| C++ STL | std::map, std::set | 通用有序容器 | 平衡读写 |
| Java | TreeMap, TreeSet | 通用有序容器 | 同上 |
| Nginx | 定时器管理 | 大量超时事件增删 | 删除快 |
| libevent | 定时器 | 同上 | 同上 |
为什么 C++/Java 的有序 map 选红黑树而非 AVL 或跳表？
std::map / TreeMap 选择红黑树的工程决策分析:
1. 为什么不选 AVL 树？
std::map 的典型使用模式: 插入 → 查找 → 删除 → 插入 → ...
即读写混合，而非纯读。
AVL 删除: 可能需要 O(log n) 次旋转（从删除点到根的路径上每个节点都可能失衡）
红黑树删除: 最多 3 次旋转 + O(log n) 次变色
对于 map 的迭代器稳定性:
AVL 的多次旋转可能改变更多节点的位置 → 迭代器失效风险更高
红黑树的旋转次数少 → 对迭代器更友好
结论: 在读写混合场景下，红黑树的删除优势 (35%) 大于 AVL 的查找优势 (10%)
2. 为什么不选跳表？
- 跳表是概率平衡 → 最坏情况 O(n)（虽然概率极低）
→ 标准库不能接受"概率性"的性能保证
- 跳表的空间开销不确定（取决于随机数）
→ 标准库需要确定性的空间行为
- 跳表不支持高效的 reverse iterator
→ std::map 需要双向迭代器
- 跳表的 lower_bound/upper_bound 实现不如红黑树自然
3. 为什么不选 B 树？
- B 树节点内有多个 key → 插入/删除时需要移动节点内的元素
- std::map 保证: 插入/删除不会使其他迭代器失效
→ B 树的节点内移动会破坏这个保证
- B 树更适合磁盘 I/O（减少页访问），内存中优势不明显
4. Linux 内核为什么也选红黑树？
CFS 调度器: 频繁插入（新进程）和删除（进程结束/阻塞）
epoll: 大量 fd 的增删
VMA: 内存区域的频繁合并和分裂
这些场景都是"写多读少" → 红黑树的删除优势是决定性的
且内核代码不能有"概率性"行为 → 排除跳表c
// Linux 内核 rbtree — 侵入式设计
struct rb_node {
unsigned long __rb_parent_color; // 低 bit 存颜色, 高位存父指针
struct rb_node *rb_right;
struct rb_node *rb_left;
};
// 节省内存: 父指针 + 颜色共用一个 unsigned long
#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
#define rb_color(r) ((r)->__rb_parent_color & 1)4. 跳表 — 概率平衡
4.1 概率分析 — 为什么 p 的选择是核心设计决策
Level 0: 所有 n 个节点 (概率 1)
Level 1: ~n·p 个节点
Level 2: ~n·p² 个节点
...
Level k: ~n·p^k 个节点
期望总指针数 = n × (1 + p + p² + p³ + ...) = n / (1-p)
期望层数 ≈ log_{1/p}(n)
期望查找时间 ≈ (log_{1/p}(n)) / p + 1/(1-p)p=1/2 vs p=1/4 vs p=1/e 深度对比：
| 指标 | p=1/2 | p=1/4 (Redis) | p=1/e |
|---|---|---|---|
| 每节点期望指针数 | 2.00 | 1.33 | ~1.58 |
| 空间开销 | +100% | +33% | +58% |
| 期望层数 | log₂(n) | log₄(n) = 0.5·log₂(n) | ~log₂(n)/1.44 |
| 期望查找比较次数 | ~2·log₂(n) | ~4·log₄(n) = 2·log₂(n) | ~2·log₂(n) |
| 插入时指针更新数 | ~2 | ~1.33 | ~1.58 |
| 查找最快 | ❌ | ✅（常数最小） | ❌ |
| 空间最优 | ❌ | ✅ | ❌ |
为什么 Redis 选 p=1/4？
mermaid
flowchart LR
subgraph P05["p=0.5, n=1M"]
A1["L0: 1000000"] --- A2["L1: 500000"] --- A3["L2: 250000"]
A3 --- A4["L3: 125000"] --- A5["L4: 62500"] --- A6["..."]
end
subgraph P025["p=0.25, n=1M (Redis)"]
B1["L0: 1000000"] --- B2["L1: 250000"] --- B3["L2: 62500"]
B3 --- B4["L3: 15625"] --- B5["L4: 3906"] --- B6["..."]
end
P05 -.- N1["总指针: ~2M<br/>期望跳数: ~1.44×"]
P025 -.- N2["总指针: ~1.33M<br/>期望跳数: ~1.0×"]
style B2 fill:#4CAF50,color:#fff
style N2 fill:#4CAF50,color:#fff关键：p=0.25 时每节点平均只有 1.33 个指针（空间接近链表），但查找仍然是 O(log n)，且在内存带宽敏感的 Redis 单线程场景下常数最优。少 33% 的指针意味着更好的缓存局部性。
p=0.25 vs p=0.5 的完整内存和查找效率深度分析：
═══════════════════════════════════════════════════════════════
内存分析: 每节点的指针数量推导
═══════════════════════════════════════════════════════════════
节点在第 k 层的概率 = p^(k-1) × (1-p) (几何分布)
节点的期望层数 = 1/(1-p)
节点的期望指针数 = 期望层数 = 1/(1-p)
p=0.5: 期望指针数 = 1/(1-0.5) = 2.0 个/节点
p=0.25: 期望指针数 = 1/(1-0.25) = 1.33 个/节点
p=1/e: 期望指针数 = 1/(1-1/e) ≈ 1.58 个/节点
实际内存占用 (n=100万个 int64 key, 64位系统):
每个指针 = 8B
p=0.5:
总指针数 = n × 2.0 = 200万个
指针内存 = 200万 × 8B = 16MB
数据内存 = 100万 × 8B = 8MB
总内存 = 24MB → 额外开销 = 16MB (200%)
p=0.25:
总指针数 = n × 1.33 = 133万个
指针内存 = 133万 × 8B = 10.64MB
数据内存 = 100万 × 8B = 8MB
总内存 = 18.64MB → 额外开销 = 10.64MB (133%)
节省: 16MB - 10.64MB = 5.36MB (节省 33.5%)
对于 Redis 这种内存数据库，33% 的内存节省非常显著！
═══════════════════════════════════════════════════════════════
查找效率分析: 期望比较次数的精确推导
═══════════════════════════════════════════════════════════════
查找路径分析:
从最高层开始，每层要么"向右走"要么"向下走"
在某一层"向右走"的期望步数:
每个节点出现在当前层的概率 = p
→ 在当前层连续向右走的期望步数 = 1/p - 1
(几何分布: 期望走 1/p 步才遇到一个"不在上层"的节点)
总层数 = log_{1/p}(n)
期望比较次数 = 层数 × 每层期望步数
= log_{1/p}(n) × (1/p)
= log_{1/p}(n) / p
更精确的公式 (Pugh 1990):
E[比较次数] = (1/p) × log_{1/p}(n) + 1/(1-p)
代入具体值 (n=100万):
p=0.5: (1/0.5) × log₂(10⁶) + 1/0.5 = 2 × 20 + 2 = 42 次
p=0.25: (1/0.25) × log₄(10⁶) + 1/0.75 = 4 × 10 + 1.33 = 41.33 次
p=1/e: e × log_e(10⁶) + e/(e-1) = 2.718 × 13.8 + 1.58 = 39.1 次
结论: 三者的查找比较次数几乎相同！(39~42 次)
但 p=0.25 的内存只有 p=0.5 的 67%
═══════════════════════════════════════════════════════════════
为什么 p=0.25 在 Redis 中是最优选择？
═══════════════════════════════════════════════════════════════
1. 内存效率: 比 p=0.5 省 33% 内存 → Redis 是内存数据库，每字节都珍贵
2. 查找速度: 比较次数几乎相同 (41 vs 42)
3. Cache 友好: 更少的指针 → 节点更小 → 更多节点能装入 cache line
4. 位运算友好: 0.25 = 1/4 → 判断 random() < 0.25 可以用 (random() & 3) == 0
而 1/e ≈ 0.368 需要浮点运算
5. 插入开销: 每次插入平均只需更新 1.33 个指针 (vs p=0.5 的 2 个)
唯一的"代价": 最大层数稍高
p=0.5: 期望最大层 = log₂(n) = 20
p=0.25: 期望最大层 = log₄(n) = 10 (实际更低！)
→ p=0.25 的层数反而更少 → 向下走的次数更少c
// Redis 的随机层数生成
int zslRandomLevel(void) {
int level = 1;
while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
// p=0.25 时的层数分布 (n=1M):
// Level 1: 100.00% (1000000 节点)
// Level 2: 25.00% ( 250000 节点)
// Level 3: 6.25% ( 62500 节点)
// Level 4: 1.56% ( 15600 节点)
// Level 5: 0.39% ( 3900 节点)
// ...
// Level 21: <1个 → ZSKIPLIST_MAXLEVEL=32 足够 n=2^644.2 跳表 vs 红黑树/AVL — 工程视角
| 维度 | 跳表 | 红黑树 | AVL |
|---|---|---|---|
| 实现复杂度 | 简单（~200 行） | 复杂（~500+ 行） | 复杂（~400 行） |
| 范围查询 | O(log n + k) 极好 | O(log n + k) 需中序遍历 | 同红黑树 |
| 并发友好 | 天然支持 lock-free | 旋转涉及多节点，锁粗 | 同红黑树 |
| 内存（每节点） | ~1.33 指针 (p=0.25) | 3 指针（父+左+右）+ 1B color | 3指针 + 1B balance |
| 平衡保证 | 概率（期望 O(log n)） | 确定（最坏 O(log n)） | 确定（严格平衡） |
| 最坏查找 | O(n)（极低概率，p^(-maxLevel)） | O(log n) | O(log n) |
| 插入旋转 | 无旋转（只改指针） | 最多 2 次旋转 | 最多 O(log n) 次旋转 |
4.2.1 跳表的随机性退化问题——最坏情况有多坏？如何防御？
跳表的平衡性依赖随机数生成器。如果运气极差，可能出现:
- 所有节点都只有 1 层 → 退化为链表 → O(n)
- 某个节点层数极高 → 浪费空间但不影响正确性
最坏情况的概率分析:
设 n 个节点，p=0.25，所有节点都只有 1 层的概率:
P(全部 1 层) = (1-p)^n = 0.75^n
n=100: P ≈ 3.2 × 10^{-13} → 几乎不可能
n=10: P ≈ 0.056 → 有 5.6% 的概率！
所以小数据量时跳表的性能方差较大，大数据量时概率保证非常强。
查找效率退化的量化分析:
期望查找比较次数 = (1/p) × log_{1/p}(n) + 1/(1-p)
p=0.25 时:
期望 = 4 × log₄(n) + 4/3
n=100万: 期望 ≈ 4 × 10 + 1.33 ≈ 41.33 次比较
标准差分析（查找路径长度的方差）:
Var(查找路径) ≈ n^{2p-1} / (1-p)² (当 p < 0.5 时方差很小)
p=0.25: 方差 ≈ O(1/n^{0.5}) → 随 n 增大，方差趋近 0
→ 大数据量时，跳表的查找性能非常稳定
p=0.5 时:
方差更大 → 性能波动更明显
这也是 Redis 选 p=0.25 而非 p=0.5 的原因之一
防御退化的工程手段:
1. MAXLEVEL 限制:
Redis: ZSKIPLIST_MAXLEVEL = 32
→ 即使随机数连续"中奖"，层数也不会超过 32
→ 32 层足够索引 4^32 ≈ 1.8 × 10^19 个元素
2. 确定性跳表（Deterministic Skip List）:
不用随机数，而是根据节点数量确定层数
→ 保证最坏 O(log n)
→ 但失去了实现简单的优势，工程中很少用
3. 1/e 最优概率:
理论上 p = 1/e ≈ 0.368 使得"期望查找时间 × 空间"的乘积最小
但 p=0.25 更实用（空间更省，且 0.25 可以用位运算判断）
4. Redis 的实际保证:
n=100万, p=0.25:
期望最大层数 = log₄(n) ≈ 10
P(某节点层数 > 20) = 0.25^20 ≈ 10^{-12}
→ 实际中跳表的层数几乎不会超过 12-15 层4.3 场景负载决策矩阵
空间利用率 = 有效数据 / 总内存· 查找效率 = 期望比较次数· 关键问题：在什么负载下选什么结构？
mermaid
flowchart TD
Q1["你的工作负载是什么？"] --> Q2{"读占主导<br/>(>90% 读)？"}
Q2 -->|"是"| Q3{"数据量巨大<br/>且内存敏感？"}
Q3 -->|"是"| AVL_M["AVL 树<br/>空间最优(3指针)<br/>查找最快 ▼10%"]
Q3 -->|"否"| RBT_M["红黑树<br/>查找较快"]
Q2 -->|"否"| Q4{"写占主导<br/>(>50% 写/删)？"}
Q4 -->|"是, 内存中"| SKIP["跳表 p=0.25<br/>无旋转, 插入/删除最快<br/>Lock-free 并发写"]
Q4 -->|"是, 磁盘中"| LSM["LSM 树<br/>顺序写, 后台 compaction"]
Q4 -->|"否, 读写均衡"| Q5{"需要高并发？"}
Q5 -->|"是"| SKIP2["跳表<br/>CAS Lock-free<br/>ConcurrentSkipListMap"]
Q5 -->|"否, 单线程"| RBT_M2["红黑树<br/>平衡读写, 确定性"]
style AVL_M fill:#2196F3,color:#fff
style SKIP fill:#4CAF50,color:#fff
style LSM fill:#FF9800,color:#fff
style RBT_M2 fill:#9C27B0,color:#fff| 工作负载 | 推荐结构 | 空间效率 | 查找效率 | 插入效率 | 删除效率 | 典型系统 |
|---|---|---|---|---|---|---|
| 纯读 / 极少写 | AVL | ★★★ 3指针 | ★★★★★ | ★★ | ★★ | 字典/静态索引 |
| 读多写少 (90/10) | 红黑树 | ★★ 3指针 | ★★★★ | ★★★ | ★★★ | CFS调度器, std::map |
| 读写均衡 | 跳表 p=0.25 | ★★★★ 1.33指针 | ★★★★ | ★★★★★ | ★★★★★ | Redis ZSet |
| 写多读少 | LSM 树 | ★★★ (compaction) | ★★ (读放大) | ★★★★★ | N/A | RocksDB |
| 高并发读写 | 跳表 lock-free | ★★★ 1.33指针 | ★★★★ | ★★★★★ | ★★★★★ | Java ConcurrentSkipListMap |
| 内存极度紧张 | 跳表 p=0.25 | ★★★★★ 仅33%额外 | ★★★★ | ★★★★★ | ★★★★★ | 嵌入式/高频交易 |
4.3 为何 LSM 树的 MemTable 用跳表？
LevelDB / RocksDB 的 MemTable 选择跳表的关键原因：
- 并发写友好：跳表的插入只影响局部节点，可以细粒度加锁
- 范围查询：LSM 的
Iterator.Seek()需要找第一个 ≥ key 的元素 → 跳表天然高效 - 实现简单：嵌入式场景（LevelDB 代码库小），跳表的实现胜出
- 无旋转：没有复杂的树结构调整，不会在 flush 期间造成延迟尖刺
5. B 树 — 为磁盘而生
5.1 磁盘 IO 的性能现实
操作 | 延迟 | 类比 (放在 1 秒视角)
L1 Cache | 0.5 ns | 1 秒
L2 Cache | 7 ns | 14 秒
主内存 | 100 ns | 3 分钟
NVMe SSD | 100 μs | 3 天
SATA SSD | 500 μs | 15 天
HDD 随机读 | 10 ms | 10 个月B 树的哲学：一次磁盘 IO 读一个节点 → 节点越大，每次 IO 检查的 key 越多。
5.2 节点大小计算
设页大小 = 16KB (MySQL InnoDB 默认)
每个 key-value 对 = 8 + 8 = 16 字节
每个子节点指针 = 8 字节
每个节点最多容纳的 key 数: 16KB / (16+8) ≈ 680
树高 3 层: 680³ = 314,432,000 → 3.1 亿条记录只需 3 次 IO！5.3 B 树的插入与分裂
插入 key=50 到一个满的节点 [10|20|30]:
1. 找到插入位置（在 30 后面）
2. 节点已满（度 t=3，最多 2t-1=5 个 key，此处简化）
3. 分裂节点:
[10|20] 提升 20 → [20] [30|50] (新节点)
/ \
[10] [30|50]B 树的高度增加只发生在根节点分裂 → 所有叶子深度同时 +1 → 完美平衡。
5.4 B 树 vs 二叉平衡树（内存场景）
| B 树 (t=2) | 红黑树 | 跳表 | |
|---|---|---|---|
| 节点内搜索 | 线性扫描 (3 key) | 1 次比较 | 1 次比较 |
| 缓存行利用 | 较差（节点跨多行） | 好 | 好 |
| 插入分裂 | 复杂 | 旋转 | 插入指针 |
| 内存碎片 | 严重（节点大小固定） | 无 | 无 |
结论：在纯内存场景下 B 树不如二叉平衡树。B 树只在磁盘场景有压倒性优势。
6. B+ 树 — 数据库索引事实标准
6.1 与 B 树的关键区别
B 树: B+ 树:
内部节点存数据 + key 内部节点只存 key (扇出更大)
叶子节点独立，无链接 叶子节点用双向链表连接
范围查询需中序遍历 范围查询顺序扫描叶子链表 → O(log n + k)为什么 B+ 树更优？
- 内部节点扇出更大 → 树更矮 → 更少 IO
- 范围查询碾压 B 树 →
SELECT * FROM t WHERE id BETWEEN 100 AND 200只需 1 次 seek + 顺序读 - 全表扫描高效 → 遍历叶子链表
6.2 MySQL InnoDB 的聚簇索引
主键索引 (聚簇索引):
B+ 树叶子节点 = 完整行数据
[内部节点: key + child_ptr]
|
[叶子: key1 | col1,col2,col3] → [key2 | col1,col2,col3] → ...
二级索引:
B+ 树叶子节点 = 主键值 + 索引列
查找: 二级索引找到主键 → 回表到聚簇索引查完整行
EXPLAIN Extra: "Using index" → 覆盖索引，无需回表6.3 B+ 树的分裂与合并——InnoDB 索引的核心操作
页分裂（Page Split）——插入时节点满了怎么办？
InnoDB 的 B+ 树每个节点 = 一个 16KB 的页。
当一个叶子页满了（无法再插入新记录）时，触发页分裂。
═══════════════════════════════════════════════════════════════
场景 1: 顺序插入（自增主键）— 最优情况
═══════════════════════════════════════════════════════════════
插入 key=1,2,3,...,100 到一个最多容纳 4 条记录的叶子页:
步骤 1: 页 A 装满 [1,2,3,4]
步骤 2: 插入 key=5 → 页 A 满了 → 分裂
分裂策略（顺序插入优化）:
InnoDB 检测到是"右侧插入"模式 → 不对半分！
而是: 保留原页不动，新记录直接放入新页
结果:
页 A: [1,2,3,4] (不动)
页 B: [5] (新页，后续 6,7,8... 继续填入)
父节点: [... | 5 → 页B]
优势: 页 A 利用率 100%，无数据搬迁 ✅
═══════════════════════════════════════════════════════════════
场景 2: 随机插入（UUID 主键）— 最差情况
═══════════════════════════════════════════════════════════════
页 A 已满: [10, 30, 50, 70]
插入 key=40 → 应该在 30 和 50 之间 → 页 A 满了 → 分裂
分裂策略（随机插入）:
对半分裂: 将页 A 的记录分成两半
步骤:
1. 分配新页 B
2. 将页 A 后半部分 [50, 70] 移动到页 B
3. 在页 A 中插入 40
4. 更新父节点: 添加指向页 B 的指针，分隔键 = 50
5. 更新叶子页的双向链表指针
结果:
页 A: [10, 30, 40] (利用率 75%)
页 B: [50, 70] (利用率 50%)
父节点: [... | 50 → 页B]
代价:
- 1 次页分配 (新页 B)
- 数据搬迁 (50% 的记录从 A 移到 B)
- 父节点更新 (可能触发父节点也分裂 → 级联分裂)
- 页利用率下降 (从 100% → 平均 62.5%)
- 产生磁盘碎片 (新页可能不连续)
═══════════════════════════════════════════════════════════════
场景 3: 内部节点分裂（级联分裂）
═══════════════════════════════════════════════════════════════
当叶子页分裂后，父节点需要添加新的分隔键。
如果父节点也满了 → 父节点也分裂 → 可能一直传播到根节点。
根节点分裂:
旧根: [20, 40, 60, 80] (满了)
分裂:
新根: [40]
左子: [20]
右子: [60, 80]
→ 树高 +1（这是 B+ 树高度增加的唯一方式）
→ 所有叶子深度同时 +1 → 完美平衡 ✅
级联分裂的概率:
设每个节点最多 m 个 key，随机插入时:
叶子分裂概率 ≈ 1/m (每 m 次插入触发一次)
父节点分裂概率 ≈ 1/m² (每 m² 次插入)
祖父节点分裂概率 ≈ 1/m³
...
InnoDB m ≈ 1170 → 级联分裂到第 2 层的概率 ≈ 1/1,368,900
→ 几乎不会发生页合并（Page Merge）——删除后页太空怎么办？
当一个页的利用率低于阈值（InnoDB 默认 50%，由 MERGE_THRESHOLD 控制）时，
InnoDB 尝试将该页与相邻页合并。
═══════════════════════════════════════════════════════════════
合并过程:
═══════════════════════════════════════════════════════════════
页 A: [10, 30] (利用率 50%，低于阈值)
页 B: [50, 70] (利用率 50%)
检查: 页 A + 页 B 的记录能否放入一个页？
[10, 30, 50, 70] → 4 条记录 ≤ 页容量 → 可以合并 ✅
合并步骤:
1. 将页 B 的所有记录移动到页 A
2. 更新叶子链表: 页 A 的 next 指向页 B 的 next
3. 从父节点删除指向页 B 的分隔键
4. 释放页 B（标记为空闲页，加入 Free List）
5. 如果父节点因删除而低于阈值 → 可能触发父节点合并
结果:
页 A: [10, 30, 50, 70] (利用率 100%)
页 B: 已释放
═══════════════════════════════════════════════════════════════
为什么 InnoDB 不立即合并？
═══════════════════════════════════════════════════════════════
合并的代价:
- 需要加锁两个页 + 父节点
- 数据搬迁 + 链表更新
- 可能触发级联合并
所以 InnoDB 的策略是"延迟合并":
- 删除记录时只标记为"已删除"（不立即物理删除）
- 后台 purge 线程定期清理
- 只有当页利用率真的低于 MERGE_THRESHOLD 时才合并
- 这也是为什么 DELETE 后表空间不会立即缩小
═══════════════════════════════════════════════════════════════
分裂 vs 合并的性能影响
═══════════════════════════════════════════════════════════════
| 操作 | 代价 | 频率 | 对性能的影响 |
|------|------|------|-------------|
| 叶子分裂 | 1次页分配+数据搬迁 | 每 ~m 次插入 | 插入 RT 偶尔抖动 |
| 级联分裂 | 多次页分配 | 极罕见 | 可忽略 |
| 页合并 | 数据搬迁+链表更新 | 大量删除后 | 后台执行，影响小 |
| 碎片累积 | 空间浪费 | 长期运行 | OPTIMIZE TABLE 整理 |
UUID 主键的灾难:
随机插入 → 每次都可能触发页分裂
页利用率平均只有 ~50-70%（对比自增主键的 ~90%+）
空间浪费 30-50% + 大量随机 I/O
→ 这就是为什么 InnoDB 强烈建议用自增整数主键主键设计原则：
- 用自增整数而非 UUID：UUID 随机性导致大量页分裂 + 碎片
- 自增主键 → 所有插入在"最右"叶子 → 顺序写 → 最优
6.4 各数据库索引选择
| 数据库 | 默认索引 | 特点 |
|---|---|---|
| MySQL InnoDB | B+ 树 | 聚簇索引 + 二级索引回表 |
| PostgreSQL | B+ 树 (Lehman-Yao 并发) | 非聚簇，所有索引是二级索引 |
| MongoDB WiredTiger | B+ 树 | 类似 InnoDB |
| SQLite | B 树 (变体 B*-tree) | 轻量，文件即数据库 |
| Elasticsearch | LSM (Lucene) | 写优化，用 Segment 合并 |
| RocksDB | LSM | 写优化，Leveled Compaction |
7. LSM 树 — 写优化的对数结构
7.1 为什么需要 LSM？
B+ 树的写放大严重：
一次 INSERT:
1. 查找插入位置 (O(log_B n) IO)
2. 如果节点已满 → 分裂 (更多 IO)
3. 更新可能触发页的随机写
对于 HDD: 每次随机写 ~10ms → 100 次/秒 → 太慢了LSM 的核心思想：把随机写变成顺序写。
7.2 LSM 的结构
写入路径:
Write → MemTable (内存, 跳表/红黑树) → WAL (磁盘顺序写)
↓ (MemTable 满了)
Immutable MemTable
↓ (后台 flush)
SSTable Level 0 (磁盘)
↓ (后台 compaction)
SSTable Level 1
↓ (后台 compaction)
SSTable Level 2 ...
读取路径:
Read → MemTable → Immutable MemTable → Level 0 (所有文件) → Level 1 → ...
↑ 布隆过滤器加速每个 SSTable 的检查写放大 vs 读放大 vs 空间放大 — LSM 的三体问题：
| 策略 | 写放大 | 读放大 | 空间放大 |
|---|---|---|---|
| Leveled (RocksDB 默认) | 高 (10-30×) | 低 (每层最多查 1 个文件) | 低 (~10%) |
| Tiered (Cassandra) | 低 (2-5×) | 高 (需查多个文件) | 高 (50-100%) |
| Tiered+Leveled (DynamoDB) | 中 | 中 | 中 |
7.3 LSM vs B+ 树：场景选择
| 场景 | 推荐 | 原因 |
|---|---|---|
| 大量写入 (日志、时序、IoT) | LSM | 顺序写 = 100× 快于随机写 |
| 大量点查 + 偶尔写 | B+ 树 | 1 次 IO 找到数据 |
| 大量范围查询 | B+ 树 | 叶子链表 → 顺序扫描 |
| 既要写又要读 | B+ 树 | LSM 后台 compaction 干扰前台读 |
| SSD 存储 | LSM | SSD 顺序写优势大 |
| HDD 存储 | B+ 树 | LSM 的 compaction 在 HDD 上不可接受 |
7.4 LSM 的 Compaction 策略
| 策略 | 算法 | 使用者 |
|---|---|---|
| Leveled | N 层，每层大小固定 (×10) | RocksDB 默认, LevelDB |
| Tiered/Size-tiered | 等大小的 SSTable 合并 | Cassandra |
| Universal | 大小相近的合并，写放大最低 | RocksDB 可选 |
| FIFO | 只删除最老文件，无合并 | 纯时序数据 (TTL) |
8. 场景决策矩阵
8.1 按读写比例选择
工作负载:
┌──────────────────────────────────────────────────┐
│ 100% 读 (无写) │
│ → 排序数组 + 二分查找 (最简单, 最优) │
│ → 或 AVL (如果必须动态) │
├──────────────────────────────────────────────────┤
│ 90% 读 / 10% 写 │
│ → AVL 树 (树最矮, 查找最快) │
├──────────────────────────────────────────────────┤
│ 50% 读 / 50% 写 │
│ → 红黑树 (插入/删除只需 O(1) 旋转) │
│ → 跳表 (如果需要并发) │
├──────────────────────────────────────────────────┤
│ 10% 读 / 90% 写 │
│ → LSM 树 (写的吞吐最高) │
│ → 如果必须内存 → 红黑树 │
└──────────────────────────────────────────────────┘8.2 多维度对比
| 维度 | AVL | 红黑树 | 跳表 | B 树 | B+ 树 | LSM 树 |
|---|---|---|---|---|---|---|
| 查找 | ★★★★★ | ★★★★☆ | ★★★★☆ | ★★★☆☆ | ★★★★☆ | ★★☆☆☆ |
| 插入 | ★★★☆☆ | ★★★★☆ | ★★★★☆ | ★★☆☆☆ | ★★☆☆☆ | ★★★★★ |
| 删除 | ★★☆☆☆ | ★★★★★ | ★★★★☆ | ★★☆☆☆ | ★★☆☆☆ | ★★★★★ |
| 范围查询 | ★★★★☆ | ★★★☆☆ | ★★★★★ | ★★★☆☆ | ★★★★★ | ★★☆☆☆ |
| 内存占用 | ★★★★☆ | ★★★★☆ | ★★★☆☆ | ★★☆☆☆ | ★★★☆☆ | ★★★★★ |
| 实现难度 | ★★★★☆ | ★★☆☆☆ | ★★★★★ | ★★☆☆☆ | ★★☆☆☆ | ★★☆☆☆ |
| 并发友好 | ★☆☆☆☆ | ★★☆☆☆ | ★★★★★ | ★☆☆☆☆ | ★★★★☆ | ★★★★☆ |
| 磁盘适应 | ★☆☆☆☆ | ★☆☆☆☆ | ★☆☆☆☆ | ★★★★☆ | ★★★★★ | ★★★★★ |
9. 并发场景深度分析
9.1 并发读（Read-Only / Read-Mostly）
所有 O(log n) 结构在纯读场景下都可以做到无锁 — 读操作不修改树结构。
方案: RCU (Read-Copy-Update) 或 不可变数据结构
- 读线程永远看到一致的树
- 写线程创建新版本 → 原子替换根指针
- 旧版本等待所有读线程退出后回收Linux 内核大量使用 RCU 保护读操作，红黑树的查找完全无锁。
9.2 并发写（需要锁）
红黑树的并发写 — 困难
旋转操作涉及 5-6 个节点 → 需要锁住这些节点的父路径 → 锁粒度粗。
c
// 红黑树并发写的两难:
// 选项 A: 全局锁 → 简单但吞吐低
// 选项 B: 细粒度锁 → 死锁风险极高（向上回溯的旋转）
// 实践中大多数系统用全局锁或读写锁保护整棵树跳表的并发写 — 天然优势
跳表的插入只修改局部节点的 forward 指针 → 可以用 CAS 实现 lock-free。
c
// Lock-free 跳表插入 (简化)
do {
// 1. 无锁查找插入位置，记录每层的前驱节点
update = find_predecessors(key);
// 2. 创建新节点
newNode = create_node(key, random_level());
// 3. CAS 插入:
// 从 Level 0 向上，每层用 CAS 设置 forward 指针
newNode->forward[i] = update[i]->forward[i];
} while (!CAS(&update[i]->forward[i], newNode->forward[i], newNode));这就是为什么 ConcurrentSkipListMap (Java) 是并发有序容器的首选。
9.3 B+ 树的并发 — Lehman-Yao 算法
PostgreSQL 使用的 B-link 树（Lehman & Yao, 1981）：
关键技巧: 每个内部节点有指向右兄弟的指针 (high key pointer)
查找时:
- 只持有当前节点的读锁
- 如果 key > node.max_key → 跟随右兄弟指针 → 不回溯！
插入时的锁策略:
- 从根向下，只在当前操作的节点上加锁
- 到了子节点立即释放父节点的锁 (lock coupling / crab walking)
- 分裂时先插入 → 再分裂 → 更新父节点
保证: 任何时刻树结构一致，无死锁9.4 并发场景总结
| 场景 | 推荐结构 | 并发方案 | 实际系统 |
|---|---|---|---|
| 纯读 (无写) | AVL / 红黑树 | RCU 无锁读 | Linux 内核 VMA |
| 读多写少 | 跳表 / 红黑树 | 读写锁 | epoll |
| 读写均衡 | 跳表 | Lock-free CAS | ConcurrentSkipListMap |
| 写多读少 | LSM 树 | 无锁写 + 后台 compaction | RocksDB |
| 高并发磁盘 | B+ 树 (B-link) | 锁耦合 + 右兄弟指针 | PostgreSQL |
| 纯内存高并发 | 跳表 | Lock-free | Redis (单线程无需) |
10. 选择指南
需要什么？
┌─ 有序遍历 / 范围查询 ─────────────────────────────┐
│ │
├─ 数据在内存 ───────────────────────────────────┐ │
│ ├─ 需要高并发写入 → 跳表 (Lock-free) │ │
│ ├─ 读多写少 (>90%读) → AVL 树 │ │
│ ├─ 读写均衡 → 红黑树 │ │
│ └─ 实现简单优先 → 跳表 │ │
│ │
├─ 数据在磁盘 ───────────────────────────────────┐ │
│ ├─ 写多读少 → LSM 树 (RocksDB) │ │
│ ├─ 读多写少 → B+ 树 (MySQL InnoDB) │ │
│ ├─ 范围查询多 → B+ 树 │ │
│ └─ 嵌入式/单文件 → B 树 (SQLite) │ │
│ │
└────────────────────────────────────────────────────┘
只需要精确查找？→ Hash 表 (O(1))
只需要前缀匹配？→ Trie
需要概率去重？→ Bloom Filtermermaid
flowchart TD
subgraph RBT["红黑树插入修复 (6 Case)"]
direction TB
INS["插入红色节点 z"] --> PAREN{"z.p 是 黑色?"}
PAREN -->|"是"| DONE["✅ 完成, 不违反任何性质"]
PAREN -->|"否 (z.p 是红色)"| SIDE{"z.p 是 左儿子?"}
SIDE -->|"是"| CASE123["Case1: 叔叔红→变色上行<br/>Case2: LR→左旋转Case3<br/>Case3: LL→右旋+变色"]
SIDE -->|"否"| CASE456["Case4: 叔叔红→变色上行<br/>Case5: RL→右旋转Case6<br/>Case6: RR→左旋+变色"]
CASE123 --> FIX["最多 2 次旋转"]
CASE456 --> FIX
end
subgraph LSM["LSM 树 Compaction"]
direction LR
WRITE["写入 MemTable"] --> FLUSH["MemTable -> L0 SST"]
FLUSH --> COMPACT["L0 -> L1 Compaction"]
COMPACT --> DEEPER["L1 -> L2 -> ... -> Ln"]
end
style DONE fill:#4CAF50,color:#fff
style FIX fill:#2196F3,color:#fff
style WRITE fill:#FF9800,color:#fff
style COMPACT fill:#9C27B0,color:#fff11. 从复杂度到工程实现：为什么真实系统不会只看 O(log n)
11.1 同样是 O(log n)，真实速度可能差很多
树结构的复杂度看起来相近，但真实系统里影响性能的，往往不只是比较次数，还有：
- 节点是否连续存储
- 指针跳转多不多
- cache miss / TLB miss 多不多
- 插入删除时是否需要旋转、分裂、compaction
- 并发时锁能不能做细
所以线上性能经常不是“红黑树 vs AVL 谁复杂度更优”，而是：谁更符合当前硬件和负载模型。
11.2 内存中的树为什么常输给数组/堆/哈希表
大多数树节点都长这样：
text
key + value + left ptr + right ptr + parent ptr + color/balance问题在于：
- 节点通常分散在堆上
- 遍历时会不断指针跳转
- CPU 预取效果差
- 缓存局部性明显弱于连续数组
这也是为什么：
- 只做精确查找时，哈希表经常更快
- 做优先级选择时，堆常比平衡树更合适
- 数据稳定时，排序数组 + 二分查找常有很强竞争力
11.3 为什么数据库偏爱 B+ 树，内存系统更常用红黑树/跳表
mermaid
flowchart LR
A["数据主要在内存"] --> B["关注 cache、指针跳转、并发写"]
B --> C["红黑树 / 跳表 更常见"]
D["数据主要在磁盘或页缓存"] --> E["关注扇出、IO 次数、范围扫描"]
E --> F["B+树 更常见"]核心差异不是“谁更高级”，而是优化目标不同：
- 内存结构：更怕 cache miss、锁竞争、旋转复杂度
- 磁盘结构：更怕 I/O 次数、页分裂、范围查询成本
11.4 各系统为什么做出不同改良
| 系统/语言 | 结构 | 背后原因 |
|---|---|---|
| Linux CFS | 红黑树 | 删除/插入频繁，需要稳定 O(log n) |
Java ConcurrentSkipListMap | 跳表 | 并发写更友好，容易做无锁/CAS |
| Redis ZSet | 跳表 + 哈希 | 既要按 score 有序，又要按 member 快查 |
| MySQL InnoDB | B+ 树 | 磁盘页友好、范围查询强 |
| RocksDB MemTable | 跳表 | 写入简单，flush/iterator 方便 |
也就是说，结构的改良往往不是为了教科书上的最优，而是为了：
- 更适合缓存局部性
- 更适合并发控制
- 更适合磁盘页
- 更适合工程实现复杂度
11.5 实战中的典型故障
| 现象 | 可能根因 |
|---|---|
| 范围查询很慢 | 结构不适合顺序扫描 |
| 写入 RT 抖动 | 旋转/分裂/compaction 代价大 |
| 内存占用高 | 节点元数据和指针过多 |
| 多核扩展差 | 全局锁或树结构调整过重 |
| 数据量变大后性能断崖 | 工作集超出缓存/内存层级 |
11.6 一个判断原则
text
先看数据主要在内存还是磁盘；
再看读写比例、范围查询、并发写强度；
最后再看理论复杂度。如果只记住 O(log n)，很容易选错结构；如果把局部性、并发、I/O 模式、实现复杂度一起放进来，决策会靠谱很多。
B+Tree 为什么是数据库索引的标准
一个节点 = 一个磁盘页
B+Tree 不是因为它"多路"所以快，而是因为它的节点大小设计成和磁盘页对齐：
text
MySQL InnoDB 默认页大小 = 16KB
B+Tree 节点 = 16KB:
每个索引项 = key(8B) + 子节点指针(6B) = 14B
一个节点存 ~1170 个索引项
3 层 B+Tree 能索引多少行?
Root (1 node): 1170 个指针 → 指向 1170 个内部节点
Level 2: 1170 个节点, 每个 1170 个指针 → 1170² = 1,368,900
Level 3 (Leaf): 1170³ 个叶子节点, 每个叶节点存 ~100 行 → ~170M 行
→ 3 次磁盘 I/O 就能定位 1.7 亿行中的任意一行mermaid
graph TD
subgraph "B+Tree 物理结构"
R["Root Node (16KB)<br/>[key1|ptr][key2|ptr]...[keyN|ptr]"]
R --> I1["Internal Node (16KB)"]
R --> I2["Internal Node (16KB)"]
I1 --> L1["Leaf Node (16KB)<br/>[key|data][key|data]...<br/>→ next leaf"]
I1 --> L2["Leaf Node (16KB)<br/>← prev | ... | next →"]
I2 --> L3["Leaf Node (16KB)"]
end
subgraph "InnoDB 二级索引"
SI["二级索引 Leaf<br/>[索引列][主键ID]"] --> PK["回表: 用主键ID<br/>查聚簇索引"]
endInnoDB 聚簇索引 vs 二级索引的物理布局
| 特性 | 聚簇索引（主键） | 二级索引 |
|---|---|---|
| 叶子节点存什么 | 完整行数据 | 索引列 + 主键值 |
| 默认创建 | 有主键就用主键；无主键用第一个唯一非空索引；都没有就自建 6B ROW_ID | 手动创建 |
| 回表 | 不需要 | 需要（用主键值回聚簇索引查完整行） |
| 物理顺序 | 按主键排序存储 | 按索引列排序存储 |
| 建议 | 用自增 ID（避免页分裂和随机 IO） | 覆盖索引时不需要回表 |
sql
-- 聚簇索引示例
CREATE TABLE users (
id INT PRIMARY KEY, -- 聚簇索引：叶子存完整行
email VARCHAR(100),
INDEX idx_email (email) -- 二级索引：叶子存 (email, id)
);
-- 覆盖索引：不需要回表
SELECT id, email FROM users WHERE email = 'x@y.com';
-- 二级索引 idx_email 的叶子 (email, id) 已经满足查询 → 不回表
-- 需要回表：
SELECT * FROM users WHERE email = 'x@y.com';
-- 先查 idx_email → 得到 id → 再用 id 查聚簇索引 → 得到完整行LSM-Tree vs B+Tree 的写放大对比
| 维度 | B+Tree (InnoDB) | LSM-Tree (RocksDB/Cassandra) |
|---|---|---|
| 写入方式 | 随机写（修改磁盘页） | 顺序写（追加到 MemTable → SSTable） |
| 写放大 | 2-3×（页分裂 + Redo Log + Doublewrite） | 10-30×（Compaction 反复读写同一数据） |
| 读放大 | 1×（直接定位叶子页） | 5-20×（需要查 MemTable + 多层 SSTable + Bloom Filter） |
| 空间放大 | 低（页利用率 ~70%） | 中等（Compaction 前旧版本滞留） |
| 随机读 | 快（B+Tree 直接定位） | 慢（多层查找） |
| 范围扫描 | 快（叶子链表按序扫描） | 中等（需合并多个 SSTable） |
| 适合场景 | OLTP（读多写少、点查） | OLAP / 时序 / 日志（写密集、顺序读） |
mermaid
flowchart LR
subgraph "LSM-Tree 写入路径"
W["PUT key=value"] --> MT["MemTable<br/>(内存, 跳表)"]
MT -->|"满了"| SS1["SSTable Level 0<br/>(磁盘, 无序, ~8MB)"]
SS1 -->|"Compaction"| SS2["SSTable Level 1<br/>(有序, ~80MB)"]
SS2 -->|"Compaction"| SS3["SSTable Level N<br/>(更大)"]
end
subgraph "写放大来源"
C1["Level 0→1: 10×放大"]
C2["Level 1→2: 10×放大"]
C3["越下层放大越大"]
end何时选 B+Tree，何时选 LSM-Tree？
text
选 B+Tree (MySQL InnoDB / PostgreSQL):
- 读多写少, 点查为主
- 需要事务 (ACID)
- 需要 JOIN / 关联查询
- 数据量 < 1TB
- OLTP 场景 (订单、用户、账户)
选 LSM-Tree (RocksDB / Cassandra / HBase):
- 写密集 (日志、时序、IoT 传感器)
- 写多读少, 或读按时间范围
- 数据量 > 1TB, 需要水平扩展
- 不需要关联查询
- OLAP / 时序 / 事件溯源场景
登录后即可发表评论 👇