CS 课教的那张清单——数组、链表、哈希表、栈、队列、图、树——本身没毛病。地基是牢的。但它只讲了数据结构的一半。另一半呢，全活在真实系统的肚子里，脏、快、有脾气，几乎全是为了打一个在具体场景里冒出来的痛点才被发明出来的。大学不教它们，真不是它们冷门，是“已经有解了”的东西，不需要拎出来当考题占课时。
我前几天翻到一篇讲“CS 学位跳过的数据结构”的文章，边看边拍大腿，这些玩意儿当年有人要是这么讲，我能少走三圈弯路。
第一个画布隆过滤器，最有名也最反直觉的一个。
打个比方，它就是门口那个记性不好的保安大爷。他记不住每个进过门的人长什么样，但他有一块大板子，上面钉了一排钉子。每进来一个人，他往板子上固定的几个位置各按一个图钉。之后再有人来，说“我之前来过”，大爷就去检查那几个位置——钉子都在？可能真来过。少了一个？那肯定没来过。
加入一个元素 x：
hash₁(x) ──► 位 3 ──┐
hash₂(x) ──► 位 17 ──┼─► 全部置 1
hash₃(x) ──► 位 42 ──┘
查询 y 在不在集合里：
hash₁(y) ──► 位 3 ──┐
hash₂(y) ──► 位 19 ──┼─► 有一个是 0 ──► 肯定不在
hash₃(y) ──► 位 42 ──┘
它最大的特点就是那句“可能已经出现过”：允许假阳性（大爷记岔了，把没来过的人放进来了），但绝不给你假阴性（你真来过，他一定认得出）。这玩意儿 1970 年就有了，Burton Bloom 写的论文，快六十年了，Cassandra、Postgres 全在内部用它。浏览器拿它筛恶意网址也是这个思路——不用每个页面都先发网络请求问一遍，本地滤掉一批，剩下的再问。
但先别急着认同这个比喻，它有个地方漏风：门卫大爷是“一个人”，而布隆过滤器是哈希函数和位数组。实际是三个 hash 决定几个位置，不是“大爷认脸”。不过抓大方向够了，它就是一层预过滤，把“肯定没有”挡在门外，放“可能有”进去。
第二个卡了我一阵子的，杜鹃哈希。
我第一次看到这名字，还以为什么高深算法——结果它思路简单到离谱。每个键有两个候选位置，两个不同的哈希函数算出来。插入的时候俩位置都满了？行，随手抓起一个位置的现住键，踢出去，让它去自己的另一个候选位。
插入 x：
位置 A（hash₁(x)）被 y 占了
──► 把 y 踢到 hash₂(y) 的位置
──► 那个位置被 z 占了
──► 把 z 踢到 hash₁(z) 的位置
──► 空位，停
小杜鹃把别的蛋挤出去的画面，名字就是这么来的。
它最漂亮的地方在于查找一定是 O(1)——每个键只可能待在两个位置之一，看一眼就知道在不在。但最烦人的也在这：插入可能踢来踢去踢出循环，最后只能把整张表重哈希。所以这结构适合“读多写少”，写多了重哈希能让人想哭。
读 O(1) 的哈希表，代价是写操作变啰嗦——这个取舍，CS 课真没讲过。
B 树和基数树，我放一起说。它们的本质其实一个意思：都是嫌树太高。
B 树让一个节点装多个键、多个子节点，树变矮了，磁盘访问次数少了。加上 B+ 树，基本撑起了现代文件系统和关系数据库。这个数据库课多少会提，算“课程有讲”。
基数树更狠，它把连续的单子节点链压成一条边。共享前缀特别长的数据（IP 路由表就是典型）能被它压成又短又密的树。但——很关键的“但是”——如果数据是随机的高熵字符串，前缀根本共享不起来，压缩效果约等于零。
普通字典树（沿路每个节点只有一个孩子）：
a ─ b ─ c ─ d ─ ... ─ z （十层）
基数树（把单链压成一条边）：
abcdefgh...z （一条边写完全部）
等等，这个画法其实不太对，基数树是有选择地压，不是无脑合并……算了，方向没错，大概那意思。
最后是 Rope，这个我想单独画一下，因为它跟每个人的日常都有关。
不知道你想过没有：VS Code 打开一个一百兆的日志文件，滚动、查找、编辑怎么还那么流畅。如果文本是“一个字符串”，你改中间任何一个字符，后面所有内容全得挪一遍——一百兆的字符串，一次编辑就是一次内存爆炸级别的操作。
Rope 的思路很简单：把整段文本拆成很多小块，用一棵树组织起来。内部节点不存文本，只存“我的子树从起点开始一共有多少个字符”。
10 个字符的 "abcdefghij" 存成 Rope：
(内部节点: 总长 10)
/ \
(长 3) (长 7)
/ \ / \
"abc" "de" "fgh" "ij"
编辑时你只需要切开一两块、换掉一块，别的兄弟节点根本不用碰。VS Code 在超大文件上能保持顺滑，靠的就是这个思路撑着（当然不止它一个）。协作编辑工具也一样，每次改都先把整篇文档复制一遍，谁也扛不住。
我上一次手写 Rope，是做玩具编辑器的时候。当时觉得“文本不就是个数组吗”，然后被大文件按在地上摩擦——改中间，后面全要搬。搬完手一抖，忘了更新长度字段，直接崩了。
回过头看，就是缺了“把文字拆开存”这个念头。
好了，想说的说完了。
其实就一句话：这些数据结构一点都不玄，它们只是没被好好讲明白，或者说，它们全是先有了具体的问题，才被逼出来的——不是为了出考题才生的。
CS 课教书上的那些，因为它们干净、通用、能当考点。但真实系统面对的是又大又脏的数据。大得记不住，脏得排不齐，还得快。布隆过滤器、杜鹃哈希、B 树、基数树、Rope，每个都是对着“又大又脏还得快”吼回去的回应。
这个回应，比它们自己看上去的样子，想说的话要多得多。
下期想画开哪个？我最近绕了挺久的还有 embedding 和 KV cache，你说了算。