土法炼钢兴趣小组的算法知识备份

算法与数据结构百科系列 · 写作计划

目录

算法与数据结构百科系列 · 写作计划

项目愿景

构建中文互联网上最系统、最深入的算法与数据结构技术博客系列。不做教科书搬运工，不做面试八股文集锦——每一篇文章都要回答三个问题：

  1. 这个算法 / 数据结构解决了什么真实的工程问题？
  2. 它的设计中最精妙的 trade-off 是什么？
  3. 在生产系统中，它是怎么被用（或被用错）的？

目标读者：中高级系统工程师。假设你会写 C/Go/Rust，理解操作系统和网络基础，用过数据库但不满足于只会写 SQL。如果你对 Linux 内核、分布式系统、密码学有一定了解（参见本站其他系列），阅读体验会更好。

与现有内容的关系：post/algorithms/ 下已有 7 篇文章（二分查找、KMP、Heavy Hitters、持久化数据结构、JSON 解析器、正则引擎、ReDoS），新系列在此基础上大幅扩展，已有文章保留并纳入系列索引，不重写不覆盖。

与其他系列的协同： - 系列八（OS 算法）与 post/linux/ 联动 - 系列九（DB 算法）与 post/db/ 联动 - 系列十（网络算法）与 post/network/ 联动 - 系列十一（并发数据结构）与 post/go/、post/rust/ 联动 - 系列十五（数论代数）与 post/crypt/、post/cryptography/ 联动

当前状态

已有文章

系列一：排序的工程哲学（6 篇）

系列二：哈希的万千面孔（8 篇）

系列三：树的进化史（8 篇）

系列四：字符串算法全景（7 篇）

系列五：概率数据结构与流式算法（7 篇）

系列六：向量检索与高维搜索（6 篇）

系列七：图算法工程实践（8 篇）

系列八：操作系统中的算法（8 篇）

系列九：数据库核心算法（7 篇）

系列十：网络协议中的算法（6 篇）

系列十一：并发数据结构（8 篇）

系列十二：压缩与编码（7 篇）

系列十三：计算几何（6 篇）

系列十四：动态规划进阶（6 篇）

系列十五：数论与代数算法（6 篇）

系列十六：编译器与语言实现中的算法（6 篇）

附加：算法工程杂谈（5 篇）

系列约定

  1. 目录命名: NN-english-slug/slug.md（两位数字前缀，小写连字符）

  2. 标题格式: H2 使用中文数字序号（## 一、## 二、## 三、…）

  3. 图表: SVG 使用暗色主题

    • 背景: #2d333b
    • 蓝色: #388bfd，绿色: #3fb950，橙色: #f0883e，紫色: #a371f7
    • 字体: ui-monospace, monospace，字号 13

  4. 代码: 完整可编译/运行的示例，首选 C/C++/Go/Rust

  5. 语言: 全中文写作，中文标点，专业术语首次出现时括注英文

  6. 交叉引用: 系列内使用相对 .html 路径

  7. 不使用 emoji

  8. Frontmatter 格式:

    ---
title: "标题"
date: YYYY-MM-DD
author: ltl
description: "描述"
categories: [algorithms]
tags: [tag1, tag2, tag3]
---

  9. 文章长度: 目标 800-1200 行（含代码），深度优先

  10. 每篇至少: 一个完整实现 + 一组基准测试数据 + 一个生产案例或工程陷阱

  11. 文末导航: 上一篇 / 下一篇 + 相关推荐

目录结构

post/algorithms/
├── plan.md                          # 本文件（不发布）
├── index.md                         # 系列索引页
├── 01-timsort/
│   ├── timsort.md
│   └── timsort-merge.svg
├── 02-pdqsort/
│   ├── pdqsort.md
│   └── pdqsort-decision.svg
├── ...
└── 115-competitive-analysis/
    └── competitive-analysis.md

写作优先级

第一梯队：基础设施级（与系统工程强相关）

  1. 系列八（OS 算法）— 与 Linux 系列联动最紧密
  2. 系列二（哈希）— 所有系统都在用，读者面最广
  3. 系列十一（并发数据结构）— 与 Go/Rust 系列联动
  4. 系列三（树）— 存储引擎的骨架

第二梯队：领域深耕级（与已有系列联动）

  1. 系列九（DB 算法）
  2. 系列十（网络算法）
  3. 系列十五（数论代数）— 与密码学双螺旋
  4. 系列十二（压缩编码）

第三梯队：拓展视野级

  1. 系列六（向量检索）— AI 时代刚需
  2. 系列四（字符串全景）— 延伸已有文章
  3. 系列七（图算法）
  4. 系列十六（编译器算法）— 延伸 JSON parser / regex

第四梯队：锦上添花级

  1. 系列一（排序）
  2. 系列五（概率数据结构）— 延伸 Heavy Hitters
  3. 系列十三（计算几何）
  4. 系列十四（DP 进阶）
  5. 附加系列

跨系列引用关系

                    ┌── 系列三(树) ──────────┐
                    │                        ↓
系列二(哈希) ───→ 系列八(OS算法) ←── 系列十一(并发)
    │                  ↓                     ↑
    │            系列九(DB算法) ←──── 系列十二(压缩)
    │                  ↓
    │            系列十(网络算法)
    │
    └──→ 系列五(概率DS) ──→ 系列六(向量检索)
                                ↑
                          系列十三(计算几何)

系列四(字符串) ──→ 系列十六(编译器) ──→ 系列十(GC)
    ↑                     ↑
  已有KMP/regex      已有JSON-parser

系列十五(数论) ←──→ 已有密码学系列(crypt/cryptography)

系列十四(DP进阶) ──→ 系列七(图算法)

详细大纲

系列一：排序的工程哲学

01 · TimSort 深度解剖：Python 与 Java 默认排序的精妙设计

目标: 理解 TimSort 为什么能成为两大语言标准库的默认排序，它对真实数据的哪些特征做了针对性优化。

内容要点: - 真实数据不是随机的：生产环境中数据的有序性统计 - Run 检测：识别升序和严格降序子序列，反转降序 run - minrun 的选择：为什么是 32-64 之间的 2 的幂附近值 - 二分插入排序：对短 run 的优化，为什么不用普通插入排序 - 归并策略：merge stack invariant（Tim Peters 的不变量） - galloping mode：当一侧连续胜出时切换到指数搜索 - galloping 的自适应阈值：min_gallop 的动态调整 - 临时缓冲区管理：merge_lo 与 merge_hi 的空间优化 - 稳定性保证：为什么稳定排序在工程中比快排更常用 - Java 的 TimSort bug（2015）：形式化验证发现的栈溢出

代码/示例: C 实现核心 TimSort（run 检测 + galloping merge），附与 std::sort 的基准对比

SVG: TimSort 的 merge stack 状态变化图

02 · pdqsort：击败所有对手的模式自适应排序

目标: 解析 Rust std::sort_unstable 和 C++ Boost.Sort 背后的 pdqsort，理解”模式击败”的含义。

内容要点: - Introsort 回顾：快排 + 堆排的混合策略，为什么还不够好 - pdqsort 的三重策略：对随机数据用快排，对有序数据用插入排序，对对抗性数据用堆排 - pivot 选择：median-of-three，为什么不用 median-of-medians - 分区方案：Hoare partition 的现代变体，branchless partition - pattern-defeating：检测重复元素（Dutch National Flag）和预排序（已排序 run 检测） - 坏分区计数：何时从快排回退到堆排 - 小数组优化：insertion sort 的阈值选择（为什么是 24 而不是 16） - 与 introsort、TimSort、std::sort 的基准对比（随机、已排序、逆序、重复、pipe organ） - Rust 标准库的 pdqsort 实现解读

代码/示例: Rust/C++ 实现 pdqsort 核心，多种数据分布下的 benchmark

SVG: pdqsort 的决策流程图

03 · 基数排序：打破比较下界的正确姿势

目标: 理解非比较排序的理论基础、工程实现难点和适用场景边界。

内容要点: - 比较排序的 O(n log n) 下界证明：决策树模型 - 基数排序不违反下界的原因：它不在比较模型中 - MSD vs LSD 基数排序：稳定性、缓存友好性、递归开销 - 计数排序作为基础：为什么桶的数量是关键参数 - 缓存友好性问题：基数排序的随机内存访问模式 - ska_sort：Adrian Kuegel 的缓存友好基数排序，American Flag Sort 变体 - 为什么数据库排序不用基数排序：变长键、复合键、比较语义 - 基数排序的实际最佳场景：整数数组、固定长度字符串、IP 地址 - 与 pdqsort / std::sort 的跨数据类型性能对比

代码/示例: C 实现 LSD/MSD 基数排序和 ska_sort 变体，缓存命中率对比

SVG: MSD vs LSD 的桶分配过程对比图

04 · 外部排序：当数据装不进内存

目标: 理解处理超大数据集的排序工程，从磁盘 I/O 模型到现代 SSD 上的优化。

内容要点: - 外部存储模型（External Memory Model）：I/O 复杂度 O(N/B · log_{M/B}(N/B)) - 基本多路归并：将数据切分为内存大小的 run，排序后写回，再多路归并 - 初始 run 生成：replacement selection vs 内部排序，为什么现代系统倾向后者 - 多路归并的优先队列：败者树（Loser Tree）vs 最小堆，为什么败者树更快 - 缓冲区管理：double buffering，预读与异步 I/O - 磁盘顺序读写 vs 随机读写的性能差异（实测数据） - SQLite 的外部排序实现：b-tree sorter 源码分析 - LevelDB/RocksDB 中的排序：SSTable 构建过程 - SSD 时代的变化：随机读性能改善后外部排序策略的演进 - 分布式排序：MapReduce 的 shuffle & sort

代码/示例: C 实现多路外部归并排序（含败者树），对 10GB 数据的实测

SVG: 多路归并的数据流动图

05 · 并行排序：从归并网络到 GPU 双调排序

目标: 理解排序的并行化，从理论上的排序网络到工业级的多核/GPU 排序实现。

内容要点: - 比较器网络与 0-1 原理 - Batcher 的奇偶归并网络与双调排序（Bitonic Sort） - 双调排序的 GPU 映射：为什么它特别适合 SIMD/GPU - 并行归并排序：work-efficient parallel merge（Merge Path 算法） - 多核 CPU 上的并行排序：Intel TBB parallel_sort、GNU parallel mode - 采样排序（Sample Sort）：适合分布式环境的并行快排 - GPU 排序：CUB DeviceRadixSort、Thrust sort、ModernGPU 的实现 - 实测对比：单线程 pdqsort vs 多核并行排序 vs GPU 排序（不同规模和数据类型） - 并行排序的 scalability 分析：Amdahl 定律在排序中的体现

代码/示例: CUDA 双调排序实现 + OpenMP 并行归并排序，GPU vs CPU 基准测试

SVG: 双调排序网络的比较器连线图

06 · 排序基准测试：用数据说话

目标: 建立一个严谨的排序算法基准测试框架，用实测数据回答”什么时候该用什么排序”。

内容要点: - 基准测试方法论：如何避免常见的 micro-benchmark 陷阱 - 数据分布生成器：均匀随机、正态分布、已排序、逆序、锯齿、pipe organ、重复率控制 - 12 种排序算法的统一测试：insertion、heap、merge、quick、introsort、pdqsort、TimSort、radix (LSD/MSD)、ska_sort、std::sort、std::stable_sort、parallel sort - 性能指标：吞吐量（elem/s）、比较次数、交换/移动次数、缓存命中率（perf stat） - 分支预测率的量化分析：perf stat branch-misses - 不同数据规模的性能变化曲线：从 16 个元素到 1 亿个元素 - 不同元素大小的影响：4B int vs 64B struct vs 1KB record - 稳定性 vs 性能的 trade-off 量化 - 关键结论与选型指南

代码/示例: 完整的 C/C++ 基准测试框架（可复现），生成性能图表的脚本

SVG: 多组对比性能图表

系列二：哈希的万千面孔

07 · 哈希表内部：开放寻址、链式、Robin Hood 的三国演义

目标: 深入理解三大哈希表实现策略的内部机制与工程权衡。

内容要点: - 哈希表的基本操作：插入、查找、删除的复杂度分析 - 链式哈希（Separate Chaining）：简单可靠，但缓存不友好 - 链表 vs 红黑树（Java 8 HashMap 的优化） - 每次查找的平均指针追踪次数 - 开放寻址（Open Addressing）：线性探测、二次探测、双重哈希 - 线性探测的聚集（clustering）问题 - Robin Hood Hashing：从穷人手中偷取位置的公平策略 - Robin Hood 的 PSL（Probe Sequence Length）分布收窄效应 - backward-shift deletion vs tombstone - 负载因子与性能曲线：实测不同负载因子下的查找 / 插入性能 - 扩容策略：翻倍 vs 渐进式 rehash（Redis 的做法） - 缓存行分析：链式 vs 开放寻址在 L1/L2/L3 命中率的差异 - Go map 的实现：bucket 数组 + overflow 链 + evacuation - Rust HashMap 的实现：基于 Swiss Table（hashbrown） - 真实工作负载下的性能对比

代码/示例: C 分别实现链式 / 线性探测 / Robin Hood 三种哈希表，附负载因子 - 性能曲线

SVG: 三种策略的探测路径对比图

08 · Cuckoo Hashing：最坏 O(1) 查找的优雅设计

目标: 理解 Cuckoo Hashing 的理论基础、实现细节和失败处理。

内容要点: - 问题定义：为什么最坏 O(1) 查找比期望 O(1) 更有价值（实时系统、网络设备） - 基本 Cuckoo Hashing：两个哈希函数、两张表、踢出链 - 随机图理论视角：插入成功等价于 Cuckoo Graph 无环或仅有小环 - 负载因子上限：基本方案约 50%，为什么？ - d-ary Cuckoo Hashing：d > 2 个哈希函数将负载因子推高到 90%+ - BFS vs DFS 替换路径搜索：BFS 更短但开销更大 - 桶化 Cuckoo Hashing：每个位置存 k 个元素，大幅提升负载因子 - Cuckoo Filter 的起源：从哈希表到布隆过滤器替代品 - DPDK 中的 Cuckoo Hash：rte_hash 源码分析 - 与 Robin Hood、Swiss Table 的性能对比

代码/示例: C 实现 d-ary Cuckoo Hash（带 BFS 踢出），附失败率 vs 负载因子曲线

SVG: Cuckoo 踢出链的图示

09 · Swiss Table：Google 的 SIMD 加速哈希表

目标: 深入解析 Abseil flat_hash_map 的设计，理解 SIMD 如何加速哈希表探测。

内容要点: - 传统开放寻址的瓶颈：每次探测都要比较完整 key - Swiss Table 的核心创新：元数据数组（control bytes） - 控制字节的设计：7 位 H2 哈希 + 1 位 empty/deleted/full 标记 - SSE2 加速的组探测：一次 SIMD 指令检查 16 个控制字节 - _mm_cmpeq_epi8 + _mm_movemask_epi8 的工作原理 - Group 探测的位运算：ctz 找到第一个匹配位 - 增长策略：capacity 必须是 2^n - 1 的原因（H1 取模优化） - tombstone 处理：为什么 Swiss Table 区分 EMPTY 和 DELETED - 内存布局：元数据与数据分离的缓存优势 - Abseil flat_hash_map vs std::unordered_map 基准对比 - hashbrown（Rust 版 Swiss Table）的实现差异 - 在 ARM NEON 上的适配：没有 SSE2 怎么办

代码/示例: C 实现简化版 Swiss Table（含 SSE2 探测），附与 std::unordered_map 基准对比

SVG: Swiss Table 的控制字节 + SIMD 探测示意图

10 · 完美哈希：从理论到 gperf 实践

目标: 理解完美哈希的理论极限和工业应用，特别是编译器关键字识别场景。

内容要点: - 完美哈希函数（PHF）vs 最小完美哈希函数（MPHF） - 理论下界：n 个键的 MPHF 至少需要 ~1.44 bits/key - FKS 两级哈希：Fredman-Komlós-Szemerédi 的经典构造 - CHD 算法（Compress, Hash and Displace）：空间接近理论极限 - hash-displace-compress：Botelho-Pagh-Ziviani 的工业级 MPHF - gperf：GNU 的完美哈希生成器 - 如何为编译器关键字表生成 PHF - gperf 的关联值搜索算法 - 在编译器中的应用：GCC/Clang 的关键字识别 - cmph 库：多种 MPHF 算法的 C 实现 - 静态数据集 vs 动态数据集：完美哈希的适用边界 - 与 Cuckoo Filter、Ribbon Filter 的概念对比

