课程只教 HashMap 和二叉树，但真实系统里遇到的数据结构教科书根本不提。核心问题始终是：为什么用这个而不是那个？答案归根结底是三个权衡——能烧多少内存、能容忍多少磁盘 I/O、优化什么访问模式。

TinyLFU：缓存淘汰决策

经典 O(1) LFU 用每个频率桶一条双向链表 + HashMap，精确但 bookkeeping 量大。TinyLFU 换了个思路：用 count-min sketch——固定大小的二维计数器网格，多个哈希函数并行工作。Key 哈希到每一行后递增相应格子；查频率时取所有行的最小值。近似计数，可能 overcount 但永远不会 undercount。关键是 sketch 大小固定，无论 key 是 1 万还是 1 千万。

Caffeine（Java 缓存库）用 Windowed TinyLFU，把缓存分成三段：1% 的 window 吸收"只用一次"的噪音，20% 的 probation 是试用期，80% 的 protected 存放真正热点数据。每一次淘汰决策的代价只有几次哈希查询。

Skip List：有序索引 + 并发写入

Skip List 是一个带快车道的有序链表。底层包含所有按序排列的节点，上层逐步稀疏，可以 O(log n) 跳跃查找。插入时找到位置，掷硬币决定是否晋升到上一层——正面就继续掷，直到掷出反面。无需旋转，无需重平衡。

Redis sorted set 底层就是 Skip List。优势在于并发写入时每个层级只锁局部节点，可以做细粒度锁或 lock-free CAS。对比 B+ 树需要旋转触碰多个节点，必须大范围加锁。

HNSW：向量近似最近邻搜索

暴力 KNN 对 100 万个 128 维向量意味着每次查询做 1.28 亿次浮点比较。HNSW 构建多层图：底层每个向量作为节点连接到最近邻；上层是逐步稀疏的随机子集。搜索从最顶层出发，贪心地向查询向量靠近，然后下降到下一层重复，直到最底层精确搜索。

代价是全内存——100 万个向量大约需要 1GB 存储。如果内存紧张，IVF（倒排文件索引）把空间划分成簇，只搜索其中几个。

COW + Radix Tree：协作画布实战

Copy-on-Write 处理版本历史：每次笔画都快照整个画布太贵。COW 共享底层数据，只复制实际变化的部分。Undo 就是把根指针指向前一个版本，不做任何复制。

Radix Tree 处理空间查询：用 Z-order curve（Morton code）把 x/y 坐标交叉位编码成单一 key。画布上相邻的点 Morton 码前缀相似，在树里自然聚簇。"这个矩形区域内有什么？"变成前缀扫描。

二者结合：画布状态是一棵以 Morton 编码空间坐标为 key 的 Radix tree，版本化基于这棵树的 COW。每次笔画创建的新版本与上一版本共享 95% 的节点。冲突通过操作日志 + rebase 检测，而非盲目 last-writer-wins 丢弃其中一方的意图。