数据库内核手记 06：索引不止 B+ 树——过滤器、跳表与 Trie-开发者社区

前两篇解释了 B+ 树怎样维护有序结构，以及多个线程如何安全地访问它。但索引设计还有另一条思路：有时，我们不需要先找到记录，只需要尽快确认“这里没有”；有时，数据全在内存里，复杂的页分裂也未必是合适的选择。

本篇沿着三个问题展开：怎样跳过不可能命中的位置？怎样在内存中保持有序？怎样利用字符串本身的前缀？它们分别引出过滤器、跳表与 Trie，也为下一篇的全文与向量检索补齐基础。

第 02 篇讲过 LSM：一个键可能出现在多个 SSTable 中。假设每个文件都需要一次读取才能确认它是否存在，一次不存在的键查询反而可能很贵。

过滤器给文件配一份小摘要，先回答集合成员查询：

这两种回答不对称。误报“可能存在”只增加一次检查；误报“不存在”却会漏掉真实结果。因此经典 Bloom filter 的设计目标是允许前者，避免后者。

过滤器不是完整的键值索引：它通常不能返回记录位置，也不保存原始键以完成精确比较。

设位数组长度为 m，初始全部为 0，另有 k 个哈希映射。插入键 x 时，计算 k 个位置，把相应位设为 1；查询时重新计算这些位置。

用一个 8 位的教学例子：

插入 A：设置位置 1、4 插入 B：设置位置 4、6 最终置位集合：{1, 4, 6} 查询 C：检查位置 1、6 → 都是 1，但 C 从未插入 查询 D：检查位置 2、6 → 位置 2 是 0，因此一定不存在

图 1：不同键共同留下的位，可能拼出另一个键的查询特征。这正是假阳性的来源。

为什么没有假阴性？只要插入时正确设位、之后不错误清除、查询使用同一组规则，一个已插入键对应的位就仍然全为 1。并发插入也要正确地发布更新；算法性质不能替代实现同步。

在哈希近似独立、均匀分布的模型下，插入 n 个元素后，假阳性概率近似为：

f ≈ (1 - exp(-k × n / m))^k

直觉是：数组越拥挤，随机检查的 k 位越容易全部为 1。给定 m 和 n，较合适的哈希数量约为k ≈ (m/n) × ln 2。

例如每个键分配 10 位、使用 7 个映射，近似误报率约为 0.82%。这是模型估计，不是任意输入下的保证。继续向固定大小的过滤器塞入更多键，误报率会升高。

哈希数量也不能无限增加：计算更贵，而且额外设位会加速数组变满。

A 和 B 都使用位置 4。删除 A 时如果把位置 4 清零，B 的查询就可能错误地返回不存在。

Counting Bloom filter 用计数器替代单个位，使受控删除成为可能，但要防止计数溢出，并确保删除操作对应真实插入。Cuckoo filter 保存短指纹，采用另一种组织方式支持成员查询及删除；它与第 03 篇保存完整键的 Cuckoo 哈希表不是同一个结构。

还有面向范围的摘要，例如根据键前缀构建的范围过滤器。它们试图快速排除“这个区间里没有键”，但是否支持动态更新、允许何种误报，取决于具体设计。

普通有序链表点查最坏要走过大量节点。跳表保留底层完整链表，再为部分节点建立更高层的前进链接。

图 2：寻找 35 时，先在高层前进到 20；更远的节点会越过目标，于是逐层下降，最后在底层找到 35。

查找时保持一个原则：向右走之后仍小于目标，才继续前进；再走就会越过目标时，向下走一层。最底层决定实际命中与否，范围扫描也从这里继续向右。

节点高度通常由随机过程决定。例如每增加一层的概率是 1/2，那么 n 个节点的期望分布是：底层 n 个、上一层约 n/2 个、再上一层约 n/4 个。层数和期望查找成本因此为 O(log n)。最坏情况仍可能退化，不能把期望界写成确定界。

插入 35 时，先记录各层上应位于它前面的节点，再选择新节点高度，把相应链接接过去。它不需要像平衡二叉树一样旋转，也不需要像页式 B+ 树一样搬移半页条目。

删除则解除节点在各层上的链接。在并发实现中，常见做法是先逻辑标记，再物理摘链，最后等待安全回收。读者可能仍持有旧地址，因此“从链中移除”与“释放内存”必须分开。

原子 CAS 可以帮助替换一个链接，但不能自动解决重复键、失败重试、内存可见性和回收问题。正确的无锁跳表需要完整协议。

跳表常用于内存中的有序集合，也适合作为 MemTable 的候选结构：插入后仍能有序遍历，方便生成有序文件。

代价是额外指针和较分散的访问。B+ 树把大量键压在连续页内，跳表则可能在多个内存地址间跳转。两者的空间和速度还取决于节点布局、键长度、并发与分配器，不能只按渐进复杂度决定胜负。

B+ 树通过分隔键比较来选子树；Trie 按键的字符、字节或若干位逐段选择分支。

假设保存car、cat、dog：

图 3：car 与 cat 共用 c、a 两段路径；终止标记说明一条路径是否已经构成完整键。

查找cab时，走到前缀ca后发现没有 b 分支，即可返回不存在。查找ca则不同：路径存在不代表这个完整键存在，还要检查终止标记。

如果每层的分支选择成本可视为常数，长度为 L 的键查找约需 O(L)；它依赖键长，而非只依赖集合中的键数。按分支顺序遍历可以产生编码顺序，但这种顺序是否等于业务排序，还取决于字符串编码、大小写、排序规则和数值编码方式。

朴素 Trie 可能为一个长前缀分配许多只有单个孩子的节点。路径压缩把连续的单分支路径合并成一个带字符串片段的边，例如直接保存database这个片段。

查找时要比较边上的整个片段。完整存储并检查压缩片段的 Radix tree 仍可精确匹配，并不会因为“做了压缩”就天然产生假阳性。只有省略了某些信息、把完整核验推迟到叶子或外部记录时，才需要额外验证。

节点的横向空间也可优化：孩子很少时保存紧凑数组，孩子很多时使用更直接的映射。自适应节点布局是在指针空间和分支选择成本之间取舍。