代码/示例: 用 gperf 为 C 关键字集生成 PHF，C 实现 CHD 算法

11 · 一致性哈希：不要相信教科书版本

目标: 破除对一致性哈希的常见误解，对比多种现代方案。与 post/system-design/ 联动。

内容要点: - 问题定义：分布式缓存 / 存储的键分配问题 - 教科书版一致性哈希（Karger 1997）：环 + 虚拟节点 - 虚拟节点的问题：内存开销大、负载不均匀性仍然显著 - 实测：100 个物理节点 × 150 虚拟节点的负载方差 - Jump Consistent Hash（Google 2014）：O(ln n) 时间、O(1) 空间、完美均匀 - 但只支持顺序编号的桶，不支持任意删除 - Multi-probe Consistent Hashing（Google 2015）：O(1) 空间 + 任意节点增删 - Maglev Hashing（Google 2016）：查表法，O(1) 查找，用于 Google 负载均衡器 - 置换表生成算法的精巧设计 - Rendezvous Hashing（Highest Random Weight）：最简单的替代方案 - 各方案的对比：均匀性、内存、查找速度、节点增删成本 - 实际系统的选择：Cassandra（虚拟节点）、Dynamo（虚拟节点）、Envoy（Maglev/Ring）

代码/示例: Go 实现 Jump / Maglev / Rendezvous / 虚拟节点四种方案，负载均匀性对比

SVG: 各方案的负载分布热力图

12 · Bloom Filter 全家族：Standard → Counting → Cuckoo → Ribbon

目标: 全面掌握概率集合成员判定问题的所有主流方案。

内容要点: - Standard Bloom Filter 回顾：最优哈希数 k = (m/n) ln 2 的推导 - false-positive 概率的精确公式 vs 近似公式 - 空间效率的信息论极限：每个元素至少 ~1.44 bits 才能达到给定 FPR - Counting Bloom Filter：支持删除，但 4× 空间开销 - Blocked Bloom Filter：缓存友好的分块设计 - Cuckoo Filter（Fan et al. 2014）：部分键 + Cuckoo Hash - 支持删除、空间效率更高、查找更快 - fingerprint 长度与 FPR 的关系 - 满载时的插入失败问题 - Quotient Filter：紧凑存储的另一条路 - Ribbon Filter（Google 2021）：空间效率接近理论极限 - 基于带状矩阵的高斯消元 - 构建时间 vs 查询速度的 trade-off - 各方案的综合对比：空间、查询速度、构建速度、删除支持 - 在生产系统中的应用：RocksDB（Ribbon Filter）、Chrome（Bloom Filter）

代码/示例: C 实现 Standard Bloom / Cuckoo Filter / 简化 Ribbon Filter，FPR vs 空间对比

SVG: 各 filter 方案的空间效率对比图

13 · 密码学哈希 vs 非密码学哈希：设计哲学的分野

目标: 理解两类哈希函数的不同设计目标，以及在工程中的正确选型。与 post/crypt/ 联动。

内容要点: - 非密码学哈希的目标：速度 + 分布均匀性 - 密码学哈希的目标：原像抗性 + 碰撞抗性 + 雪崩效应 - avalanche effect 的量化：SMHasher 测试套件 - 常见非密码学哈希函数：MurmurHash3、CityHash、FarmHash、xxHash - SipHash：在两者之间的特殊位置 - 为什么 Python/Rust/Ruby 都用 SipHash 做默认哈希 - HashDoS 攻击：从 PHP 到 CCC 大会的演示 - SipHash-2-4 的 ARX 结构与安全性分析 - wyhash：当前速度最快的通用哈希之一 - 密码学哈希不该用在哈希表中的原因：速度代价 - 非密码学哈希不该用在安全场景的原因：length extension、碰撞攻击 - 哈希函数选型决策树

代码/示例: C 实现 SipHash-2-4，附 HashDoS 攻击演示

SVG: 两类哈希函数的设计目标雷达图

14 · 向量化哈希：xxHash3 与 wyhash 的 SIMD 实现

目标: 深入理解现代哈希函数如何利用 SIMD 指令达到极致吞吐量。

内容要点: - 哈希函数的性能上限：内存带宽 - xxHash3 的设计（Yann Collet） - 短输入路径（≤ 16B）：为什么用不同的算法 - 中等输入（17-128B）：单次累加 - 长输入（> 128B）：多条 accumulator 并行 - 最终 avalanche：为什么需要 XXH3_avalanche - 128 位输出与 secret 的使用 - wyhash 的设计（王一） - 核心操作：multiply-and-xor - 利用 128 位乘法（_umul128 / __uint128_t） - 极简代码量下的高质量与极速 - AES-NI 加速的哈希：AHash（Rust）、meow_hash - 用硬件 AES 指令做非密码学哈希的争议 - 基准测试：不同输入长度下 xxHash3 / wyhash / CRC32C / AHash 的吞吐量 - SMHasher 质量测试：分布均匀性、碰撞率、雪崩质量

代码/示例: C 实现 wyhash 核心（< 30 行），xxHash3 长输入路径分析，throughput 基准

系列三：树的进化史

15 · 红黑树 vs AVL：Linux 内核为什么选红黑树

目标: 用精确数据解答这个经典争论，深入内核源码理解红黑树的实际应用。

内容要点: - AVL 树回顾：严格平衡（左右子树高差 ≤ 1）、旋转操作 - 红黑树的五条性质与平衡保证：最长路径 ≤ 2× 最短路径 - 旋转次数的精确分析：插入最多 2 次旋转，删除最多 3 次旋转 - AVL 插入最多 2 次旋转，但删除可能 O(log n) 次 - Linux 内核的 rbtree（lib/rbtree.c）源码解读 - 颜色位存在父指针的最低位中（节省空间） - augmented rbtree 的设计：interval tree 的实现 - 内核中红黑树的使用场景统计：CFS 调度器、epoll、内存管理（VMA） - CFS 调度器的红黑树：以虚拟运行时间为 key 的插入/删除/leftmost - 为什么内核选红黑树不选 AVL：删除的旋转次数上界更好、实现稍简单 - 但 AVL 在读密集场景更优：搜索的高度更低 - 实测对比：插入密集、删除密集、搜索密集、混合工作负载

代码/示例: C 实现红黑树和 AVL 树，附各种工作负载下的性能对比

SVG: 红黑树插入/删除的旋转步骤图解

16 · B-tree 深度解剖：从磁盘 I/O 模型到 boltdb 源码

目标: 从 I/O 模型的第一性原理出发理解 B-tree，再通过 boltdb 源码看真实实现。

内容要点: - 磁盘 I/O 模型：页面大小、随机 I/O vs 顺序 I/O、B-tree 的诞生动机 - B-tree 的性质：最小度 t、节点容量 [t-1, 2t-1]、高度 O(log_t n) - 搜索、插入、删除的完整算法与复杂度分析 - 节点分裂（split）与合并（merge）的详细步骤 - B+tree 的改进：所有数据在叶子、叶子链表支持范围查询 - bulk loading：自底向上构建，避免大量分裂 - 写放大分析：一次插入可能触发多少页面写入 - boltdb 源码逐行解读（Go）： - 页面布局（branchPageElement / leafPageElement） - mmap 文件 I/O - 事务与 CoW 策略 - 游标（Cursor）的遍历实现 - B-tree 的现代变体：B-link tree（Lehman-Yao 并发协议）、Bε-tree（写优化）

代码/示例: Go 实现简化 B+tree（含 bulk loading），附不同阶数下的 I/O 次数实测

SVG: B-tree 节点分裂过程图

17 · B+tree 与 LSM-tree：两种存储引擎哲学的碰撞

目标: 用”读放大 / 写放大 / 空间放大”三角模型统一分析两种架构。与 post/db/ 联动。

内容要点: - 读放大（Read Amplification）：一次逻辑读需要多少次物理 I/O - 写放大（Write Amplification）：一次逻辑写产生多少倍的物理写入 - 空间放大（Space Amplification）：实际占用空间 / 有效数据大小 - B+tree（InnoDB）的分析：读放大低、写放大中等、空间放大低 - 随机写的页面分裂代价 - WAL 的额外写入 - LSM-tree（RocksDB）的分析：读放大高、写放大高、空间放大中等 - MemTable → L0 → L1 → … 的 compaction 过程 - leveled compaction 的写放大：T × (层数 - 1) - 三角关系的不可能定理：不可能同时最小化三者 - RUM 猜想（Read-Update-Memory conjecture） - 实测对比：随机写吞吐、随机读延迟、范围扫描速度、空间占用 - WiscKey（FAST 2016）：键值分离以减少 LSM-tree 写放大 - 混合方案：TiDB 的 B+tree 索引 + RocksDB 存储

代码/示例: 简化 LSM-tree（MemTable + SSTable + Compaction）Go 实现，附与 B+tree 基准对比

SVG: 读放大/写放大/空间放大三角图

18 · Treap 与跳表：随机化的力量

目标: 理解随机化如何优雅地解决平衡性问题，以及 Redis 为什么选跳表。

内容要点: - 随机化 BST 的动机：避免红黑树 / AVL 的复杂旋转逻辑 - Treap = Tree + Heap：随机优先级实现概率平衡 - 期望高度 O(log n) 的证明（与随机化快排的联系） - 插入 / 删除的旋转操作 - 可合并（merge）和可分裂（split）的 Treap - 跳表（Skip List）：概率化的多层链表 - 随机层数的几何分布：期望层数 O(log n) - 搜索的期望比较次数：O(log n) - 插入和删除的无旋转实现 - Redis ZSET 为什么用跳表不用红黑树： - 范围操作天然高效 - 实现简单、容易调试 - 内存占用可控（平均 1.33 指针/节点） - antirez 本人的回答 - Java ConcurrentSkipListMap：跳表在并发场景的天然优势 - 跳表 vs 红黑树 vs B-tree 的综合性能对比

代码/示例: C 实现 Treap（含 split/merge）和跳表，附 Redis ZSET 场景的性能对比

SVG: 跳表的多层结构与搜索路径图

19 · 线段树与树状数组：区间问题的优雅武器

目标: 深入理解区间查询与修改的数据结构，从竞赛到工业应用。

内容要点: - 问题分类：静态区间查询（前缀和/稀疏表）、单点修改+区间查询、区间修改+区间查询 - 树状数组（Binary Indexed Tree / Fenwick Tree）： - lowbit 技巧的位运算本质 - 单点更新 + 前缀查询的 O(log n) 实现 - 用差分实现区间修改 - 二维树状数组 - 线段树（Segment Tree）： - 递归建树与区间合并 - 单点修改 + 区间查询 - 懒标记（Lazy Propagation）实现区间修改 - 权值线段树与动态开点 - 持久化线段树（主席树）： - path copying 实现历史版本 - 第 k 小问题的经典解法 - 空间优化：动态开点 + 回收 - 工业应用：数据库的区间索引、时序数据聚合、CDN 带宽统计 - 线段树 vs 树状数组的选型：什么时候用谁

代码/示例: C++ 实现树状数组 + 懒标记线段树 + 主席树，附区间操作性能对比

SVG: 线段树的区间分解与懒标记下推示意图

20 · 持久化数据结构：函数式世界的基石

目标: 深入理解 path copying 和 fat nodes，以及持久化数据结构在现代系统中的应用。扩展已有 ads/persistent 文章。

内容要点: - 持久化的定义：partial persistence vs full persistence vs confluent persistence - Path Copying：修改只复制路径上的节点 - 持久化二叉搜索树的 O(log n) 时间与空间 - 与 Git 对象模型的联系 - Fat Nodes：在节点中存储所有历史版本 - 空间效率更高但查询需要版本搜索 - Clojure 的持久化 Vector：HAMT（Hash Array Mapped Trie） - 32 叉树的选择：缓存行与 CPU 字长的平衡 - 结构共享的内存效率 - transient 优化：批量修改时的临时可变性 - Immutable.js 和 Scala 的持久化集合 - 写时复制（CoW）与持久化的关系：btrfs、ZFS 的文件系统 CoW - 数据库中的 MVCC 作为一种持久化数据结构 - 持久化 vs 不可变：语义上的细微差别

代码/示例: Go 实现持久化红黑树（path copying），附版本切换的性能测试

SVG: path copying 的新旧版本结构共享图

21 · Van Emde Boas 树：当 O(log log n) 不只是理论

目标: 理解 VEB 树的递归结构之美，以及在哪些场景下它真正有用。

内容要点: - 问题定义：在 {0, 1, …, U-1} 宇宙上的 predecessor/successor 查询 - 二叉查找树的 O(log n)、平衡 BST 的 O(log n)、为什么能做到 O(log log U) - VEB 树的递归结构：summary + clusters，宇宙大小每次开方 - 插入、删除、successor、predecessor 的详细算法 - 空间优化：从 O(U) 到 O(n)（哈希化 VEB） - X-fast Trie 与 Y-fast Trie：另一条 O(log log U) 的路 - 实际应用场景： - Linux 内核的 O(1) 调度器（部分思路类似 VEB 的位图层级） - 网络路由中的最长前缀匹配 - 定时器管理中的高效 predecessor 查询 - 为什么 VEB 树很少在实际系统中直接使用：常数因子、缓存不友好 - 实测：VEB vs 红黑树 vs 跳表在 successor 查询上的性能

代码/示例: C 实现 VEB 树和 X-fast Trie，附 predecessor 查询的基准对比

SVG: VEB 树的递归宇宙分割图

22 · Merkle 树与认证数据结构：从 Git 到区块链

目标: 理解 Merkle 树如何提供数据完整性验证，以及现代变体。与 post/crypt/ 联动。

内容要点: - Merkle 树的基本结构：叶子存数据哈希，内部节点存子节点哈希的哈希 - 成员证明（Membership Proof）：O(log n) 个哈希即可验证 - 增量验证：修改数据后只需重算路径上的哈希 - Git 的对象模型：blob → tree → commit 就是一棵 Merkle 树 - Bitcoin 的 Merkle 树：区块中交易的 Merkle Root，SPV 轻客户端验证 - Merkle Patricia Trie：Ethereum 的状态树 - 前缀压缩的 trie + Merkle 哈希 - 为什么 Ethereum 需要它（状态根的高效验证） - Certificate Transparency：Google 的日志审计用 Merkle 树 - Merkle Mountain Range：只追加的 Merkle 结构 - 认证跳表（Authenticated Skip List）：替代 Merkle 树的方案 - Verkle 树（Vector commitment + Merkle）：Ethereum 的未来方向

代码/示例: Go 实现 Merkle 树（含 proof 生成与验证），附增量更新性能测试

SVG: Merkle Proof 的路径验证示意图

系列四：字符串算法全景

23 · 后缀数组：比后缀树更实用的选择

目标: 理解后缀数组为什么在工程中逐渐取代后缀树，掌握线性构造算法。

内容要点: - 后缀树回顾：强大但空间开销巨大（~20 bytes/char） - 后缀数组的定义：后缀按字典序排序后的起始位置数组 - 后缀数组能做的事：模式匹配（二分查找 O(m log n)）、最长重复子串、最长公共子串 - 构造算法的进化： - 朴素 O(n^2 log n) - 前缀倍增（Manber-Myers）O(n log^2 n) → O(n log n) - DC3/Skew 算法 O(n) - SA-IS（Nong et al. 2009）O(n)：目前实践中最常用的线性算法 - LCP 数组（Longest Common Prefix）： - Kasai 算法 O(n) 构造 - LCP 数组的应用：最长重复子串 = max(LCP) - 在全文索引中的应用：基于后缀数组的全文搜索 - 在生物信息中的应用：基因组序列比对 - 后缀数组 vs 后缀树 vs FM-index 的时空权衡

代码/示例: C 实现 SA-IS 算法 + Kasai LCP 构造，附模式匹配和最长重复子串示例

SVG: 后缀数组与 LCP 数组的对应关系图

