第 2 章 · 数据结构与算法设计范式
“算法这道题，面试要考，但它的价值远不止面试。“
本章覆盖的课程
| 编号 | 课程 | 说明 |
|---|---|---|
| 019 | 数据结构与算法之美 | 229 门课里唯一的纯算法 S 级课 |
为什么要大幅扩展这门课？
原课讲的是”面试够用”的算法。但你的目标是能创造新工具——这意味着你需要的不只是”会做题”，而是：
- 理解复杂度分析的完整含义——O(n) 不是全部，常数因子、缓存效应、摊还分析同样重要
- 掌握算法设计范式的全谱——遇到新问题知道该往哪个方向想
- 理解数据结构与存储层次的关系——为什么数据库用 B+Tree 而不是红黑树
章节结构
| 文档 | 内容 |
|---|---|
00-设计推演：数据结构怎么选.md | ★ 必读开篇：数组 → 有序数组 → 链表 → BST → 红黑树 → 哈希 → 跳表 → B+Tree → LSM 的九次失败演进 |
01-复杂度分析与算法工程观.md | 大 O 之外：常数因子、缓存复杂度、摊还分析、GC 友好 |
02-算法设计范式全谱.md | 分治/贪心/DP/回溯/分支限界/随机化/近似，配 Go 实现 |
03-工程视角的数据结构.md | B+Tree vs 红黑树、跳表、LSM、布隆过滤器、并查集，全部 Go 实现 |
★ 先读
00-设计推演。 它不是在罗列”有哪些结构”，而是让你自己走一遍： 从for i := range users的线性扫描开始，每遇到一个具体失败（O(n) 查询 / 插入慢 / BST 退化 / 磁盘上树太高 / 哈希不支持范围查询……），下一个结构就自然浮现了。走完这一篇你会明白一件事：不存在”最好的”数据结构，只有”被某组约束逼出来的形状”。
学完这一章，你应该能
- 说出一个算法的缓存复杂度（cache complexity），而不只是时间复杂度
- 遇到新问题，能判断它属于哪种设计范式，以及为什么其他范式不适用
- 解释为什么 LevelDB/RocksDB 用 LSM-Tree 而 MySQL 用 B+Tree
- 用 Go 实现一个完整的 B+Tree，能跑 benchmark
- 写出 GC 友好的算法实现（避免逃逸、复用对象、利用
[]byte免扫描特性）
这一章的核心观点
数据结构不是”抽象的东西”，它是为存储层次设计的。
CPU 寄存器 ~0.3 ns
L1 缓存 ~1 ns
L2 缓存 ~4 ns
L3 缓存 ~15 ns
主存 ~80 ns ← 红黑树的一个节点访问
SSD ~100 μs ← B+Tree 的一个节点访问
机械硬盘 ~10 ms
网络 ~1-100 ms
每一个数据结构的设计，都在针对某个特定的存储层次做优化：
- B+Tree：节点大小 = 磁盘页大小（4KB/16KB），把树高从 30 降到 3
- 跳表：用概率平衡代替严格平衡，实现简单且并发友好
- LSM-Tree：把随机写变成顺序写，用读放大换写放大
- 布隆过滤器：用极小的空间快速排除”一定不存在”
这跟第 1 章讲的缓存行、内存页、NUMA 是一脉相承的——都是”让相关的东西物理上靠近”这条法则的应用。
开始阅读：00-设计推演：数据结构怎么选