00 · 设计推演：数据结构怎么选
“不存在’最好的’数据结构。每一个结构都是被一组具体约束逼出来的形状。“
开场：一个具体的起点
老陈：需求很朴素——存 100 万用户，支持按 ID 查询。
小林：用 Go 的 map 啊。
老陈：不许用现成的。你自己设计。
小林：……那就用个数组？
老陈：好。写下来，然后我问你：查询
id=873245要多久？
v0：无序数组
type User struct {
ID int
Name string
}
var users []User // 100 万个
func Find(id int) *User {
for i := range users {
if users[i].ID == id {
return &users[i]
}
}
return nil
}这一版能工作。
失败：查询 O(n)，100 万数据平均要扫 50 万次。假设每次比较 1ns，就是 500 微秒。
老陈：如果 QPS 是 1 万，光查找就要花掉 5 秒的 CPU 时间/秒。也就是 5 个核全耗在查找上。
小林：那……排序一下？
老陈：排序了怎么查？
v1：有序数组 + 二分查找
// 按 ID 排序
func Find(id int) *User {
lo, hi := 0, len(users)-1
for lo <= hi {
mid := (lo + hi) / 2
switch {
case users[mid].ID == id:
return &users[mid]
case users[mid].ID < id:
lo = mid + 1
default:
hi = mid - 1
}
}
return nil
}改进巨大：O(n) → O(log n)。100 万数据只要 20 次比较。
失败：
| # | 问题 | 后果 |
|---|---|---|
| 1 | 插入 O(n) | 插到中间要移动后面所有元素 |
| 2 | 删除 O(n) | 同理 |
| 3 | ★ 缓存不友好（隐蔽但严重） | 见下 |
问题 3 值得展开：
二分查找的访问模式:
第1次: users[500000]
第2次: users[250000] ← 跳了 250000 × sizeof(User)
第3次: users[125000]
...
★ 每次跳跃都是几十 KB 甚至 MB 的跨度
★ 每次都是 cache miss + 大概率 TLB miss
实测对比（第 1 章第 01 节的数据）:
顺序扫描: ~3 ns/元素
随机访问: ~50 ns/元素（跨页时更糟）
★ 所以"20 次比较"听起来很美，但可能是 20 次 cache miss
实际耗时可能接近顺序扫几百个元素
老陈：这就是”理论复杂度”和”实际性能”的第一次冲突。
后面你会反复遇到：O(log n) 的随机访问，可能比 O(n) 的顺序扫描还慢。
数据结构的性能 = 复杂度 × 每次操作的常数，而常数主要由内存访问模式决定。
v2：链表
针对 v1 的插入问题，改用链表。
type node struct {
user User
next *node
}改进：插入 O(1)（已知位置时）。
失败：查询回到 O(n)，而且更慢——
数组的二分: 20 次跳跃访问，虽然 cache miss，但至少能跳
链表的查找: 必须顺着 next 指针走，n 次访问，且每个节点可能在不同内存页
★ 链表是最缓存不友好的结构，没有之一
老陈：链表在现代 CPU 上几乎是性能灾难。
Go 的
container/list用得少不是没原因的。如果非要链表语义，用数组 + 索引（第 1 章讲的 CSR 格式）——把指针换成
int32索引，缓存友好得多。
v1 和 v2 各解决一半问题。能不能都要？
v3：二叉搜索树（BST）
思路：既支持 O(log n) 查询，又支持 O(1) 插入。
500
/ \
250 750
/ \ / \
125 375 625 875
type node struct {
user User
left, right *node
}
func (n *node) find(id int) *User {
for n != nil {
switch {
case n.user.ID == id:
return &n.user
case id < n.user.ID:
n = n.left
default:
n = n.right
}
}
return nil
}理想情况：O(log n) 查询 + O(log n) 插入。
★ 致命失败：退化
如果按 ID 递增顺序插入: 1, 2, 3, 4, 5...
1
\
2
\
3
\
4
\
5
★ 退化成链表！查询变回 O(n)
老陈：这就是”最坏情况”的价值。
BST 平均 O(log n) 听起来不错，但”平均”取决于输入分布。 而真实数据往往是有序的（自增 ID、时间戳）——恰好是最坏情况。
记住：永远问”最坏情况是什么”。如果最坏情况不可接受，平均再好也没用。
这也是为什么快速排序要随机选 pivot（第 2 章第 02 节），为什么 Go 的 map 要随机哈希种子。
v4：自平衡树（AVL / 红黑树）
思路：插入删除时自动调整，保证树高 O(log n)。
| AVL | 红黑树 | |
|---|---|---|
| 平衡标准 | 左右子树高度差 ≤ 1 | 黑高相同，无连续红节点 |
| 树高上限 | 1.44 log n | 2 log n |
| 查询 | 更快（更平衡） | 稍慢 |
| 插入删除 | 更多旋转 | 更少旋转 |
| 适用 | 查询密集 | ★ 插入删除频繁（通用） |
改进：最坏情况也是 O(log n)。这就是 std::map、Java TreeMap、Linux 内核 rbtree 的选择。
失败：
| # | 问题 | 说明 |
|---|---|---|
| 1 | 指针跳转，缓存不友好 | 树高 20 = 20 次随机内存访问 |
| 2 | ★ 磁盘上完全不可用 | 见下 |
| 3 | 并发困难 | 旋转会修改多个节点，锁粒度大 |
问题 2 是关键的：
假设数据在磁盘上，1 亿条记录:
红黑树: 树高 log₂(10⁸) ≈ 27
→ 查询一次要 27 次磁盘 IO
→ HDD: 27 × 10ms = 270 ms ★ 灾难
→ SSD: 27 × 100μs = 2.7 ms
★ 磁盘的"每次访问成本"是内存的 10⁵ 倍
这时候"减少访问次数"比"减少比较次数"重要一万倍
老陈：这就是数据结构设计里最重要的一次视角转换：
当存储介质变化时，优化目标也变了。
内存: 优化"比较次数" → 平衡树 磁盘: 优化"IO 次数" → B+Tree不是红黑树不好，是它的优化目标不适合磁盘。
v5：哈希表
换个思路：不做比较，直接算出位置。
type HashTable struct {
buckets [][]Entry
}
func (h *HashTable) Get(key string) (Entry, bool) {
idx := hash(key) % len(h.buckets)
for _, e := range h.buckets[idx] {
if e.Key == key {
return e, true
}
}
return Entry{}, false
}改进：O(1) 查询，一次哈希 + 一两次内存访问。
失败：
| # | 问题 | 后果 |
|---|---|---|
| 1 | ★ 不支持范围查询 | 查询 id 在 1000-2000 之间 只能全表扫 |
| 2 | 哈希冲突 | 退化成链表（所以要好的哈希函数 + 扩容） |
| 3 | 无序 | 不能顺序遍历 |
| 4 | 扩容抖动 | rehash 时延迟尖刺（Go map 用渐进式扩容缓解） |
问题 1 是根本性的：
真实业务里，"范围查询"的需求极其常见:
· 查某时间段的订单
· 查分数前 100 名
· 查某价格区间的商品
· ORDER BY / GROUP BY
★ 数据库索引必须支持范围查询，所以哈希索引几乎不被用作主索引
（MySQL 只有 MEMORY 引擎支持哈希索引，且是显式指定）
v6：跳表（Skip List）
思路：在有序链表上加”多层索引”，用概率代替严格平衡。
第3层: 1 ────────────────────► 9
第2层: 1 ────────► 5 ────────► 9
第1层: 1 ──► 3 ──► 5 ──► 7 ──► 9
改进：
| 优势 | 说明 |
|---|---|
| 实现简单 | 比红黑树简单一个数量级（Redis 作者的理由） |
| ★ 范围查询友好 | 底层是有序链表，找到起点后顺序扫 |
| 并发友好 | 插入只改局部指针，不需要旋转 |
| 查询 O(log n) | 概率意义下 |
Redis 选跳表而不是红黑树的理由（作者 antirez 的原话）：
“Skip lists are… simpler to implement… and they offer… better performance for range queries (ZRANGE).”
失败：
| # | 问题 |
|---|---|
| 1 | 还是内存结构，磁盘上依然不行 |
| 2 | 内存开销（每个节点多层指针，约 1.33 倍） |
| 3 | 概率平衡，最坏情况无保证（虽然概率极低） |
v7：B+Tree —— 为磁盘而生
核心洞察：磁盘的最小 IO 单位是”页”（4KB/16KB）。一次 IO 能读一个页，那就要让一个页里装尽可能多的索引项。
第一个改动：多路搜索树
红黑树: 每个节点 1 个 key，2 个子节点
B+Tree: 每个节点 1000+ 个 key，1000+ 个子节点
★ 树高从 27 降到 3
★ IO 次数从 27 降到 3
第二个改动：节点大小 = 页大小
节点 16KB:
key 8 字节 + 指针 6 字节 = 14 字节
→ 1170 个 key/节点
→ 树高 3: 1170³ ≈ 16 亿条记录
→ ★ 16 亿数据，最多 3-4 次磁盘 IO
第三个改动：内部节点只存 key，不存数据
B-Tree: 所有节点都存数据 → 每节点 key 数少 → 树高
B+Tree: 只有叶子存数据 → 每节点 key 数多 → 树矮
★ 这是 B+Tree 相对 B-Tree 的核心优势
第四个改动：叶子用链表相连
范围查询 "id 1000-2000":
1. 定位到 id=1000 的叶子（3 次 IO）
2. ★ 顺着链表扫，几乎全是顺序 IO
B-Tree 要中序遍历（在树里上下跳，随机 IO）
B+Tree 只要顺序扫
这四个改动，每一个都针对磁盘的一个特性：
| 改动 | 针对的磁盘特性 |
|---|---|
| 多路 | 减少 IO 次数（IO 是主要成本） |
| 节点 = 页大小 | 一次 IO 读回尽量多的数据 |
| 内部节点只存 key | 让树更矮 |
| 叶子链表 | 范围查询变成顺序 IO |
失败：
| # | 问题 |
|---|---|
| 1 | 随机写 |
| 2 | 页分裂代价高 |
| 3 | 崩溃时页可能写一半 |
v8：LSM-Tree —— 换个方向优化写
B+Tree 的问题 1（随机写）在 HDD 上是致命的（随机写比顺序写慢 100 倍）。
换个思路：如果所有写都是追加呢？
B+Tree: 找到位置 → 原地修改 → 随机写
LSM: 追加到日志 → 内存排序 → 批量写成有序段 → 后台合并
★ 全是顺序写
（完整演进见第 4 章 00-设计推演：从零造一个存储引擎）
代价转换：
B+Tree: 写放大（页级） → 读快（3-4 次 IO）
LSM: 写快（顺序） → 读放大（要查多层多段）
★ 这是一次”约束转移”，不是”问题解决”。
老陈：这里有个很重要的认知升级：
很多设计改进，本质上不是”把问题解决”，而是”把问题从贵的资源转移到便宜的资源”。
- LSM: 把”磁盘随机写”转移到”磁盘顺序写 + CPU（合并）+ 空间（写放大）”
- 缓存: 把”延迟”转移到”内存成本”
- 索引: 把”查询时间”转移到”存储空间 + 写放大”
- CDN: 把”源站带宽”转移到”边缘节点成本”
当你优化不动时，问自己：“这个成本能不能转嫁到别的地方？”
★ 决策树：怎么选
需要什么操作？
│
├─ 只要点查询，不要范围
│ ├─ 数据在内存 → 哈希表
│ └─ 数据在磁盘 → 哈希索引（很少见）或 B+Tree
│
├─ 需要范围查询
│ ├─ 数据在内存
│ │ ├─ 读多写少 → 有序数组（二分）
│ │ ├─ 读写均衡 → 红黑树
│ │ ├─ 并发高 + 实现简单 → ★ 跳表
│ │ └─ 插入多、查询少 → 链表（但先看能不能用数组+索引）
│ │
│ └─ 数据在磁盘
│ ├─ 读多写少 / 需要事务 → ★ B+Tree
│ └─ 写多读少 / 数据量大 → ★ LSM-Tree
│
└─ 需要模糊查询 / 全文检索
└─ ★ 倒排索引（第 4 章第 03 节）
速查表
| 结构 | 查询 | 插入 | 范围 | 有序 | 磁盘友好 | 并发 | 代表 |
|---|---|---|---|---|---|---|---|
| 无序数组 | O(n) | O(1)摊销 | ❌ | ❌ | ❌ | ✅ | 小数据集 |
| 有序数组 | O(log n) | O(n) | ✅ | ✅ | ⚠️ | ✅ | 静态查表 |
| 链表 | O(n) | O(1) | ❌ | 可维护 | ❌ | ⚠️ | 队列/栈 |
| BST | O(log n)均 | O(log n)均 | ✅ | ✅ | ❌ | ⚠️ | 教学 |
| 红黑树 | O(log n) | O(log n) | ✅ | ✅ | ❌ | ⚠️ | TreeMap、epoll |
| 跳表 | O(log n)概 | O(log n)概 | ✅ | ✅ | ❌ | ✅ | Redis ZSet |
| 哈希表 | O(1) | O(1) | ❌ | ❌ | ❌ | ⚠️ | Go map |
| B+Tree | O(log n) | O(log n) | ✅ | ✅ | ★✅ | ⚠️ | MySQL、PG |
| LSM | O(层数) | ★O(1) | ✅ | ✅ | ★✅ | ✅ | RocksDB、Lucene |
★ 这一节真正的收获
不是”这些结构长什么样”，而是这条需求驱动的推导链：
需求: 存 100 万用户，按 ID 查
│
├─ v0 无序数组 失败: O(n) 查询
↓
├─ v1 有序数组+二分 失败: O(n) 插入；cache 不友好
↓
├─ v2 链表 失败: 查询回退 O(n)，缓存更糟
↓
├─ v3 BST 失败: 有序输入退化成链表（最坏情况！）
↓
├─ v4 红黑树 失败: 磁盘上树太高（27 次 IO）
↓
├─ v5 哈希表 失败: 不支持范围查询
↓
├─ v6 跳表 失败: 仍是内存结构
↓
├─ v7 B+Tree ← 优化目标从"比较次数"转为"IO 次数"
│ 失败: 随机写、写放大
↓
└─ v8 LSM ← 用"顺序写"换"读放大"
五个可以迁移的思维模式
① 永远问最坏情况
v3 的 BST 平均 O(log n) 很美，但有序输入退化成 O(n)。平均好不算好。
② 理论复杂度 ≠ 实际性能
v1 的二分是 O(log n)，但 20 次 cache miss 可能比顺序扫 200 个元素还慢。 常数因子由内存访问模式决定。
③ 存储介质变了，优化目标就变了
内存: 优化比较次数（红黑树）
磁盘: 优化 IO 次数（B+Tree）
SSD: 优化写放大（LSM）
④ 优化不动时，转移成本
LSM 没有”解决”写放大，而是把它转移成了读放大和空间放大。 问自己：“这个成本能转嫁到哪里？”
⑤ 先做最差版本，让失败指引方向
v0 很烂，但每个后续版本的改动，都是被 v0-vN 的具体失败逼出来的。 没有失败的清单，就没有改进的方向。
现在，轮到你了
练习：为下面这个需求推导数据结构。
需求：实时排行榜。100 万玩家，分数会频繁变动（每秒几万次更新），要能：
- 查某个玩家的排名（第几名）
- 查前 100 名
- 查某个玩家前后 10 名（“我附近的人”）
v0 会是什么？会失败在哪？
提示（不要用，先自己想）：
- v0 可能是”排序数组”，失败在更新 O(n)
- 需要考虑：排名怎么 O(log n) 算出来？
- “查前 100 名”要求什么遍历能力？
- 分数相同怎么办？
老陈：答案是”跳表 + 每个节点维护 span（跨度）“——Redis 的 ZSet 在元素较大时就是这么做的。
span 让”查排名”从 O(n) 变成 O(log n)：从最高层往下走，累加经过的跨度。
这个”用额外字段加速特定查询”的技巧，跟 B+Tree 的叶子链表是一类思路： 为高频查询专门设计一条快速路径。
下一节
这一节我们建立了”约束塑造结构”的视角，那一节会量化它——为什么 O(log n) 可能比 O(n) 慢，以及怎么算真实的常数因子。