24 · AC 自动机：多模式匹配与入侵检测系统

目标: 理解多模式匹配的工业级方案，以及在安全系统中的实际应用。

内容要点: - 问题定义：在文本中同时搜索多个模式串 - 朴素方案：对每个模式串跑 KMP / BM，O(mk × n) 总时间 - AC 自动机：Trie + KMP 的 fail 函数扩展 - Trie 构建：所有模式串的前缀树 - fail 指针构造：BFS 层级计算，类比 KMP 的 failure function - 字典后缀链接（dictionary suffix link）：输出链 - 匹配过程：O(n + m + z) 时间（z 为匹配数） - goto/failure/output 三函数的状态机视角 - 编译为 DFA：消除 fail 跳转，用空间换时间 - 状态爆炸问题：为什么 Snort 2.x 用 DFA 而 3.x 回到 NFA - 在入侵检测系统中的应用： - Snort/Suricata 的规则匹配引擎 - Hyperscan（Intel）的混合匹配架构 - 敏感词过滤的工业实践 - AC 自动机 vs 正则引擎 vs SIMD 字符串搜索的性能对比

代码/示例: C 实现 AC 自动机（含 fail 指针 + 输出链），附多模式匹配基准测试

SVG: AC 自动机的 Trie + fail 指针结构图

25 · BWT 与 FM-index：从 bzip2 到基因组比对

目标: 理解 BWT 的信息论含义和 FM-index 的优雅搜索算法。

内容要点: - Burrows-Wheeler 变换（BWT）： - 旋转矩阵视角：所有循环移位排序后取最后一列 - BWT 的可逆性证明：为什么最后一列 + 首列排序可以恢复原串 - LF-mapping 的数学原理 - BWT 为什么有利于压缩：相似上下文的字符被聚集 - bzip2 的压缩管线：BWT → Move-to-Front → RLE → Huffman - FM-index（Ferragina-Manzini）： - Occ 表（occurrence table）与 C 表 - backward search 算法：O(m) 搜索时间 - 空间优化：采样与 wavelet tree - 在基因组比对中的应用： - BWA-MEM 的工作原理：seed-and-extend - 为什么参考基因组用 FM-index 而不是哈希表 - 与后缀数组的关系：BWT ↔︎ SA 的互相转换 - r-index：run-length BWT 的压缩索引

代码/示例: C 实现 BWT 编码/解码 + 简化 FM-index backward search

SVG: BWT 旋转矩阵与 LF-mapping 图

26 · 编辑距离与模糊匹配：搜索引擎的纠错秘密

目标: 从经典 DP 到位并行算法，理解搜索引擎拼写纠错的底层技术。

内容要点: - 编辑距离（Levenshtein Distance）：插入、删除、替换三种操作 - Wagner-Fischer 算法：经典 O(nm) 动态规划 - 优化： - 提前终止（当距离超过阈值 k 时） - 对角线优化（Ukkonen）：O(kn) 当 k 较小 - 位并行（Myers’ bit-parallel）：用位运算打包 DP 矩阵的一列 - 利用 64 位 word 一次处理 64 行 - 实际性能：比朴素 DP 快 10-60× - Bitap 算法（Shift-Or）：结合正则和近似匹配 - Damerau-Levenshtein 距离：考虑相邻字符交换 - Elasticsearch 的 fuzzy query 实现： - Levenshtein automaton 的构造 - 与倒排索引的结合 - SymSpell 算法：预计算删除变体的快速近似搜索 - 在搜索引擎中的应用：Did you mean… 的实现

代码/示例: C 实现 Myers’ bit-parallel 编辑距离，附与朴素 DP 的性能对比

27 · 字符串哈希：Rabin-Karp 与滚动哈希的工程实践

目标: 深入理解滚动哈希的数学原理和实际应用中的坑。

内容要点: - Rabin-Karp 算法：多项式哈希 + 滚动更新实现 O(n) 期望时间匹配 - 多项式哈希的选择：基数 b 和模数 p 的选取 - 生日悖论与碰撞概率分析 - 双哈希（double hashing）降低碰撞概率 - anti-hash 测试：如何构造让特定哈希函数碰撞的输入 - Codeforces 上的 hack 案例 - 随机化基数的防御策略 - rsync 的滚动校验和：Adler-32 变体 - 弱哈希（rolling）+ 强哈希（MD4/MD5）的两级校验 - 文件同步的块匹配算法 - 滚动哈希在抄袭检测中的应用：Winnowing 算法 - 内容寻址存储（CAS）中的分块哈希：Rabin fingerprint - 数据去重（deduplication）的分块策略 - CDC（Content-Defined Chunking）

代码/示例: C 实现 Rabin-Karp 匹配 + Rabin fingerprint 分块，附碰撞率分析

28 · SIMD 字符串处理进阶

目标: 深入理解向量化字符串操作的设计模式。与已有 simd-strfind.org 联动。

内容要点: - SSE4.2 字符串指令回顾：PCMPESTRI / PCMPESTRM - 四种模式：equal each、equal any、ranges、equal ordered - 为什么它们在实际中不如预期快 - 更好的方案：用通用 SIMD 指令构建字符串操作 - 向量化 memchr： - 16 字节一组比较 + movemask - glibc 的实现 vs 手写优化 - 向量化 strlen：找第一个 ‘\0’ - 向量化 JSON 解析：simdjson 的架构 - Stage 1：SIMD 标记结构字符（{, }, [, ], :, ,, “） - Stage 2：tape 构建与解析 - 为什么 simdjson 能达到 GB/s 级解析速度 - Hyperscan 的向量化设计：多正则引擎 - UTF-8 验证的 SIMD 实现：simdutf 库 - AVX-512 vs AVX2 vs NEON 的适配策略

代码/示例: C 实现 SIMD memchr + SIMD JSON 结构字符标记，附性能基准

29 · Unicode 算法：UTF-8 的精妙设计与文本处理的隐藏陷阱

目标: 理解 Unicode 的编码设计与文本处理中的反直觉问题。

内容要点: - UTF-8 的设计精妙之处： - 自同步（self-synchronizing）：从任意位置都能找到字符边界 - ASCII 兼容：7 位 ASCII 编码不变 - 前缀编码：无需前瞻即可确定字符长度 - 字典序保持：UTF-8 字节序 = Unicode 码点序 - Rob Pike 和 Ken Thompson 在餐巾纸上的设计 - 为什么 len("café") 这么难： - code point vs grapheme cluster - 组合字符（combining characters）：é = e + ́ - NFC vs NFD 规范化 - 大小写转换的陷阱： - 德语 ß → SS（一对多映射） - 土耳其语 I → ı（locale-dependent） - 字符串排序（Collation）： - Unicode Collation Algorithm (UCA) - 多级排序：L1 基本字母 → L2 重音 → L3 大小写 - ICU 库的 collation 实现 - 文本分割（Segmentation）： - grapheme cluster 边界（UAX #29） - 词边界和行断规则 - 为什么正则表达式的 . 匹配 Unicode 如此复杂 - 安全问题：Unicode 同形攻击（homograph attack）

代码/示例: C 实现 UTF-8 验证器 + grapheme cluster 分割，附反直觉测试用例集

系列五：概率数据结构与流式算法

30 · HyperLogLog：用 12KB 统计十亿基数

目标: 从概率直觉到精确数学，完全理解 HyperLogLog 的工作原理。

内容要点: - 基数估计问题：计算不同元素的数量，但内存远小于数据量 - 概率计数的直觉：哈希值前导零的最大数量 → 估计基数 - Flajolet-Martin 算法：最简单的概率计数器 - LogLog 改进：多桶取几何平均 - HyperLogLog：多桶取调和平均（harmonic mean） - 为什么调和平均比几何平均更好：对离群值不敏感 - m 个桶，每桶 log log U 位，标准误差 1.04/√m - 小基数修正：LinearCounting 切换策略 - 大基数修正：2^32 以上的偏差修正 - Redis PFCOUNT / PFADD / PFMERGE 源码分析： - 稠密表示 vs 稀疏表示 - 合并操作：取 max - HyperLogLog++ (Google 2013)： - 64 位哈希、稀疏表示、偏差修正表 - 实测精度：不同桶数下的相对误差曲线

代码/示例: C 实现 HyperLogLog（含稀疏/稠密切换），附精度 vs 空间曲线

SVG: HyperLogLog 的桶结构与前导零统计示意图

31 · Count-Min Sketch：流式频率估计的瑞士军刀

目标: 理解 CMS 的设计、误差界和优化变体。

内容要点: - 频率估计问题：估计元素 x 在数据流中出现的次数 - Count-Min Sketch 结构：d 行 × w 列的计数器矩阵 - 查询：d 行中取最小值 - 误差界：P[f̂(x) - f(x) > εN] < δ，需要 w = ⌈e/ε⌉, d = ⌈ln(1/δ)⌉ - 保守更新（Conservative Update）：只增加最小的计数器 - 实测误差降低 2-5× - Count-Mean-Min 变体：中位数取代最小值，减少过估计 - 与 Count Sketch 的区别：支持负频率，中位数估计 - 点查询（point query）vs 范围查询（range query） - CMS 在实际系统中的应用： - 网络流量监控：top-K 重流识别 - 搜索引擎：query 频率估计 - 数据库：近似 COUNT(DISTINCT) - 与 Heavy Hitters 算法的关系（联动已有 hh 文章）

代码/示例: C 实现 CMS（含保守更新），附误差率 vs 空间的实测曲线

32 · t-digest：分布式系统中的分位数估计

目标: 理解 t-digest 如何在合并友好的前提下实现高精度分位数估计。

内容要点: - 分位数估计问题：精确计算需要排序（O(n log n)），流式场景需要近似 - 简单方案的不足：等宽直方图精度差、等深直方图难合并 - q-digest：基于树的可合并分位数 sketch - t-digest（Ted Dunning 2019）的核心思想： - 用可变宽度的质心（centroid）表示数据分布 - 尾部（p50 附近）允许大质心，极端分位数（p99/p99.9）用小质心 - 压缩函数 δ(q) 控制质心大小：k1、k2、k3 三种变体 - 合并算法：两个 t-digest 的合并是 O(m) 的（m = 质心数） - 这就是为什么它在分布式系统中大受欢迎 - 在 P99 延迟监控中的应用： - Prometheus 的 histogram vs summary - 为什么 t-digest 比固定桶的 histogram 更适合尾部延迟 - Elasticsearch 的 percentiles 聚合就是 t-digest - 精度分析：不同质心数下的分位数误差

代码/示例: Go 实现 t-digest（含合并），附与精确排序的分位数误差对比

33 · 水塘抽样：未知大小数据流的公平抽样

目标: 从基础到高级变体，理解流式抽样的数学保证。

内容要点: - 问题定义：从未知大小的数据流中均匀抽取 k 个样本 - 单元素水塘抽样（k=1）：第 i 个元素以 1/i 概率替换当前样本 - 均匀性证明：归纳法 - 通用水塘抽样（k>1）：Vitter 的 Algorithm R - 前 k 个直接入池，第 i 个（i > k）以 k/i 概率替换随机位置 - 加权水塘抽样： - A-Res（Reservoir with Efraimidis-Spirakis）：按 u^(1/w) 排序取 top-k - 实现简洁且性能好 - 指数跳跃优化（reservoir with exponential jumps）： - 不需要对每个元素都生成随机数 - 期望只需 O(k(1 + ln(n/k))) 次随机数生成 - 分布式水塘抽样：多个 reducer 的结果如何合并 - 在 A/B 测试中的应用：在线流量抽样 - 在数据库中的应用：pg_stat_statements 的采样、TABLESAMPLE

代码/示例: Go 实现加权水塘抽样（A-Res）+ 指数跳跃优化，附均匀性验证

34 · MinHash 与 SimHash：海量文本的相似度检测

目标: 理解局部敏感哈希在相似度检测中的应用。

内容要点: - 集合相似度：Jaccard 系数 J(A,B) = |A∩B| / |A∪B| - MinHash 的核心定理：P[h_min(A) = h_min(B)] = J(A,B) - 直觉解释：随机排列中最小元素落在交集中的概率 - MinHash 签名：用 k 个不同哈希的 MinHash 组成签名向量 - Jaccard 估计：k 个位置中相等的比例 - 误差界：O(1/√k) - LSH 加速：band hashing 技术 - 将 k 个 MinHash 分成 b 个 band，每个 band r 行 - S 形碰撞概率曲线：调节 b 和 r 控制阈值 - SimHash（Charikar 2002）： - 适用于余弦相似度 - 随机超平面投影 → 0/1 位串 - 汉明距离 ≈ 角度距离 - Google 的网页去重系统：SimHash 的工业规模部署 - 海量指纹的汉明距离近邻搜索 - 多表策略 - 在抄袭检测、新闻去重、推荐系统中的应用

代码/示例: Python 实现 MinHash + LSH band hashing，附大规模文档去重测试

35 · 频率估计的理论极限：Space-Saving 与 Misra-Gries

目标: 从理论下界出发，统一理解频率估计算法家族。延伸已有 Heavy Hitters 文章。

内容要点: - 频率估计问题的形式化：ε-approximate frequency，ε-heavy hitters - 空间下界：Ω(1/ε) 个计数器是必需的（通信复杂度论证） - Misra-Gries（1982）算法： - k 个计数器，遇到新元素时所有计数器减 1 - 误差界：f̂(x) ≤ f(x) ≤ f̂(x) + n/(k+1) - 最古老的流式算法之一 - Space-Saving（Metwally 2005）算法： - Stream-Summary 数据结构：哈希表 + 双链表 - 替换最小计数元素，继承其计数 + 1 - 同时给出频率上界和下界 - 可以证明 top-k 的正确性 - Lossy Counting（Manku-Motwani 2002）：基于窗口的方案 - 三种算法的统一视角：它们在做同样的事情，只是实现策略不同 - 实测对比：精度、吞吐量、内存开销 - 工业应用：网络监控中的 heavy-hitter 检测

代码/示例: C 实现 Space-Saving（含 Stream-Summary），与 CMS 的精度对比

36 · 流式算法总论：亚线性空间的艺术

目标: 从通信复杂度建立流式算法的统一理论框架。

内容要点: - 数据流模型的形式化：cash register model、turnstile model - 通信复杂度与空间下界的联系： - 单向通信复杂度 → 单遍流式算法空间下界 - INDEX 问题的 Ω(n) 下界 - 矩与范数估计： - F0（不同元素数）：Flajolet-Martin → HyperLogLog - F1（元素总数）：精确计数器即可 - F2（二阶矩/自连接大小）：AMS Sketch（Alon-Matias-Szegedy） - 四独立哈希与方差分析 - Fp（p > 2）：Indyk 的 p-stable 分布方法 - L0 估计：不同元素数在 turnstile 模型下 - 线性 sketch 的概念：sketch 是线性映射，支持合并 - 这就是为什么 sketch 天然适合分布式计算 - 图的流式算法：连通性、生成树的半流式算法 - 流式算法的实践限制：多遍 vs 单遍、随机性需求 - 流式算法在现代基础设施中的位置：Flink/Kafka Streams 中的近似计算

代码/示例: C 实现 AMS Sketch（F2 估计），附理论误差 vs 实测误差对比

系列六：向量检索与高维搜索

37 · KD-tree：低维空间的分治之道

目标: 理解 KD-tree 在低维空间的优势和维度诅咒的量化边界。

内容要点: - 问题定义：k 近邻查询（k-NN）和范围查询 - KD-tree 的构建：交替选择维度分割，中位数切分 - 搜索算法：回溯剪枝的核心条件（当前最近距离 vs 到分割超平面的距离） - 期望搜索复杂度：O(n^{1-1/d}) 在均匀分布下 - 维度诅咒的量化：d > 10 后 KD-tree 退化为线性扫描 - 高维空间中”近”和”远”的距离差异趋近于零 - BBF（Best-Bin-First）近似搜索： - 限制回溯次数获得近似 k-NN - FLANN 库的实现 - PCL（Point Cloud Library）中的 KD-tree：3D 点云处理的核心 - 构建时间 vs 查询时间的 trade-off：在什么 n 和 d 下 KD-tree 优于暴力搜索 - 替代方案：Ball tree、VP-tree 在某些度量空间下更优

