你的 CS 学位没好好教你的数据结构
每个计算机科学课程都会反复灌输七种基本数据结构：数组、链表、哈希表、栈、队列、图、树。你可能闭着眼睛都能背出它们的 Big O 复杂度——说真的，90% 的代码用这些足够了。
但偶尔，你的系统会撞上一堵墙，这七种基本结构都应付不了，就有人发明了一种更古怪的工具来填补缺口。
当哈希表无法给你一个快速的答案：Bloom 过滤器
普通哈希表很好用，直到你需要问"我可能之前见过这个吗？"——而数据集大到根本无法放进内存。
想想一个网络爬虫要检查数十亿个 URL，或者一个数据库要决定是否值得去磁盘查找某一行。
Bloom 过滤器的解法是放弃一个方向的确定性。它是一个固定的位数组加上少量独立的哈希函数。添加一个元素会翻转几个位。检查一个元素时做同样的哈希，看看这些位是否都亮着。
如果任何一个位是关的，那这个元素绝对没有被添加过——零歧义。
如果全都亮着，那这个元素很可能被添加过，但两个不相关的元素可能意外点亮同样的位——所以会有假警报。
零假阴性，偶尔假阳性。这就是体育馆门口的金属探测器：绝不会让人带着刀过去，但可能被你的皮带扣误报。
Cassandra 和 PostgreSQL 内部就用了这个技巧，浏览器也用它来屏蔽恶意网站而不必每次页面加载都去查网络。
当两个哈希槽胜过两个链：布谷鸟哈希
普通哈希表处理冲突的方式要么在槽位链成一个链表，要么向前探测下一个空位。两种方式都行，但表满了或哈希函数和数据不匹配时性能会严重下降。
布谷鸟哈希用了一个不同的方法。每个键从两个独立的哈希函数得到两个候选槽位。插入一个键时，如果第一个槽位是空的，搞定。如果被占了，你不做链表也不做探测——直接把当前的住户踢出去，把它塞进自己的第二个候选槽位。
如果那个槽位也满了，被踹的元素再被挪到它的备用槽，以此类推——像一场慢动作的抢椅子游戏。
好处是最坏情况 O(1) 的查找。不是"通常很快"，不是摊还，是真正的常数时间——因为任何键只能存在于两个已知的位置之一。两个位置都查一下，完事。
代价是插入偶尔会陷入一个被踢的循环，触发全面 rehash。所以它是一个在读速度比插入简单更重要的场景下选用的结构。
当树长得太高：B-树
二叉搜索树每个节点最多两个孩子。这在纸面上很好，但当数据集大到树部分存在磁盘上而非内存中时就有问题了。
每个层级更多的孩子意味着更少的层级总数，但二叉树做不到这一点。随着数据增长，树越长越高，每次搜索都要沿着高度逐层读取磁盘。
磁盘读很慢，哪怕少读几层都有质的区别。
几十年前泛化出来的 B-树解法是让每个节点持有多个排序的键、指向多个孩子，而不是只有两个。
想象一个图书馆，不是一排长长的单排书架从头走到尾，而是一排宽大的书架单元，每个单元里几十本按序排放的书，走廊尽头有个路牌告诉你该查哪个单元。
更少的走廊，更少的往返，底层仍然是同样的排序顺序。
这就是 B-树（以及它的近亲 B+ 树）成为大多数文件系统和关系数据库底层支撑的原因。短而宽的树，在"多一层"开始花费真实时间的时候，碾压又高又瘦的树。
当共享前缀是核心：基数树
现在来看一个专门为前缀查找构建的树——就像路由互联网流量用的那种。
每个设备都有一个 IP 地址。路由器需要把传入的数据包匹配到可能包含海量条目的路由表，而且要快到让你感觉不到延迟。
普通的 Tire 树在很多只有单个孩子的长链上浪费了大量空间——这些节点存在的唯一意义是指向唯一的另一个节点。
基数树通过把任何只有单个孩子的一系列节点合并成一个组合边来清理这个问题。只要数据共享长的公共前缀，树就更短、更密。这正好是 IP 地址范围的常见形状。
但在没有共享结构的数据上就不行了。扔一堆随机、高熵的字符串给它，压缩技巧基本帮不上忙——因为根本没有什么公共的东西可以合并。
当文档太大没法搬来搬去：Rope
试着在一个 50 万字的字符串最开头插入一个字符——如果它是一整块连续内存存储的，看看之后的所有内容都要被往后挪一个位置是什么后果。
对一条推文来说还行，但一本小说长度的文档就是灾难。这正是文本编辑器面临的问题。
Rope 绕过这个问题的方式是，从一开始就不把文本存成一个巨大的连续块。而是把它分成较小的块，作为树的叶子节点串在一起。树中的每个内部节点都维护着它下面所有字符的计数。
想要第 40000 个字符？不用从头扫描，沿着树往下走，用这些计数像目录一样跳过不需要的整个分支。
在开头附近编辑不再需要重写整篇文档——只需要重新链接树的一小部分。
这是 VS Code 在真正巨大的文件上仍然保持响应的重要原因。同样是协作编辑工具的底层思路——多人同时编辑时，不用每次按键都重新复制整篇文档。
所有这一切背后的模式
这几种结构没有一种想要取代数组或哈希表。它们每一种的存在，都是因为某个具体而真实的约束——慢磁盘、共享地址前缀、笨重的字符串、单向确定性的需求、常数时间的保证——让基本版本不堪重负，而有人用一个结构性的巧妙扭转把它修好了。
你在生产环境中实际用到的最奇怪的数据结构是什么？我很想听听背后的故事。
原文出处：Data structures your CS degree kind of glossed over（中文翻译）