代码/示例: C 实现 KD-tree（含 BBF 近似搜索），附不同维度下的查询性能曲线

SVG: KD-tree 的二维空间分割图

38 · 局部敏感哈希（LSH）：高维近邻搜索的概率方法

目标: 深入理解 LSH 的理论框架和实际构造。

内容要点: - 精确最近邻在高维下的困境：所有已知方法的查询或空间是指数级 - (r, cr, p1, p2)-sensitive 哈希族的定义 - 距离 ≤ r 的点碰撞概率 ≥ p1 - 距离 > cr 的点碰撞概率 ≤ p2 - 放大引理：AND 构造（减少 false positive）和 OR 构造（减少 false negative） - 常见 LSH 族： - 汉明距离：随机坐标投影 - 余弦相似度：随机超平面（SimHash 就是） - 欧氏距离：随机投影 + 分桶（E2LSH） - Jaccard 相似度：MinHash - Multi-probe LSH：一次查询探测多个邻近桶 - 减少哈希表数量 3-10× - 查询时间与召回率的权衡曲线 - LSH 的局限性：参数选择困难、对距离分布敏感 - 与 HNSW、IVF-PQ 的对比：为什么图方法正在取代 LSH - Falconn 库的实现

代码/示例: C++ 实现余弦 LSH + multi-probe，附召回率-查询速度曲线

SVG: LSH 的桶碰撞概率 S 曲线图

39 · HNSW：图索引如何击败树索引

目标: 深入理解 HNSW 为什么在实际基准中表现最好。

内容要点: - 小世界网络理论（Milgram 实验）：高聚集 + 短路径 - NSW（Navigable Small World）图： - 构建：逐个插入，连接 M 个最近邻 - 搜索：贪心路由，期望 O(polylog n) 跳 - HNSW = Hierarchical NSW： - 多层图结构：每层是一个 NSW，密度指数递减 - 最上层稀疏（快速跳转），最下层稠密（精确搜索） - 层数分配：几何分布 P(layer = l) = 1/mL^l - 构建参数： - M：每个节点的连接数，影响搜索精度和构建速度 - efConstruction：构建时的 beam width - efSearch：查询时的 beam width - 距离计算加速：PQ 量化 + 重排序 - 为什么 HNSW 击败了 LSH 和树方法： - 图索引天然适应数据分布 - 多层跳跃 ≈ 跳表的思想 - hnswlib 源码分析：序列化、多线程构建 - 局限性：内存占用大、构建慢、不好更新

代码/示例: C++ 实现简化 HNSW，附 vs QPS 基准（sift1M 数据集）

SVG: HNSW 的多层图结构与搜索路径图

40 · 乘积量化（PQ）与 IVF-PQ：十亿向量的工业级检索

目标: 理解大规模向量检索的核心压缩技术。

内容要点: - 内存瓶颈：10 亿 × 128 维 × 4B = 512GB，装不进内存 - 乘积量化（Product Quantization）： - 将 D 维向量分成 M 个子空间 - 每个子空间独立 k-means 聚类（通常 k=256 → 1 byte） - D=128 维压缩为 M=8 bytes（64× 压缩比） - 非对称距离计算（ADC）：查询不量化，数据库量化 - 预计算查询到所有码字的距离表 - 查询时只需 M 次查表 + 加法 - IVF（Inverted File Index）： - 粗量化器将空间分成 nlist 个 Voronoi 区域 - 查询时只搜索 nprobe 个最近区域 - IVF-PQ 组合：IVF 过滤 + PQ 距离计算 - OPQ（Optimized Product Quantization）： - 旋转变换使子空间独立性更好 - 量化误差降低 10-30% - FAISS 源码剖析： - IndexIVFPQ 的训练、添加、搜索流程 - GPU 加速：距离计算批量 GEMM - 十亿级检索的完整 pipeline：粗排（IVF-PQ）→ 精排（重排序）

代码/示例: Python + FAISS 实现十亿级检索 pipeline，附 recall-QPS-memory 三维曲线

41 · ScaNN 与 DiskANN：Google 和 Microsoft 的向量检索之路

目标: 理解两大厂在向量检索上的前沿工作。

内容要点: - ScaNN（Google 2020）： - 各向异性量化（Anisotropic Quantization） - 关键洞察：内积搜索中，方向比距离更重要 - 量化损失函数中引入方向加权 - 与标准 PQ 的对比：recall 提升 5-10% - 两阶段搜索：tree-based 粗排 + 重排序 - DiskANN（Microsoft 2019）： - Vamana 图：从 random graph 开始的贪心构建 - SSD-friendly 设计：图节点对齐到磁盘扇区 - 只需 Nlog(N) 字节的 SSD 空间 + O(N) 内存 - 十亿级数据只需一台机器 - Fresh DiskANN（EMNLP 2021）：支持实时更新 - 与 HNSW + PQ 的对比： - 内存受限场景：DiskANN 胜出 - 纯内存场景：HNSW 仍然最快 - 向量检索系统架构趋势：hybrid（图索引 + 量化 + 磁盘）

代码/示例: 性能数据对比分析（基于公开 benchmark），Python 复现 Vamana 图构建

42 · 从零实现一个向量搜索引擎

目标: 综合项目——用 Rust 或 C++ 实现包含 HNSW + PQ + SIMD 的完整向量搜索引擎。

内容要点: - 系统架构设计：索引层、量化层、存储层、查询层 - 索引层：实现 HNSW - 多线程构建 - 序列化与反序列化 - 量化层：实现 PQ + OPQ - k-means 训练 - 编码与解码 - SIMD 加速： - 内积 / L2 距离的 SIMD 实现 - 距离查表的 SIMD 化 - 存储层： - mmap 文件布局 - 增量追加 - 查询层： - IVF 粗排 + HNSW 精排 - 后过滤（属性过滤） - 基准测试：与 FAISS / hnswlib / DiskANN 对比 - sift1M / gist1M 数据集 - 、QPS、内存占用、构建时间

代码/示例: 完整 Rust/C++ 项目（~2000 行核心代码）

系列七：图算法工程实践

43 · Dijkstra 与 A*：从优先队列实现到路径规划

目标: 从优先队列的选择到游戏 AI 的路径规划，全面理解最短路算法的工程面。

内容要点: - Dijkstra 算法回顾：贪心 + 松弛操作 - 优先队列的选择对性能的影响： - 二叉堆：O(m log n)，实现简单、缓存友好 - 斐波那契堆：O(m + n log n)，理论最优但常数因子大 - 配对堆（Pairing Heap）：实测通常最快 - 实测对比：稀疏图 vs 稠密图下三种堆的差异 - Dial 的桶队列：当边权是小整数时 O(m + nC) 方案 - 双向 Dijkstra：两头同时搜索，停止条件的正确性 - A* 算法：启发式引导的 Dijkstra - admissible heuristic：低估保证最优性 - consistent heuristic：单调性避免重复展开 - 欧氏距离启发式在地图中的应用 - JPS（Jump Point Search）：网格地图上的 A* 加速 - 跳跃规则减少展开节点数 10-100× - 游戏引擎（Unity、UE5）中的实际应用 - Contraction Hierarchies：预处理加速的道路网络最短路 - Google Maps / OSRM 的核心技术

代码/示例: C 实现 A* + JPS（含网格地图可视化），附三种堆的 Dijkstra 性能对比

SVG: A* 搜索的展开顺序 vs Dijkstra 的展开顺序对比图

44 · Bellman-Ford 与路由协议：负权边与 count-to-infinity

目标: 理解 Bellman-Ford 在网络路由中的实际应用和经典问题。

内容要点: - Bellman-Ford 算法：V-1 轮松弛，处理负权边 - 负环检测：第 V 轮还能松弛则存在负环 - SPFA（Shortest Path Faster Algorithm）：队列优化的 Bellman-Ford - 平均 O(m) 但最坏 O(nm) - “SPFA 已死”的讨论：构造最坏情况输入 - 距离向量路由协议（Distance Vector Routing）： - RIP（Routing Information Protocol）就是分布式 Bellman-Ford - 每个路由器维护距离向量，周期性交换 - count-to-infinity 问题： - 链路断开后的路由环路 - 为什么 Bellman-Ford 在分布式中收敛很慢 - 解决方案： - split horizon：不向来源方向通告路由 - poison reverse（毒性逆转）：向来源通告距离为 ∞ - 跳数限制（RIP 的 15 跳上限） - 为什么 OSPF（链路状态协议）逐渐取代 RIP - Johnson 算法：Bellman-Ford + Dijkstra 解决全源最短路（含负权）

代码/示例: Go 实现 Bellman-Ford + 模拟 RIP 路由协议的 count-to-infinity

SVG: count-to-infinity 的路由更新过程图

45 · 最小生成树：Kruskal 与 Prim 的工程权衡

目标: 深入 Union-Find 的优化，理解 MST 算法在网络设计中的实际应用。

内容要点: - MST 的定义与基本性质：切割性质（Cut Property） - Kruskal 算法：排序 + Union-Find - Union-Find 的两个关键优化： - 路径压缩（Path Compression） - 按秩合并（Union by Rank） - 反 Ackermann 函数 α(n) 的近乎常数复杂度 - Prim 算法：类 Dijkstra 的贪心生长 - 优先队列的选择影响（同 Dijkstra 分析） - Borůvka 算法：并行友好的 MST - 每轮各组件选最轻出边，并行度 O(n) - 在并行计算框架（MapReduce/Spark）中的优势 - 三种算法的适用场景： - 稀疏图：Kruskal - 稠密图：Prim - 并行环境：Borůvka - 实际应用： - 网络设计：最小成本连通网络 - 图像分割：Felzenszwalb-Huttenlocher（基于 MST） - 聚类：单链接层次聚类 = MST

代码/示例: C 实现 Union-Find（含路径压缩 + 按秩合并）+ Kruskal，附性能对比

SVG: Union-Find 的路径压缩前后对比图

46 · Tarjan 算法族：SCC、割点、桥的统一框架

目标: 理解 DFS 树的深刻性质和 Tarjan 系列算法的统一视角。

内容要点: - DFS 树的四种边：树边、回边、前向边、交叉边 - 无向图只有树边和回边 - Tarjan 的 SCC 算法（强连通分量）： - low-link 值的定义与维护 - 栈的作用：识别 SCC 的根节点 - 线性时间 O(V + E) - Kosaraju 的 SCC 算法：两次 DFS - 与 Tarjan 的对比：Kosaraju 更直观但需要反向图 - 割点（Articulation Point）算法： - low[u] ≥ disc[v] 的判定条件 - 特殊情况：根节点的判定 - 桥（Bridge）算法： - low[v] > disc[u] 的判定条件 - 与割点算法的微妙差异 - SCC 在依赖分析中的应用： - 包管理器的循环依赖检测（Go modules、npm） - 编译器的强连通分量优化 - 2-SAT 问题：利用 SCC 的高效求解

代码/示例: C 实现 Tarjan SCC + 割点 + 桥（统一框架），附依赖图分析示例

SVG: DFS 树的 low-link 计算过程图

47 · 网络流与二分匹配：从最大流到最小割

目标: 理解网络流的核心算法和建模能力。

内容要点: - 网络流基础：流、容量、增广路径 - Ford-Fulkerson 方法：反复找增广路径 - 反向边的精妙设计：允许”撤销”之前的流 - 无理数容量时可能不终止 - Edmonds-Karp 算法：BFS 找最短增广路径，O(VE^2) - Dinic 算法： - 层级图（Level Graph）+ 阻塞流（Blocking Flow） - O(V^2 E)，单位容量图 O(E√V) - 为什么 Dinic 在实践中通常最快 - Push-relabel 算法： - 局部操作（push/relabel），避免全图 BFS - O(V^2 √E)，适合稠密图 - 最高标号启发式（highest-label） - 最大流最小割定理（Max-flow Min-cut）：对偶性的经典 - König 定理：二分图最大匹配 = 最小点覆盖 - 二分匹配：匈牙利算法 / Hopcroft-Karp - 应用实例： - 任务调度：将分配问题建模为二分匹配 - 图像分割：graph cuts 最小割 - 棒球淘汰问题：经典的最大流建模

代码/示例: C 实现 Dinic 算法 + 匈牙利算法，附任务分配建模示例

SVG: 残余图与增广路径的迭代过程图

48 · 拓扑排序：依赖解析的核心

目标: 从算法到构建系统，理解拓扑排序的工程价值。

内容要点: - DAG（有向无环图）与拓扑序的关系 - 两种实现： - Kahn 算法（BFS）：维护入度为 0 的队列 - DFS 后序翻转：finish time 的逆序 - 拓扑排序的唯一性：当且仅当存在哈密顿路径 - 增量拓扑排序：动态添加边时如何维护拓扑序 - MNR（Marchetti-Spaccamela et al.）算法 - 在 IDE 的增量编译中的应用 - 在构建系统中的应用： - Make 的依赖图就是拓扑排序 - Bazel/Buck2 的并行构建：拓扑排序确定并行度 - 关键路径（Critical Path）分析 - 在包管理器中的应用： - npm/pip 的安装顺序 - 循环依赖检测（与 SCC 联动） - 课程选修问题：经典的建模与求解 - 字典序最小的拓扑排序：优先队列替换普通队列

代码/示例: Go 实现 Kahn 算法 + 增量拓扑排序，附构建系统并行度分析

49 · PageRank 与随机游走：搜索引擎的数学基础

目标: 深入理解 PageRank 的数学模型和大规模计算方法。

内容要点: - 网页重要性的直觉：被重要网页引用的网页更重要（递归定义） - PageRank 的数学模型： - 转移矩阵 M：Mij = 1/out(j) if j→i - 阻尼因子（damping factor）d = 0.85：随机跳转防止悬挂节点 - PageRank 向量是 M’ 的主特征向量 - Markov 链视角： - 随机游走的平稳分布 - 遍历性条件：不可约 + 非周期 - 阻尼因子保证了遍历性 - 幂迭代法：最简单的计算方法 - 收敛速度取决于第二大特征值 - 典型 20-50 次迭代收敛 - 大规模计算： - MapReduce 实现：每轮一次 map + reduce - 稀疏矩阵存储：只存非零元素 - 收敛检测：L1 范数变化量 - Personalized PageRank (PPR)：个性化推荐 - 从特定节点出发的随机游走 - 在社交网络推荐中的应用 - HITS（Hyperlink-Induced Topic Search）：权威度与枢纽度

代码/示例: Go 实现 PageRank（幂迭代 + MapReduce 模拟），附在真实网页图上的实验

50 · 图着色与 NP-hard 近似：从寄存器分配到调度

目标: 理解图着色的理论难度和工程中的近似策略。

内容要点: - 图着色问题：用最少颜色数（色数 χ(G)）为顶点着色使相邻顶点不同色 - NP-hard 性：3 着色判定已是 NP-complete - 贪心着色：按顺序给顶点着色，使用最小可用颜色 - 不超过 Δ+1 种颜色（Δ 是最大度数） - 顶点排序策略的影响 - DSatur 算法（Degree of Saturation）： - 优先着色”约束最多”的顶点 - 实测接近最优的启发式 - Brook 定理：χ(G) ≤ Δ(G)（除了完全图和奇环） - 在寄存器分配中的应用： - 干涉图（Interference Graph）：两个活跃变量同时存在则连边 - 色数 = 所需寄存器数 - Chaitin 的图着色寄存器分配（联动系列十六） - LLVM 的寄存器分配策略 - 在调度中的应用： - 考试排程：课程冲突图着色 - 频谱分配：无线信道分配 - 编译器的指令调度 - 平面图的四色定理：计算机辅助证明的里程碑

代码/示例: C 实现 DSatur 图着色 + 简化寄存器分配器，附着色质量对比

SVG: 干涉图与着色结果对比图

系列八：操作系统中的算法

51 · 内存分配器对决：jemalloc vs tcmalloc vs mimalloc

目标: 深入理解三大用户态内存分配器的设计决策。与 post/linux/ 联动。

内容要点: - 为什么 glibc malloc（ptmalloc2）不够好：锁争用、碎片化 - 通用内存分配器的设计目标：速度、碎片率、多线程扩展性、内存占用 - jemalloc（Jason Evans, FreeBSD/Firefox/Redis）： - size class 设计：small（8-14336B）、large（> 14336B） - arena：多 arena 减少锁争用 - tcache（thread cache）：线程本地缓存 - extent：虚拟地址空间管理 - slab allocator 管理小对象 - tcmalloc（Google）： - thread cache → central cache → page heap 三级结构 - span 管理：连续页面的分配与回收 - size class 的选择与对齐策略 - 从 gperftools tcmalloc 到新 tcmalloc 的演进 - mimalloc（Microsoft/Daan Leijen）： - 极简设计：segment → page → block - 空闲链表的局部性优化 - 为什么 benchmark 表现常常最好 - 量化对比（真实工作负载）： - Redis、Nginx、RocksDB 下的吞吐与内存占用 - 碎片率对比 - 多线程扩展性曲线 - Rust 的全局分配器接口：如何替换默认分配器

代码/示例: Rust 程序分别使用三种分配器的 benchmark，附 perf 分析

52 · 页面置换算法：LRU 的谎言与 ARC 的真相

目标: 揭示教科书 LRU 在实际中的问题，理解自适应算法的优势。

内容要点: - 页面置换问题：物理内存有限，需要决定淘汰哪个页面 - Bélády 的最优算法（OPT）：淘汰未来最久不用的页面（离线最优） - FIFO：简单但 Bélády 异常（更多页框反而更多缺页） - LRU 的理论优美性：stack algorithm，无 Bélády 异常 - LRU 在实际中的问题： - 精确 LRU 需要每次访问更新时间戳（开销大） - 顺序扫描污染：一次全表扫描会冲走所有热数据 - CLOCK 算法（近似 LRU）： - 引用位 + 时钟指针，O(1) 决策 - Linux 内核的二次机会法 - Linux 的 active/inactive 双链表： - 两个 LRU 链表的晋升/降级策略 - 为什么不用纯 LRU - ARC（Adaptive Replacement Cache，IBM 2003）： - 4 个链表：T1（最近访问）、T2（频繁访问）、B1（T1 的影子）、B2（T2 的影子） - 自适应参数 p：根据 B1/B2 的命中情况动态调整 T1/T2 的大小 - 为什么 ARC 能同时应对 recency 和 frequency 工作负载 - LIRS（Low Inter-reference Recency Set）：另一个自适应方案 - 实测对比：不同访问模式下各算法的命中率

代码/示例: C 实现 CLOCK / LRU / ARC，附 trace-driven 模拟的命中率对比

SVG: ARC 的四链表结构与自适应参数调整图

53 · 进程调度：从 CFS 到 EEVDF 的哲学演变

目标: 深入内核源码理解 Linux 调度器的设计演变。

内容要点: - 调度器的核心矛盾：公平性 vs 交互性 vs 吞吐量 - O(1) 调度器（Linux 2.6 早期）： - 140 个优先级的位图 + 活跃/过期双数组 - 启发式交互性检测的问题 - CFS（Completely Fair Scheduler，Linux 2.6.23+）： - 虚拟运行时间（vruntime）：所有任务获得公平的 CPU 时间 - 红黑树：按 vruntime 排序，O(log n) 选择最小 vruntime - nice 值 → 权重的映射：nice 差 1 ≈ CPU 份额差 10% - 调度延迟（sched_latency_ns）与最小粒度（sched_min_granularity_ns） - 组调度：cgroup 的 CPU 控制 - EEVDF（Earliest Eligible Virtual Deadline First，Linux 6.6+）： - 虚拟截止时间（virtual deadline）= eligible time + slice/weight - 解决 CFS 的延迟公平性问题：CFS 只保证长期公平，EEVDF 保证短期也公平 - 与 EDF（Earliest Deadline First）的关系和区别 - 实时调度：SCHED_FIFO、SCHED_RR、SCHED_DEADLINE - EDF 在实时调度中的应用 - CBS（Constant Bandwidth Server）

代码/示例: C 模拟 CFS 和 EEVDF 调度策略，附公平性和延迟指标对比

SVG: CFS 红黑树与 EEVDF 的调度决策对比图

54 · I/O 调度：CFQ → mq-deadline → BFQ → kyber

目标: 理解 I/O 调度器的设计演变，以及 NVMe 时代为什么调度器在简化。

内容要点: - I/O 调度的目标：最大化吞吐、最小化延迟、保证公平 - 单队列时代（Linux < 3.13）： - Noop（直通，不排序） - Deadline：读写分开的截止时间保证 - CFQ（Complete Fairness Queueing）： - 按进程分队列、时间片轮转 - 预期调度（anticipatory scheduling） - 为什么 CFQ 对 HDD 表现好但对 SSD 不好 - 多队列时代（Linux 3.13+ blk-mq）： - 为什么需要多队列：NVMe 设备有多个硬件队列 - mq-deadline：deadline 的多队列适配 - BFQ（Budget Fair Queueing）： - 基于预算的公平调度 - 保证交互延迟：IO 密集程序不饿死桌面应用 - 在 Android 上的应用 - kyber：超轻量级令牌桶 - 只区分读/写两类 - 用延迟反馈控制令牌数量 - 为什么适合 NVMe - none 调度器：NVMe 时代的默认选择 - NVMe 设备自身有调度能力，软件调度反而增加延迟 - 实测：HDD vs SATA SSD vs NVMe 下不同调度器的 IOPS/延迟

代码/示例: fio 基准测试脚本，不同调度器 × 不同设备类型的性能矩阵

55 · 伙伴系统与 SLUB 分配器：Linux 物理内存管理

目标: 从物理页面分配到小对象管理，理解 Linux 内存管理的两层架构。

内容要点: - 伙伴系统（Buddy System）： - 2^n 页面分割与合并 - free_area[MAX_ORDER] 的 11 个链表（4KB → 4MB） - 分配：找最小满足的 order，多余的部分拆分为伙伴 - 释放：检查伙伴是否空闲，合并升级 - 外部碎片问题与反碎片化（migrate type：UNMOVABLE/MOVABLE/RECLAIMABLE） - SLUB 分配器（Linux 默认，替代 SLAB）： - 目标：高效分配小于一页的对象（kmalloc） - kmem_cache：为每种大小创建专用缓存 - per-cpu partial list：减少跨 CPU 竞争 - freelist 嵌入对象内部：零额外空间开销 - SLUB 的调试特性：红色区域、毒药填充 - SLAB vs SLUB vs SLOB 的对比： - SLAB：经典但复杂 - SLUB：简化、可扩展、是默认 - SLOB：嵌入式系统用的最小实现 - kmalloc 源码追踪：从用户调用到物理页面分配的完整路径 - /proc/slabinfo 与 slabtop 的解读

代码/示例: 内核模块演示 kmalloc 路径追踪，附 slabtop 输出分析

56 · 文件系统的树：ext4 extent tree 到 btrfs CoW B-tree

目标: 理解不同文件系统如何用树结构组织元数据。与 post/db/ 联动。

内容要点: - 文件系统元数据的组织需求：目录索引、文件块映射、空间管理 - ext4 的 extent tree： - 从间接块到 extent：减少大文件的元数据量 - extent 结构：(逻辑块号, 物理块号, 长度) - HTree 目录索引：哈希树加速目录查找 - XFS 的 B+tree： - 几乎所有元数据都用 B+tree 管理 - 分配组（Allocation Group）的并行性设计 - 延迟分配（Delayed Allocation） - btrfs 的 CoW B-tree： - 所有写入都是 Copy-on-Write - CoW B-tree 的空间代价：写入一个叶子需要复制整条路径 - 引用计数与快照的实现 - extent tree 管理空间引用 - ZFS 的 DMU（Data Management Unit）： - 类似 btrfs 的 CoW 策略 - 256 位校验和与自修复 - 性能对比：ext4 vs XFS vs btrfs 在不同工作负载下

代码/示例: 用 debugfs/xfs_db 观察真实文件系统的树结构，附元数据布局分析

SVG: ext4 extent tree vs btrfs CoW B-tree 的对比图

57 · epoll 的数据结构：红黑树、就绪队列与回调机制

目标: 从源码级理解 epoll 的三大内部数据结构。与 post/ioevent/ 联动。

内容要点: - epoll 的三大组件： - 红黑树：管理所有被监控的 fd（epoll_ctl ADD/MOD/DEL） - 就绪链表（rdllist）：存放已触发事件的 fd - 等待队列（wq）：epoll_wait 的阻塞进程 - 红黑树的使用： - key = fd + file pointer - O(log n) 的 ADD/DEL/MOD - 为什么不用哈希表：需要有序遍历（某些内部操作） - 事件触发的回调机制： - ep_poll_callback：设备驱动通过 waitqueue 回调 - 回调将 epitem 挂到就绪链表 - epoll_wait 只需检查就绪链表是否为空 - LT vs ET 的实现差异： - LT（Level Triggered）：事件未处理完会重新加入就绪链表 - ET（Edge Triggered）：只通知一次，需用户确保读完 - 实现细节：LT 在 epoll_wait 返回前将未完成的 epitem 重新排队 - epoll 的惊群问题： - 多线程 epoll_wait 同一 epfd - EPOLLEXCLUSIVE 的解决方案（Linux 4.5+） - epoll vs io_uring 的架构对比

代码/示例: C 演示 LT vs ET 行为差异 + strace 追踪 epoll 内核调用

SVG: epoll 的红黑树 + 就绪链表 + 回调路径图

58 · 定时器算法：时间轮、最小堆与层级时间轮

目标: 理解不同定时器数据结构的设计权衡。

内容要点: - 定时器的基本操作：添加、删除、获取最近到期 - 排序链表：O(n) 插入、O(1) 获取到期 — 定时器少时可用 - 最小堆（Min-Heap）： - O(log n) 插入/删除、O(1) 获取最小 - Go runtime 的定时器：从全局 4 叉堆到 per-P 4 叉堆的演进 - 为什么用 4 叉堆不用二叉堆：缓存友好性 - 简单时间轮（Simple Timing Wheel）： - 固定大小的环形数组，每个槽位一个链表 - O(1) 插入/删除/到期触发 - 缺点：只能处理固定范围内的定时器 - 层级时间轮（Hierarchical Timing Wheel）： - 类比时钟：秒针轮 + 分针轮 + 时针轮 - Linux 内核的 timer_list 实现：tv1-tv5 五级时间轮 - tv1：256 个槽（jiffies 精度） - tv2-tv5：64 个槽（逐级扩大范围） - cascade：低级轮处理完后从高级轮拉取 - O(1) 插入和到期触发 - Netty 的 HashedWheelTimer：Java 网络框架的选择 - 单层时间轮 + tick 精度权衡 - 为什么选单层不选层级：实现简单、IO 超时精度够用 - 精度 vs 开销的 trade-off：不同场景的选型指南

代码/示例: C 实现层级时间轮（Linux 风格），附不同定时器数量下的性能对比

SVG: 层级时间轮的多级结构与 cascade 过程图

系列九：数据库核心算法

59 · Join 算法全解：Nested Loop → Hash Join → Sort-Merge Join

目标: 从成本模型出发全面理解数据库 Join 的物理实现。与 post/db/ 联动。

内容要点: - Nested Loop Join： - Simple NLJ：O(|R| × |S|) — 暴力双循环 - Block NLJ：利用缓冲区减少 I/O - Index NLJ：内表有索引时 O(|R| × log|S|) - Sort-Merge Join： - 两表排序后归并，O(|R|log|R| + |S|log|S| + |R| + |S|) - 天然支持范围 Join（<, >, BETWEEN） - 排序结果可复用（如果后续有 ORDER BY） - Hash Join： - Classic Hash Join：Build 阶段构建哈希表 + Probe 阶段探测 - Grace Hash Join：当内存不够时分区写磁盘 - partition fan-out 的选择：决定 I/O 次数 - Hybrid Hash Join：部分分区留在内存 - Vectorized Hash Join（现代分析引擎）： - DuckDB/Velox 的批量探测 - SIMD 加速的哈希表探测 - Parallel Hash Join： - 分区并行（partition-based）：每个线程处理不同分区 - 共享哈希表（shared hash table）：原子 CAS 插入 - 成本模型对比：哪种 Join 在什么场景下最优 - 小表 Join 大表：Index NLJ 或 Hash Join - 两张大表 Join：Grace Hash Join 或 Sort-Merge - 已经排好序的数据：Sort-Merge - 查询优化器如何选择 Join 方法

代码/示例: C 实现三种 Join 算法，附不同数据规模/选择率下的 I/O 次数对比

SVG: Grace Hash Join 的分区与探测流程图

60 · 查询优化器：从 System R 到现代 Cascades

目标: 理解关系数据库查询优化的核心算法。

内容要点: - 查询优化的重要性：同一查询的不同执行计划可以差 1000× - System R 优化器（Selinger 1979）： - 动态规划枚举 Join 顺序 - 只考虑 left-deep plan - 有趣的排序（interesting orders）：传播排序属性减少重复排序 - 代价模型：I/O cost + CPU cost - 统计信息收集： - 直方图（等宽、等深、most-common-values） - 选择率估计：基于统计信息预估结果行数 - 相关性问题：独立性假设的局限 - Volcano/Cascades 优化框架（Graefe）： - 规则驱动的变换（transformation rules） - memo 结构：等价类的高效管理 - 分支定界搜索：提前剪枝差的计划 - 物理属性（physical properties）的传播 - 现代优化器的挑战： - Join 数量增加时搜索空间爆炸（12 表 Join = 4× 10^10 种顺序） - 自适应查询执行（Adaptive Query Execution）：运行时切换计划 - Learned Optimizer：用 ML 替代代价模型

代码/示例: Python 实现简化版 Selinger DP 优化器（3-4 表 Join），附执行计划可视化

61 · 缓冲池管理算法：LRU-K → 2Q → CLOCK-Pro

目标: 理解数据库缓冲池特有的页面置换需求。与系列八 52 篇互补。

内容要点: - 数据库缓冲池 vs OS 页面缓存的区别： - 数据库了解访问模式（知道哪些是顺序扫描） - 数据库可以使用 double-write 等策略 - 数据库需要脏页刷写策略 - LRU 在数据库中的问题：顺序扫描污染 - LRU-K（O’Neil 1993）： - 记录最近 K 次访问的时间戳 - 淘汰倒数第 K 次访问最久远的页面 - K=2 在实践中最常用 - 2Q（Two-Queue）： - A1in（FIFO 短期缓冲）+ Am（LRU 长期缓冲） - 只被访问一次的页面不进入 Am - 防止全表扫描污染 - CLOCK-Pro（Jiang 2005）： - CLOCK 的改进版：区分冷热页面 - 类似 ARC 的自适应，但基于 CLOCK（O(1) 开销） - MySQL InnoDB 的 young/old 双区： - buffer pool 分为 young 和 old 两区 - old 区的 “time window” 防止扫描污染 - 预取策略（Prefetching）： - 线性预读（linear read-ahead） - 随机预读（random read-ahead） - 预取对命中率的影响

代码/示例: C 实现 LRU-K 和 2Q，附数据库 trace-driven 的命中率对比

62 · WAL 与 ARIES 恢复算法：崩溃恢复的数学保证

目标: 深入理解数据库崩溃恢复的理论与 ARIES 算法的完整流程。

内容要点: - 为什么需要恢复算法：事务的 ACID 中 D（Durability）的保证 - WAL（Write-Ahead Logging）协议： - 修改数据前先写日志 - 事务提交 = 日志刷到磁盘 - LSN（Log Sequence Number）的单调性 - Steal vs No-Steal × Force vs No-Force 矩阵： - ARIES 工作在 Steal + No-Force 模式（性能最好但恢复最复杂） - ARIES 算法（Mohan 1992）的三个阶段： - 分析阶段（Analysis）：从最近 checkpoint 扫描日志，重建脏页表和活跃事务表 - 重做阶段（Redo）：从脏页表中最小 LSN 开始，重做所有操作 - 撤销阶段（Undo）：回滚所有未提交事务 - Checkpoint 策略： - 模糊检查点（Fuzzy Checkpoint）：不暂停事务 - Checkpoint 写什么：脏页表 + 活跃事务表 - CLR（Compensation Log Record）：undo 操作也要写日志 - 为什么：undo 过程中再次崩溃需要能继续 - 逻辑日志 vs 物理日志 vs 物理逻辑日志（physiological logging） - SQLite 的 WAL 模式：更简单的实现（读写分离） - PostgreSQL 的 WAL 实现：full page writes 的策略

代码/示例: Go 实现简化 WAL + ARIES 三阶段恢复，附崩溃模拟测试

SVG: ARIES 三阶段恢复的时间线图

63 · LSM-tree Compaction 策略：Leveled vs Tiered vs FIFO vs Universal

目标: 深入理解不同 compaction 策略的写放大、读放大和空间放大特征。

内容要点: - LSM-tree 的写路径回顾：MemTable → Immutable MemTable → SSTable（L0）→ Compaction → L1 → L2 → … - Leveled Compaction（RocksDB 默认）： - 每层大小比 T（默认 10） - 写放大：O(T × L)（L = 层数） - 读放大：每层最多一次 I/O - 空间放大：约 1.1× - Tiered Compaction（Cassandra 默认/RocksDB Universal）： - 每层有多个 run，满了一起合并到下一层 - 写放大：O(L)（远低于 Leveled） - 读放大：每层可能需要检查多个 run - 空间放大：最坏 2× - FIFO Compaction： - 按时间淘汰最旧的 SSTable - 适用于时序数据（只保留最近 N 天） - 写放大 = 1（最小） - RocksDB 的 Compaction 调优： - compaction 的 CPU / I/O 优先级 - 后台线程数的选择 - tombstone 累积问题：删除标记什么时候被真正清理 - 写放大的精确计算（RocksDB 的公式推导） - Dostoevsky（Harvard DASlab 2018）：Lazy Leveling 的最优设计 - SILK（USENIX ATC 2019）：优先级感知的 compaction 调度

代码/示例: Go 模拟不同 compaction 策略，附写放大/读放大/空间放大的量化对比

SVG: Leveled vs Tiered compaction 的层级结构对比图

64 · MVCC 实现变体全解：追加式 vs 就地更新 vs delta 存储

目标: 对比不同数据库的 MVCC 实现策略。与 post/db/mvcc 联动。

内容要点: - MVCC 回顾：通过多版本实现读写不阻塞 - 追加式（Append-Only）：PostgreSQL 的方式 - 每次 UPDATE 创建新 tuple 版本 - 老版本通过 t_ctid 链表链接 - 优点：写入是顺序追加 - 缺点：表膨胀（table bloat），需要 VACUUM 清理 - VACUUM 的工作原理与代价 - 就地更新（In-Place Update）：MySQL InnoDB 的方式 - 在原位修改数据，老版本存入 Undo Log - 通过 roll pointer 链接版本链 - 优点：热数据的物理位置稳定 - 缺点：Undo Log 的管理复杂 - Delta 存储：Oracle / HyPer 的方式 - 只存储与前一版本的差异（delta） - 空间效率最高 - 但重建旧版本需要遍历 delta 链 - GC（垃圾回收）策略： - 后台 GC vs 合作式 GC - epoch-based GC vs transaction-based GC - 长事务的灾难：阻止 GC 导致版本累积 - 快照隔离（Snapshot Isolation）的实现： - 时间戳 vs 事务 ID - 全局快照管理的开销 - Write Skew 问题与 SSI（Serializable Snapshot Isolation）

代码/示例: Go 实现简化的追加式 MVCC + 就地更新 MVCC，附写放大和查询延迟对比

65 · 学习索引：当机器学习遇上数据库

目标: 客观评价 Learned Index 的理论创新和实际局限。

内容要点: - The Case for Learned Index Structures（Kraska 2018）：开创性论文 - 核心洞察：索引本质上是从 key 到 position 的函数 - 如果数据分布已知，可以用模型直接预测位置 - RMI（Recursive Model Index）： - 层级模型：第一层粗定位，第二层精确定位 - 线性回归 / 神经网络作为子模型 - 误差界保证：last-mile search 用二分查找 - PGM-index（Ferragina & Vinciguerra 2020）： - 分段线性近似（Piecewise Linear Approximation） - 最优分段数量的理论保证 - 空间远小于 B-tree（实测 10-100× 节省） - CDFShop：自动选择最优 CDF 近似策略 - ALEX：可更新的学习索引 - 支持插入和删除 - Gapped Array + 自适应节点分裂 - 现实检验： - Learned Index 的假设条件：数据近似有序、分布稳定 - 并发控制的困难：模型更新的线程安全 - 与 B-tree 的公平对比（Martin Boissier 2022） - 为什么主流数据库没有采用 Learned Index - Learned Index 的未来方向：多维学习索引、写优化学习索引

代码/示例: Python 实现 PGM-index，附与 B-tree 在不同数据分布下的查询性能对比

系列十：网络协议中的算法

66 · TCP 拥塞控制：从 Reno 到 BBRv3 的进化之路

目标: 从公平性理论到实际部署，全面理解拥塞控制的演进。与 post/network/ 联动。

内容要点: - 拥塞控制的核心问题：多个发送方共享瓶颈链路 - TCP Tahoe & Reno： - 慢启动 → 拥塞避免 → 快速重传 → 快速恢复 - AIMD（Additive Increase Multiplicative Decrease）的公平性证明 - CUBIC（Linux 默认，RFC 9438）： - 三次函数取代线性增长 - 与 Reno 在高 BDP 链路上的对比 - Wmax 的记忆与 HyStart 慢启动改进 - BBR（Bottleneck Bandwidth and Round-trip propagation time）： - 从丢包驱动到带宽-延迟模型 - 四个状态：Startup → Drain → ProbeBW → ProbeRTT - BBR 的带宽探测：发送速率周期性变化 - BBRv2 的改进：减少对丢包的过度反应 - BBRv3 的改进：更好的公平性和与 CUBIC 的共存 - 拥塞控制的公平性分析： - intra-protocol fairness：同算法之间 - inter-protocol fairness：BBR vs CUBIC 共存问题 - QUIC 中的拥塞控制：应用层实现的灵活性 - 数据中心网络：DCTCP、HPCC

代码/示例: Python 模拟 CUBIC vs BBR 在不同网络条件下的窗口变化，附吞吐-延迟曲线

SVG: BBR 状态机与带宽探测示意图

67 · 滑动窗口与流控的算法本质

目标: 理解滑动窗口协议的一般性算法框架。

内容要点: - 滑动窗口的抽象模型：发送方维护 [SND.UNA, SND.NXT, SND.UNA + SND.WND) - 环形缓冲区实现：head/tail 指针的移动 - 为什么用取模运算：空间重用 - TCP 序列号的 32 位回绕处理 - 接收窗口的通告： - rwnd 的计算：接收缓冲区剩余空间 - 零窗口问题：发送方如何探测窗口恢复 - persist timer 与 zero-window probe - TCP receive window auto-tuning： - Linux 的自动调整策略：根据 RTT 和可用内存动态扩大 - tcp_rmem 参数的含义 - 窗口缩放选项（Window Scale Option）：突破 64KB 限制 - Nagle 算法与延迟 ACK 的交互： - Nagle 算法减少小包 - 延迟 ACK 减少 ACK 频率 - 两者组合导致的延迟问题 - 滑动窗口在其他协议中的应用： - Go-Back-N vs Selective Repeat - QUIC 的流控：per-stream + connection-level 双层窗口

代码/示例: C 实现通用滑动窗口协议（Go-Back-N + Selective Repeat），附吞吐量对比

SVG: 滑动窗口的发送方/接收方状态图

68 · 限流算法：令牌桶 / 漏桶 / 滑动窗口 / GCRA

目标: 深入理解四种限流算法的等价关系和工程选型。

内容要点: - 限流的目的：保护下游服务、公平共享资源 - 固定窗口计数器： - 最简单：每个时间窗口一个计数器 - 窗口边界问题：两个窗口交界处可能 2× 突发 - 滑动窗口计数器： - 加权平均两个窗口的计数 - 空间 O(1)，但是近似的 - 滑动窗口日志： - 精确记录每次请求的时间戳 - 空间 O(rate)，精确但内存高 - 漏桶（Leaky Bucket）： - 固定速率输出，突发请求排队 - 实现：FIFO 队列 + 固定速率消费 - 缺点：不允许任何突发 - 令牌桶（Token Bucket）： - 固定速率添加令牌，桶有容量上限 - 允许受限突发（burst = 桶容量） - Linux tc 的 tbf 实现 - GCRA（Generic Cell Rate Algorithm）： - ATM 网络的速率控制算法 - 与令牌桶等价但实现更简洁：只需一个 TAT（Theoretical Arrival Time）值 - 一行代码的核心逻辑 - 分布式限流： - 本地限流 + 全局配额同步 - Redis + Lua 脚本实现 - Envoy 的 rate limiting service - 精确度 vs 内存 vs 延迟的 trade-off

代码/示例: Go 实现令牌桶 + GCRA + 滑动窗口，附突发流量下的行为对比

SVG: 令牌桶与 GCRA 的等价关系图

69 · 负载均衡算法：加权轮询 / 最少连接 / P2C / EWMA

目标: 从理论到生产，理解负载均衡算法的设计权衡。

内容要点: - 轮询（Round Robin）与加权轮询： - Nginx 的 smooth weighted round-robin： - 避免权重不均匀时的请求聚集 - 每轮选择 currentWeight 最大的节点 - currentWeight += effectiveWeight, 选中后 -= totalWeight - 随机与加权随机： - 最简实现，无状态 - 但随机性导致短期不均匀 - 最少连接（Least Connections）： - 选择活跃连接数最少的后端 - 加权最少连接：connections / weight - 需要维护连接计数状态 - P2C（Power of Two Choices）： - 随机选两个候选，取负载小的 - Mitzenmacher 的论文：指数级降低最大负载 - 从 O(log n / log log n) 到 O(log log n) - gRPC 的默认策略就是 P2C - EWMA（Exponentially Weighted Moving Average）： - 用指数移动平均估计后端延迟 - P2C + EWMA 组合：Envoy/Linkerd 的实现 - 衰减因子的选择：响应性 vs 稳定性 - 一致性哈希负载均衡（联动系列二 11 篇） - 自适应负载均衡：根据实时反馈调整策略

代码/示例: Go 实现 Smooth WRR / P2C / EWMA，附模拟流量下的负载均匀性对比

70 · 路由算法：距离向量 vs 链路状态 vs 路径向量

目标: 系统对比三类路由算法的设计哲学。联动 44 篇。

内容要点: - 距离向量（Distance Vector）： - 每个节点只知道邻居的距离，通过交换收敛 - Bellman-Ford 的分布式版本 - RIP 协议的实现 - 收敛慢、count-to-infinity 问题（联动 44 篇） - 链路状态（Link State）： - 每个节点泛洪（flood）自己的链路状态 - 每个节点拥有完整拓扑，独立运行 Dijkstra - OSPF 协议： - Hello 协议维护邻居关系 - LSA（Link State Advertisement）泛洪 - SPF 计算：Dijkstra 找最短路 - Area 划分减少拓扑规模 - 路径向量（Path Vector）： - BGP 协议的路由方式 - 传播完整 AS 路径，避免环路 - 策略路由：不只是最短路径，还考虑商业关系 - BGP 的安全问题：路由劫持、RPKI - 三类算法的对比： - 收敛速度：链路状态 > 路径向量 > 距离向量 - 扩展性：路径向量（BGP 管理 100 万+ 前缀） - 资源开销：距离向量最小

代码/示例: Go 模拟三种路由协议在 10 节点网络上的收敛过程

SVG: OSPF 的 LSA 泛洪与 SPF 计算过程图

71 · 主动队列管理：RED → CoDel → FQ-CoDel → CAKE

目标: 理解 bufferbloat 问题和现代 AQM 算法的设计。

内容要点: - bufferbloat 问题： - 网络设备缓冲区过大导致延迟飙升 - 典型场景：家用路由器的 100ms → 1000ms+ 延迟 - 测量：speedtest 吞吐高但 ping 高 - 为什么 tail-drop 不好：全局同步、不公平 - RED（Random Early Detection，1993）： - 基于平均队列长度的概率丢包 - 参数调优困难（min_th、max_th、max_p） - 为什么 RED 在实践中效果不好 - CoDel（Controlled Delay，2012）： - 核心思想：sojourn time（包在队列中的驻留时间） - 不看队列长度，看延迟！ - 目标延迟 5ms，间隔 100ms - 当 sojourn time 持续超过 target：开始丢包 - 丢包速率用 1/√count 控制 - 无参数调优需求（这是革命性的） - FQ-CoDel（Fair Queuing + CoDel）： - 多个子队列（默认 1024）+ 公平调度 - 每个流独立 CoDel 控制 - 隔离突发流量不影响交互流 - Linux 默认 AQM（从 3.6 开始） - CAKE（Common Applications Kept Enhanced）： - FQ-CoDel 的增强版：流量整形 + 三层公平 - 在 OpenWrt 上的广泛部署 - 实测：bufferbloat 前后的延迟对比

代码/示例: C 模拟 CoDel 算法核心逻辑，附队列延迟的时间序列对比

SVG: CoDel 的 sojourn time 判定流程图

系列十一：并发数据结构

72 · 无锁队列：Michael-Scott 算法与 ABA 问题

目标: 深入理解最经典的无锁数据结构和并发编程中最阴险的陷阱。

内容要点: - 为什么需要无锁数据结构：锁的问题（优先级反转、死锁、convoy effect） - lock-free vs wait-free 的定义： - lock-free：至少一个线程在有限步内完成操作 - wait-free：所有线程在有限步内完成操作 - Michael-Scott 队列（1996）：最广泛使用的无锁 FIFO 队列 - sentinel node（哨兵节点）简化空队列处理 - enqueue：CAS 更新 tail.next，再 CAS 更新 tail - dequeue：CAS 更新 head - 帮助（helping）机制：其他线程帮助推进 tail - ABA 问题： - 场景：CAS(addr, A, C) 成功但 A 已经被改成 B 又改回 A - 这个节点可能已经被释放和重新分配！ - 解决方案： - tagged pointer：用高位计数器（需要 double-width CAS） - hazard pointers（下一篇） - epoch-based reclamation（76 篇） - LCRQ（Linked Concurrent Ring Queue，Morrison & Afek 2013）： - CRQ（Concurrent Ring Queue）+ 链表 - 更好的可扩展性：减少 CAS 争用 - Java ConcurrentLinkedQueue 的实现分析

代码/示例: C 实现 Michael-Scott 队列（含 tagged pointer ABA 解法），附多线程 benchmark

SVG: enqueue/dequeue 的 CAS 操作步骤图

73 · 无锁栈：Treiber 栈与指数退避

目标: 最简单的无锁数据结构入门，理解 CAS 循环的基本模式。

内容要点: - Treiber 栈（1986）：最简单的无锁数据结构 - push：CAS 更新 top 指针 - pop：CAS 更新 top 指针 - 失败则重试（CAS retry loop） - CAS 争用的性能问题： - 高并发下大量 CAS 失败，CPU 空转 - 缓存行弹跳（cache line bouncing） - 退避策略（Backoff）： - 固定退避：简单但不自适应 - 指数退避（Exponential Backoff）：减少争用 - 退避参数的选择：min_delay、max_delay - Elimination Backoff Stack（Hendler et al. 2004）： - 核心思想：push 和 pop 可以直接交换，不碰栈 - elimination array：配对 push/pop 操作 - 争用越高，elimination 越有效 - 一个反直觉的结果：并发度越高反而越快 - 无锁栈 vs 有锁栈的性能对比： - 低争用：差别不大 - 高争用：无锁 + elimination 胜出 - 生产中无锁栈的使用场景：对象池、空闲列表

代码/示例: C 实现 Treiber 栈 + Elimination Backoff Stack，附不同线程数下的吞吐对比

74 · 并发跳表：ConcurrentSkipListMap 的设计

目标: 理解跳表为什么特别适合并发场景。

内容要点: - 跳表的并发友好性：不需要全局旋转（对比红黑树） - 有锁并发跳表： - 细粒度锁：每个节点一把锁 - 手锁耦合（hand-over-hand locking）：从高层到低层逐层加锁 - 乐观锁 + 验证：先无锁搜索，锁定后验证 - 无锁并发跳表（Fraser 2004）： - 节点标记（marking）：删除前先标记 next 指针 - CAS 插入和删除 - 并发下层级一致性的保证 - Java ConcurrentSkipListMap 的实现分析： - 三层节点：HeadIndex → Index → Node - 延迟删除：先逻辑删除再物理删除 - 为什么 Java 选跳表不选红黑树做并发有序 Map - 与并发 B-tree 的对比： - B-tree 的乐观锁耦合（Optimistic Lock Coupling） - B-link tree 的分裂协议 - 在高争用下的性能差异 - 实测：ConcurrentSkipListMap vs ConcurrentHashMap vs synchronized TreeMap

代码/示例: C 实现细粒度锁并发跳表，附与无锁版本的性能对比

75 · Hazard Pointers：安全内存回收的优雅方案

目标: 深入理解无锁数据结构中内存回收的核心难题。

内容要点: - 问题核心：无锁数据结构中，一个线程删除的节点可能正被另一个线程读取 - 不能立即 free：会导致 use-after-free - 不能永不 free：会内存泄漏 - Hazard Pointers（Michael 2004）： - 每个线程维护一组 hazard pointer（通常 1-2 个） - 线程访问节点时设置 hazard pointer - 回收时检查：如果节点被任何 hazard pointer 保护则延迟回收 - retire list：延迟回收的节点列表 - scan 操作：检查所有线程的 hazard pointer - 触发 scan 的时机：retire list 达到阈值 R = 2NH（N=线程数，H=每线程 HP 数） - 形式化保证：每个线程最多延迟回收 O(NH) 个节点 - 与其他内存回收方案的对比： - Reference counting：开销大（每次访问都要修改计数） - RCU（77 篇）：读侧零开销但需要 quiescent point - Epoch-based（76 篇）：整体开销低但一个慢线程阻塞所有回收 - C++ P2530 提案：std::hazard_pointer 的标准化进程

代码/示例: C 实现 Hazard Pointer 库 + 集成到 Michael-Scott 队列中

SVG: Hazard Pointer 的 scan 与 retire 流程图

76 · Epoch-Based Reclamation：Crossbeam 的实现之道

目标: 理解 EBR 的设计和 Rust crossbeam-epoch 的实现。与 post/rust/ 联动。

内容要点: - Epoch-Based Reclamation（Fraser 2004）的核心思想： - 全局 epoch 计数器：0, 1, 2 循环 - 线程进入临界区时记录当前 epoch - 退出临界区时更新线程的 epoch - 全局 epoch 推进条件：所有活跃线程都在当前 epoch - epoch 推进两次后，两个 epoch 前的垃圾可以安全回收 - EBR 的优势： - 读路径开销极低：只需读写线程局部的 epoch - 回收是批量的：一次回收一整个 epoch 的垃圾 - EBR 的劣势： - 一个慢线程（或被抢占的线程）会阻塞所有回收 - 内存回收延迟：最多两个 epoch 的垃圾积压 - Crossbeam-epoch（Rust）的实现： - Guard：pin/unpin 语义 - Atomic：带有 epoch 保护的原子指针 - Collector 和 Local 的关系 - Rust 所有权系统的天然优势：Guard 的生命周期强制释放 - DEBRA（Distributed EBR）：减少全局同步的改进 - 与 Hazard Pointer 的对比： - 读开销：EBR < HP - 内存回收延迟：HP < EBR - 抗慢线程：HP > EBR

代码/示例: Rust 使用 crossbeam-epoch 实现无锁栈，附与 Hazard Pointer 的性能对比

77 · RCU：Linux 内核的读侧零开销并发

目标: 深入理解 RCU 的工作原理和内核实现。与 post/linux/ 联动。

内容要点: - RCU（Read-Copy-Update）的核心思想： - 读侧完全无开销（no locks, no atomics, no memory barriers） - 写侧：先拷贝、修改拷贝、原子替换指针、等待读者离开后回收旧版本 - Grace Period： - 定义：所有在替换前开始的读操作都已完成 - 经过一个 grace period 后旧数据可以安全回收 - 读侧临界区： - rcu_read_lock() / rcu_read_unlock()：只是禁止/恢复抢占 - 编译成零指令（或仅一个 preempt_disable） - Quiescent State： - 上下文切换 = quiescent state - 所有 CPU 都经过 QS = grace period 结束 - synchronize_rcu() vs call_rcu()： - synchronize_rcu：同步等待 grace period - call_rcu：注册回调，grace period 结束后异步执行 - Tree RCU（Linux 的大规模实现）： - 层级结构管理 quiescent state 的汇报 - 避免所有 CPU 同时汇报给一个点 - 可扩展到数千 CPU - SRCU（Sleepable RCU）：允许在读侧临界区睡眠 - 用户态 RCU：liburcu 的实现 - RCU 的使用模式：链表遍历、路由表更新、配置热更新

代码/示例: C 实现简化用户态 RCU（基于 QS 检测），附读密集工作负载的性能测试

SVG: RCU grace period 的时间线图

78 · 并发哈希表：从分段锁到无锁设计

目标: 追踪并发哈希表的设计演进。

内容要点: - 全局锁哈希表：最简单但无扩展性 - 分段锁（Striped Locking）： - 锁的数量固定（如 16/64 把） - 不同段可以并行操作 - Java 6 ConcurrentHashMap 的设计 - Java 8 ConcurrentHashMap 的改进： - 取消分段锁，改用 CAS + synchronized - 桶级别的细粒度锁 - 红黑树化（链表长度 > 8） - 并发 resize：transfer 的分段协作 - Cliff Click 的无锁哈希表（NonBlockingHashMap）： - 完全无锁（lock-free），基于 CAS - 特殊值标记状态转换 - 并发 resize 的精妙协议 - 读写分离的 RCU 哈希表： - 读不加锁，写用锁 + RCU 发布 - Linux 内核的 rhashtable - 适合读多写少场景 - Lock-free resize 的挑战： - 帮助式迁移（cooperative migration） - 分阶段扩容（incremental resize） - 实测对比：不同读写比下各方案的吞吐量

代码/示例: C 实现分段锁哈希表 + RCU 哈希表，附不同并发度和读写比的 benchmark

79 · MPMC Channel：Go channel 与 crossbeam-channel 的实现对比

目标: 深入理解两种语言的消息传递实现。与 post/go/ 和 post/rust/ 联动。

内容要点: - 有界 vs 无界 channel： - 有界：生产者可能阻塞，背压（backpressure） - 无界：永不阻塞但可能 OOM - Go channel 的实现（runtime/chan.go）： - hchan 结构：环形缓冲区 + 发送等待队列 + 接收等待队列 - 有缓冲 channel：先尝试环形缓冲，满了则挂起 - 无缓冲 channel：直接从发送方拷贝到接收方 - select 的实现：随机打乱 case 顺序 + 全部上锁 + 检查 + 挂起 - close 的语义：向所有等待接收方广播零值 - crossbeam-channel（Rust）的实现： - 多种 flavor：array（有界）、list（无界）、zero（容量 0） - array flavor：环形缓冲 + 位置标记 - select! 宏：编译时生成高效分发代码 - 无锁设计：CAS + 原子操作 - 性能对比： - 单生产者单消费者（SPSC） - 多生产者单消费者（MPSC） - 多生产者多消费者（MPMC） - 吞吐量和延迟的对比 - flume（Rust）：另一种设计思路 - 为什么 channel 不是银弹：某些场景下共享内存更好

代码/示例: Go 和 Rust 分别实现 MPMC benchmark，附各场景下的性能数据

系列十二：压缩与编码

80 · Huffman 编码：从最优前缀码到 DEFLATE

目标: 从信息论基础理解 Huffman 编码的最优性，到 gzip 的完整实现。

内容要点: - 前缀码（Prefix-Free Code）：为什么需要前缀无歧义 - 香农编码：用 -log p 位编码概率为 p 的符号 - Huffman 编码的贪心构造：合并最低频的两个节点 - 最优性证明：在前缀码中 Huffman 的期望码长最短 - 与熵的差距：Huffman 最多浪费 1 bit/symbol（因为只能用整数位） - Canonical Huffman Code： - 标准化编码：只需存储码长数组 - DEFLATE 格式使用的就是 canonical Huffman - DEFLATE 算法（RFC 1951）： - LZ77 滑动窗口匹配 + Huffman 编码 - 距离/长度对的编码方案 - 动态 Huffman 表 vs 静态表 - Block 结构 - gzip/zlib 格式：DEFLATE + 头部/校验和 - Huffman 在现代压缩中的地位：被 ANS 取代的趋势 - 自适应 Huffman 编码（FGK、Vitter）：流式编码

代码/示例: C 实现 Huffman 编码器/解码器（含 canonical 形式），附压缩率对比

SVG: Huffman 树的构建过程与码字分配图

81 · LZ77/LZ78/LZW：字典压缩的两条路线

目标: 理解字典压缩的两种哲学和现代变体。

内容要点: - 字典压缩的核心思想：用更短的引用替代重复模式 - LZ77（滑动窗口）： - (offset, length, next char) 三元组 - 滑动窗口大小对压缩率的影响 - 匹配查找的实现：哈希链、后缀数组、B-tree - LZ78（显式字典）： - 动态构建词典，输出 (index, next char) - 词典增长控制：满了清空还是 LRU - LZW（LZ78 变体）： - 不输出 next char，词典预置初始符号 - GIF 的 LZW：Unisys 专利风波推动了 PNG 的诞生 - 现代 LZ 变体： - lz4（Yann Collet）：极速压缩/解压 - 简化的匹配格式：token + offset - 解压速度 > 5 GB/s - Snappy（Google）：设计目标是速度而非压缩率 - LZO：用于 Linux 内核的实时压缩 - lz4 vs Snappy vs zlib 的性能对比： - 压缩率、压缩速度、解压速度 - 不同数据类型的表现差异 - 为什么 LZ77 赢了 LZ78：实际压缩率更好

代码/示例: C 实现简化 LZ77 编码器 + lz4 格式解压器，附性能基准

82 · zstd 深度解剖：有限状态熵编码与字典训练

目标: 深入理解 zstd 如何成为”最佳通用压缩器”。

内容要点: - zstd 的定位：压缩率接近 zlib，速度接近 lz4 - 总体架构：LZ 匹配 + 序列编码 + 熵编码 - 有限状态熵（FSE / tANS）： - ANS（Asymmetric Numeral Systems）的核心思想 - 为什么 ANS 比 Huffman 好：接近熵的分数位编码 - tANS（tabled ANS）：查表实现的高速解码 - FSE 的编码表构建过程 - Huff0：zstd 中的 Huffman 编码器（用于 literal 数据） - LZ 匹配策略： - 四种压缩级别的不同匹配器：fast、dfast、greedy、lazy、lazy2、btlazy2、btopt - 最优解析（optimal parsing）：动态规划选择最佳匹配序列 - 字典训练（Dictionary Training）： - 为什么小数据需要字典：1KB 的 JSON 用通用 zstd 压缩率很差 - cover 算法：从训练样本中选择最佳字典片段 - 字典格式：raw content + offset 模型 - 应用场景：相似短文本（日志、API 响应） - zstd 的帧格式与流式编解码 - 实测：不同压缩级别下的压缩率 vs 速度曲线

代码/示例: C 演示 zstd 字典训练 + 使用字典压缩 JSON 数据，附压缩率对比

83 · 算术编码与 ANS：超越 Huffman 的熵编码

目标: 深入理解逼近熵极限的编码方法。

内容要点: - Huffman 的局限：整数位约束导致每符号最多浪费 1 bit - 算术编码的核心思想： - 将整个消息映射到 [0, 1) 的一个子区间 - 区间宽度 = 消息概率 - 用尽可能少的位数唯一标识该区间 - 范围编码（Range Coding）： - 算术编码的整数实现 - 归一化操作避免精度丢失 - 为什么范围编码不受算术编码的专利限制 - ANS（Asymmetric Numeral Systems，Duda 2009）： - 编码是一个状态转换：state → new_state - 解码是逆过程：new_state → state + symbol - rANS（range ANS）：类似范围编码的流式实现 - tANS（tabled ANS）：查表解码，速度 > 1 GB/s - ANS vs 算术编码： - ANS 解码速度快 2-3×（查表 vs 除法） - ANS 天然支持 LIFO 解码顺序（可以巧妙处理） - ANS 没有专利问题 - 为什么 ANS 正在取代算术编码： - zstd 用 FSE（tANS） - LZFSE（Apple）用 ANS - JPEG XL 用 ANS

代码/示例: C 实现 rANS 编码器/解码器，附与 Huffman 的压缩率和速度对比

84 · 整数压缩：varint → PForDelta → SIMD-BP128

目标: 理解搜索引擎倒排索引的核心压缩技术。

内容要点: - 为什么需要整数压缩：倒排索引存储大量文档 ID - 差分编码（Delta Encoding）：将有序 ID 序列转为差值序列 - varint（Variable-length Integer）： - Protocol Buffers 的 varint 编码 - 每字节 7 位有效数据 + 1 位继续标记 - Group Varint：4 个 varint 一组，长度集中存储 - Frame-of-Reference（FOR）： - 块内最小值 + 固定位宽偏移 - 简单高效但假设分布均匀 - PForDelta（Patched Frame-of-Reference）： - FOR + 异常值（exception）单独存储 - 选择使 90% 值适配的位宽，其余用 exception 列表 - SIMD-BP128（Lemire et al.）： - 128 个整数一组，用 SIMD 打包/解包 - 位宽选择：块内最大值的位宽 - SSE2/AVX2 的并行位操作 - 解压速度 > 4 billion int/s - Roaring Bitmap： - 16 位高位分桶 + 三种容器（array/bitmap/run） - 自适应选择最佳容器类型 - 在 Lucene、ClickHouse、Pilosa 中的应用 - 各方案的压缩率 vs 解压速度对比

代码/示例: C 实现 FOR + PForDelta + SIMD-BP128，附倒排索引场景的基准测试

85 · 时序数据压缩：Gorilla 编码与 Delta-of-Delta

目标: 理解时序数据库的核心压缩技术。

内容要点: - 时序数据的特征：时间戳递增、值变化小、大量重复模式 - Facebook Gorilla（VLDB 2015）论文解读： - 时间戳压缩：Delta-of-Delta - 大多数时间间隔固定（如 60s） - delta-of-delta 通常为 0，只需 1 bit - 变长编码非零 delta-of-delta - 浮点值压缩：XOR 编码 - 相邻值 XOR 后前导零和尾随零通常很多 - 只编码有效位（meaningful bits） - 内存中的压缩块格式 - 在 Prometheus/VictoriaMetrics/InfluxDB 中的实践： - Prometheus 的 chunk 格式：基于 Gorilla 的变体 - VictoriaMetrics 的优化：更激进的压缩策略 - InfluxDB 的 TSM 格式 - 其他时序压缩方案： - Simple-8b：整数序列的自适应位打包 - ZigZag 编码：有符号整数的无符号映射 - Run-Length Encoding：适合常量值段 - 压缩率对比：不同数据模式下的 bits/value

代码/示例: Go 实现 Gorilla 编码（时间戳 + 浮点值），附真实监控数据的压缩率测试

86 · 列式压缩：RLE / Dictionary / Bit-packing / FSST

目标: 理解分析型数据库和列式文件格式的编码方案。

内容要点: - 列式存储的压缩优势：同列数据类型相同、值域接近 - 常见列式编码： - Run-Length Encoding (RLE)：连续重复值压缩 - 适合排序列和低基数列 - Dictionary Encoding： - 将字符串映射为整数 ID - 字典 + ID 数组 - 基数 < 60000 时极其高效 - Bit-packing：用最少位数存储整数 - 与 FOR/PForDelta 的关系 - Delta Encoding：有序列的差分编码 - FSST（Fast Static Symbol Table，VLDB 2020）： - 字符串的通用压缩：1-8 字节符号表 - 不需要事先知道字典，从数据中自动学习 - 解压速度 > 3 GB/s - 在 DuckDB 中的应用 - Apache Parquet 的编码方案： - 编码层：Plain → Dictionary → RLE/Bit-pack → Delta - 页面级压缩：Snappy/zstd 叠加在编码之上 - Apache Arrow 的内存布局： - Validity bitmap + offset + data - 零拷贝分析的设计目标 - 压缩率 vs 查询速度的 trade-off： - 直接在压缩数据上查询（late materialization）

代码/示例: C 实现 Dictionary + RLE + Bit-packing 编码器，附 TPC-H 数据的压缩率对比

系列十三：计算几何

87 · 凸包算法：Graham Scan → Andrew → Chan 的进化

目标: 理解凸包问题的算法进化和 output-sensitive 算法的优雅。

内容要点: - 凸包的定义与基本性质 - Graham Scan（1972）：按极角排序后扫描，维护栈，O(n log n) - Andrew’s Monotone Chain（1979）：按坐标排序，分别构建上下凸包，数值更稳定 - Jarvis March（Gift Wrapping）：O(nh)，output-sensitive - Chan’s Algorithm（1996）：结合 Graham 和 Jarvis，O(n log h) 最优 output-sensitive - 猜测 h 的 repeated squaring trick - 3D 凸包：增量构造法，复杂性从 O(n log n) 跃迁 - 数值稳健性问题：浮点精度导致的错误与解决方案

代码/示例: C 实现 Graham Scan / Andrew / Chan 三种算法，附随机点集的性能对比

SVG: Graham Scan 的栈操作过程图

88 · 扫描线算法：从线段交到矩形面积并

目标: 掌握计算几何中最通用的算法范式。

内容要点: - 扫描线范式：将二维问题降维为一维动态问题 - Bentley-Ottmann（线段交点）：事件点调度 + BST 维护活跃线段，O((n+k) log n) - 矩形面积并：事件 = 矩形左右边，用线段树维护覆盖，O(n log n) - 矩形周长并：类似面积并但需额外计数 - 扫描线在 EDA（电子设计自动化）中的应用

代码/示例: C 实现 Bentley-Ottmann + 矩形面积并

89 · Voronoi 图与 Delaunay 三角剖分：对偶的力量

目标: 理解两个核心几何结构的数学联系和实际应用。

内容要点: - Voronoi 图：每个点的最近邻区域，凸多边形 - Delaunay 三角剖分：没有点在外接圆内，最大化最小角 - 对偶性：Voronoi 边 ↔︎ Delaunay 三角形 - Fortune 扫描线算法：O(n log n) 构建 Voronoi - 增量构造 Delaunay：逐点插入 + 翻转 - 应用：最近设施查询、网格生成、自然邻域插值

代码/示例: C 实现增量 Delaunay 三角剖分（含 Voronoi 对偶）

SVG: Voronoi 图与 Delaunay 三角剖分的对偶关系图

90 · R-tree 与空间索引：PostGIS 的底层结构

目标: 理解地理信息系统的核心索引技术。

内容要点: - R-tree（Guttman 1984）：类 B-tree 层级结构，每个节点存 MBR - R*-tree：改进的分裂策略 + 强制重插入，查询快 30-50% - Hilbert R-tree：Hilbert 空间填充曲线保持局部性 - PostGIS 的 GiST 索引框架 - 其他空间索引：Quadtree、Geohash、S2 Geometry（Google）

代码/示例: C 实现 R-tree（含范围查询和 k-NN），附性能对比

SVG: R-tree 的 MBR 层级结构图

91 · 点定位与梯形分解

目标: 理解点定位问题的经典解法。

内容要点: - 梯形分解：随机增量构造 O(n log n)，查询 DAG O(log n) - Persistent Search Structure：扫描线 + 持久化 BST - Kirkpatrick 层级细化法：O(n) 空间 O(log n) 查询 - 在地图引擎中的实际方案：R-tree 粗筛 + 精确定位

代码/示例: C 实现随机增量梯形分解 + 查询结构

92 · 最近点对与随机化几何算法

目标: 理解随机化在几何算法中的强大威力。

内容要点: - 分治算法（经典 O(n log n)）：中间带最多检查 7 个邻居 - Rabin 随机化算法 O(n) 期望：网格哈希 - 随机增量构造（RIC）的一般范式与向后分析 - Clarkson-Shor 技术：统一分析框架

代码/示例: C 实现分治 + Rabin 随机化，附性能对比

系列十四：动态规划进阶

93 · 树形 DP：换根、虚树与树上背包

目标: 掌握树形 DP 的高级技巧。

内容要点: - 换根 DP：两次 DFS 从 O(n^2) 到 O(n)，经典例题：树上距离和 - 虚树：DFS 序排序 + LCA + 栈构建，大小 O(k) - 树上背包：利用子树大小约束的 O(nk) 优化 - 点分治（Centroid Decomposition）：O(n log n) 处理树上路径问题

代码/示例: C++ 实现换根 DP + 虚树构建 + 点分治

94 · 状压 DP：用位运算驯服指数空间

目标: 掌握状态压缩 DP 的设计模式。

内容要点: - 位运算操作：枚举子集、popcount、lowbit - TSP：dp[mask][i]，O(2^n * n^2) - Steiner Tree：子集枚举优化 - SOS（Sum over Subsets）：高维前缀和 O(n * 2^n) - Profile DP / 轮廓线 DP：棋盘放置问题

代码/示例: C++ 实现 TSP + SOS + Profile DP

95 · 斜率优化与凸包技巧

目标: 将 O(n^2) DP 优化到 O(n log n) 或 O(n)。

内容要点: - 转移方程的线性形式识别：dp[j] = slope * x[i] + intercept - 斜率单调时 O(n)：单调栈维护凸包 - 斜率不单调时 O(n log n)：凸包上二分查找 - Li Chao Tree：动态插入直线 + 单点查询最值 - 经典题目：任务安排、APIO Sequence

代码/示例: C++ 实现斜率优化 DP + Li Chao Tree

96 · 分治优化 DP：决策单调性的力量

目标: 理解决策单调性和分治/SMAWK 优化。

内容要点: - 四边形不等式与决策单调性判定 - 分治优化：O(n^2) → O(n log n)，利用 opt(i) 的单调性 - Knuth 优化：O(n^3) → O(n^2) - SMAWK 算法：完全单调矩阵的行最小值 O(n) - CDQ 分治：在线分治优化

代码/示例: C++ 实现分治优化 DP + Knuth 优化

97 · 区间 DP 与矩阵链乘

目标: 理解区间 DP 的通用框架。

内容要点: - 基本框架：dp[i][j] = min(dp[i][k] + dp[k+1][j] + merge_cost)，O(n^3) - 矩阵链乘法：找使乘法次数最小的括号化 - 最优 BST：给定搜索概率构造最小代价 BST - 回文分割、RNA 折叠预测 - 在编译器指令选择和自动并行化中的应用

代码/示例: C++ 实现矩阵链乘 + 最优 BST

98 · DP 在工业界：资源调度、广告投放与路径规划

目标: 展示 DP 在工业系统中的真实应用。

内容要点: - 广告 pacing：预算约束下的在线背包 + 拉格朗日松弛 - 动态定价：Bellman 方程的近似求解 - CDN 调度：多级缓存的内容放置问题 - Viterbi 算法：HMM 最优路径，语音识别 / GPS map matching - 近似 DP 与强化学习的联系

代码/示例: Python 实现广告 pacing + Viterbi 算法

系列十五：数论与代数算法

99 · 快速傅里叶变换：从多项式乘法到信号处理

目标: 深入理解 FFT 的分治思想和广泛应用。

内容要点: - DFT 与单位根：消去引理、折半引理 - FFT 分治：奇偶分组，蝴蝶操作，O(n log n) - 迭代实现：位反转排列 - NTT（数论变换）：在 Z_p 上避免浮点精度 - 卷积定理：时域卷积 = 频域乘法 - Bluestein 算法：任意长度 DFT

代码/示例: C 实现 FFT/IFFT + NTT，附多项式乘法和大整数乘法

SVG: 蝴蝶操作的数据流图

100 · 素性测试与工业级素数生成

目标: 理解密码学系统如何高效生成大素数。与 post/crypt/ 联动。

内容要点: - 素数定理：1024 位随机数约每 700 个有一个素数 - 费马小定理与 Carmichael 数 - Miller-Rabin：二次探测 + 多轮测试，错误概率 ≤ 4^{-k} - Baillie-PSW：至今无已知伪素数 - AKS：理论重要性 >> 实际用途 - OpenSSL 的素数生成：小素数筛 → Miller-Rabin 多轮

代码/示例: C 实现 Miller-Rabin（含大整数），附素数生成性能测试

101 · 扩展欧几里得与模逆元

目标: 从基础数论到密码学应用。

内容要点: - 欧几里得算法：O(log(min(a,b))) 步 - Bezout 恒等式与扩展 GCD - 模逆元计算：ExtGCD vs 费马小定理 - RSA 密钥生成中的 d = e^{-1} mod phi(n) - 中国剩余定理与 CRT-RSA 加速 - Montgomery 模乘：避免昂贵除法 - constant-time 实现

代码/示例: C 实现 ExtGCD + Montgomery 模乘 + CRT

102 · 格基规约（LLL）：后量子密码的战场

目标: 理解格密码的核心算法基础。与 post/cryptography/ 联动。

内容要点: - 格的基本概念、好基 vs 坏基 - SVP、CVP 的 NP-hard 性 - LLL 算法：多项式时间近似最短向量，近似比 2^{(n-1)/2} - BKZ：LLL 的加强版 - 应用：Coppersmith 攻击、背包密码破解、ML-KEM 安全参数选择

代码/示例: Python 实现 LLL，附格攻击演示

103 · 有限域算术：从 AES 到 Reed-Solomon

目标: 理解有限域的构造和工程应用。

内容要点: - GF(p) 和 GF(p^n) 的构造 - GF(2^8) 算术：加法 = XOR，乘法 = 多项式乘法 mod 不可约多项式 - AES 中的 GF(2^8)：SubBytes S-Box 和 MixColumns - Reed-Solomon 编码：多项式求值/插值、在 QR 码和 RAID-6 中的应用 - RAID-6 的双校验块恢复数学

代码/示例: C 实现 GF(2^8) 算术库 + Reed-Solomon 编码器/解码器

104 · 椭圆曲线算术：群论视角

目标: 从代数结构理解椭圆曲线运算。与 post/cryptography/ 联动。

内容要点: - 点加法的几何直觉与代数公式 - 有限域上的椭圆曲线：Hasse 定理 - 标量乘法加速：double-and-add、NAF、Montgomery Ladder - 常见曲线：P-256、Curve25519、Ed25519 - constant-time 实现的重要性：侧信道防御

代码/示例: C 实现 GF(p) 椭圆曲线点运算（含 Montgomery Ladder）+ ECDH

SVG: 椭圆曲线点加法几何示意图

系列十六：编译器与语言实现中的算法

105 · DFA 最小化：词法分析器生成的核心

目标: 理解从正则到最小 DFA 的完整管线。延伸已有 regex 文章。

内容要点: - Thompson 构造 → 子集构造 → DFA 最小化 - Myhill-Nerode 定理：不可区分状态 - Hopcroft 算法：O(n log n) 分割细化 - 在 re2c / Flex 中的应用：减少状态表和缓存压力

代码/示例: C 实现完整管线 Thompson + 子集构造 + Hopcroft 最小化

SVG: DFA 分割细化过程图

106 · LR 与 LALR 解析

目标: 理解实际编译器使用的解析技术。

内容要点: - LR(0) 项与自动机 - SLR(1) → LR(1) → LALR(1) 的能力递进 - yacc/bison 使用 LALR(1) - shift-reduce / reduce-reduce 冲突与解决 - GLR 解析：处理歧义文法，Tree-sitter 的选择

代码/示例: Python 实现 LALR(1) 解析表生成 + 驱动器

107 · PEG 解析与 Packrat

目标: 理解 PEG 和 Packrat 的优势与代价。

内容要点: - PEG 的有序选择与贪心匹配 - Packrat 记忆化：O(n) 时间但 O(n * |G|) 空间 - 空间优化：有限记忆化、滑动窗口 - Tree-sitter 的增量解析 - PEG vs 手写递归下降 vs LALR 的选型

代码/示例: Rust/C 实现 PEG 解析器，附记忆化内存分析

108 · 寄存器分配：图着色与线性扫描

目标: 理解编译器后端最复杂的优化之一。联动 50 篇。

内容要点: - 活性分析与干涉图 - Chaitin 图着色：simplify → spill → select → coalescing - 线性扫描：O(n log n)，HotSpot C1 使用 - SSA 上的寄存器分配：弦图最优着色 O(V+E) - LLVM 的 Greedy Register Allocator

代码/示例: C++ 实现 Chaitin + 线性扫描，附代码质量对比

109 · SSA 形式与编译器优化

目标: 理解现代编译器 IR 的核心表示。

内容要点: - SSA 定义：每个变量只赋值一次 - 支配树构造：Lengauer-Tarjan O(E alpha(V)) - 支配边界与 phi 函数放置：Cytron 算法 - SSA 优化：SCCP、GVN、DCE、CSE - SSA 解构：lost-copy 和 swap 问题

代码/示例: Python 实现 SSA 构造 + SCCP 优化

SVG: 支配树与支配边界的计算图

110 · 垃圾回收算法全景

目标: 全面理解 GC 的设计空间。与 post/gc/ 联动。

内容要点: - 引用计数：即时回收、循环引用问题（Python） - 标记-清除 / 标记-整理 / Cheney 复制 - 分代假说：年轻代复制 + 老年代标记清除，写屏障 - 并发三色标记：Dijkstra/Steele 写屏障 - 现代 GC：G1、ZGC（着色指针）、Go GC（并发标记）、Shenandoah

代码/示例: C 实现 Cheney 复制 GC + 分代 GC，附暂停时间对比

SVG: 三色标记状态转换图

附加：算法工程杂谈

111 · 缓存无关算法：让硬件替你优化

目标: 理解缓存无关算法的理论和实际意义。

内容要点: - 外部存储模型与缓存无关模型（Frigo 1999） - 缓存无关 B-tree：van Emde Boas 布局 - Funnel Sort：缓存无关最优排序 - 缓存无关矩阵乘法：递归分块 - 实测：缓存命中率的量化对比

代码/示例: C 实现缓存无关矩阵乘法，附 perf stat 缓存命中率对比

112 · 无分支编程：当 if 成为性能杀手

目标: 理解分支预测和如何编写分支友好的代码。

内容要点: - CPU 流水线与分支预测器（TAGE 等） - CMOV 条件移动指令 - 无分支 min/max/abs/clamp - 无分支二分查找：Eytzinger 布局 - SIMD 的天然无分支性 - 实测：branch-misses 随可预测性变化的曲线

代码/示例: C 实现无分支二分查找 + branchless partition，附 perf stat

113 · SIMD 算法设计模式

目标: 建立系统的 SIMD 设计思维。延伸已有 SIMD 文章。

内容要点: - SoA vs AoS 布局 - Mask + Blend 替代 if-else - 查表（pshufb 16 路并行 4-bit lookup） - SIMD 前缀和与 stream compaction - Gather/Scatter 与跨 lane 操作 - AVX-512 新能力：mask register、compress/expand - ARM NEON vs x86 SSE/AVX 的跨平台策略

代码/示例: C/C++ 各模式示例，附标量/SSE/AVX2/AVX-512 性能对比

114 · 随机化算法：当运气成为武器

目标: 理解随机化在算法设计中的范式意义。

内容要点: - Las Vegas vs Monte Carlo - Schwartz-Zippel 引理：多项式零点概率、矩阵乘法验证 - 随机化快选：期望 O(n) - Karger 最小割：随机收缩，成功概率 >= 2/n^2 - 分布式中的随机化：共识、负载均衡、指数退避 - 去随机化：条件期望法

代码/示例: C 实现 Karger 最小割 + Schwartz-Zippel 验证

115 · 竞争分析与在线算法

目标: 理解在线算法的理论框架。

内容要点: - 竞争比定义：在线代价 / 离线最优代价 - 滑雪租赁：确定性 2-竞争、随机化 e/(e-1)-竞争；云计算按需 vs 预留 - 分页：LRU/FIFO k-竞争（最优确定性）、随机化 O(log k)-竞争 - k-server 问题与猜想 - Yao 原理：随机化下界的博弈论视角 - 实际应用：缓存替换、负载均衡、广告分配

代码/示例: Python 模拟滑雪租赁 + 分页在线算法，附竞争比实验

参考与灵感来源

By .