前两篇解释了 B 树怎样维护有序结构以及多个线程如何安全地访问它。但索引设计还有另一条思路有时我们不需要先找到记录只需要尽快确认“这里没有”有时数据全在内存里复杂的页分裂也未必是合适的选择。本篇沿着三个问题展开怎样跳过不可能命中的位置怎样在内存中保持有序怎样利用字符串本身的前缀它们分别引出过滤器、跳表与 Trie也为下一篇的全文与向量检索补齐基础。一、过滤器花少量内存省一次无效访问第 02 篇讲过 LSM一个键可能出现在多个 SSTable 中。假设每个文件都需要一次读取才能确认它是否存在一次不存在的键查询反而可能很贵。过滤器给文件配一份小摘要先回答集合成员查询明确不存在跳过该文件。可能存在继续访问文件中的真实索引和记录。这两种回答不对称。误报“可能存在”只增加一次检查误报“不存在”却会漏掉真实结果。因此经典 Bloom filter 的设计目标是允许前者避免后者。过滤器不是完整的键值索引它通常不能返回记录位置也不保存原始键以完成精确比较。二、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 树把大量键压在连续页内跳表则可能在多个内存地址间跳转。两者的空间和速度还取决于节点布局、键长度、并发与分配器不能只按渐进复杂度决定胜负。四、Trie比较完整键还是逐段走过键B 树通过分隔键比较来选子树Trie 按键的字符、字节或若干位逐段选择分支。假设保存car、cat、dog图 3car 与 cat 共用 c、a 两段路径终止标记说明一条路径是否已经构成完整键。查找cab时走到前缀ca后发现没有 b 分支即可返回不存在。查找ca则不同路径存在不代表这个完整键存在还要检查终止标记。如果每层的分支选择成本可视为常数长度为 L 的键查找约需 O(L)它依赖键长而非只依赖集合中的键数。按分支顺序遍历可以产生编码顺序但这种顺序是否等于业务排序还取决于字符串编码、大小写、排序规则和数值编码方式。从 Trie 到 Radix tree朴素 Trie 可能为一个长前缀分配许多只有单个孩子的节点。路径压缩把连续的单分支路径合并成一个带字符串片段的边例如直接保存database这个片段。查找时要比较边上的整个片段。完整存储并检查压缩片段的 Radix tree 仍可精确匹配并不会因为“做了压缩”就天然产生假阳性。只有省略了某些信息、把完整核验推迟到叶子或外部记录时才需要额外验证。节点的横向空间也可优化孩子很少时保存紧凑数组孩子很多时使用更直接的映射。自适应节点布局是在指针空间和分支选择成本之间取舍。五、把这些结构放回数据库需求常见结构核心收益排除某个文件中不存在的键Bloom filter 等过滤器减少无效访问内存中的动态有序集合跳表局部插入与有序扫描利用字符串前缀与编码顺序Trie / Radix tree共享前缀、逐段定位磁盘上的通用有序访问B 树页内局部性与较低树高这些结构可以协作LSM 可以使用跳表组织内存、用 Bloom filter 排除磁盘文件再在文件内使用其他索引定位块。下一篇预告第 07 篇把问题从“键在哪里”扩展到“哪些文档相关”倒排索引怎样支持关键词查询向量索引又怎样在召回率与检索成本之间取舍[上一篇05]数据库内核手记 05B 树下——删除、迭代器与并发控制[下一篇07]数据库内核手记 07从关键词到语义——倒排索引与向量检索 
长河君 · 2026/10/30 4:57:42 · 阅读 1.2k 数据库内核手记 06：索引不止 B+ 树——过滤器、跳表与 Trie
前两篇解释了 B 树怎样维护有序结构以及多个线程如何安全地访问它。但索引设计还有另一条思路有时我们不需要先找到记录只需要尽快确认“这里没有”有时数据全在内存里复杂的页分裂也未必是合适的选择。本篇沿着三个问题展开怎样跳过不可能命中的位置怎样在内存中保持有序怎样利用字符串本身的前缀它们分别引出过滤器、跳表与 Trie也为下一篇的全文与向量检索补齐基础。一、过滤器花少量内存省一次无效访问第 02 篇讲过 LSM一个键可能出现在多个 SSTable 中。假设每个文件都需要一次读取才能确认它是否存在一次不存在的键查询反而可能很贵。过滤器给文件配一份小摘要先回答集合成员查询明确不存在跳过该文件。可能存在继续访问文件中的真实索引和记录。这两种回答不对称。误报“可能存在”只增加一次检查误报“不存在”却会漏掉真实结果。因此经典 Bloom filter 的设计目标是允许前者避免后者。过滤器不是完整的键值索引它通常不能返回记录位置也不保存原始键以完成精确比较。二、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 树把大量键压在连续页内跳表则可能在多个内存地址间跳转。两者的空间和速度还取决于节点布局、键长度、并发与分配器不能只按渐进复杂度决定胜负。四、Trie比较完整键还是逐段走过键B 树通过分隔键比较来选子树Trie 按键的字符、字节或若干位逐段选择分支。假设保存car、cat、dog图 3car 与 cat 共用 c、a 两段路径终止标记说明一条路径是否已经构成完整键。查找cab时走到前缀ca后发现没有 b 分支即可返回不存在。查找ca则不同路径存在不代表这个完整键存在还要检查终止标记。如果每层的分支选择成本可视为常数长度为 L 的键查找约需 O(L)它依赖键长而非只依赖集合中的键数。按分支顺序遍历可以产生编码顺序但这种顺序是否等于业务排序还取决于字符串编码、大小写、排序规则和数值编码方式。从 Trie 到 Radix tree朴素 Trie 可能为一个长前缀分配许多只有单个孩子的节点。路径压缩把连续的单分支路径合并成一个带字符串片段的边例如直接保存database这个片段。查找时要比较边上的整个片段。完整存储并检查压缩片段的 Radix tree 仍可精确匹配并不会因为“做了压缩”就天然产生假阳性。只有省略了某些信息、把完整核验推迟到叶子或外部记录时才需要额外验证。节点的横向空间也可优化孩子很少时保存紧凑数组孩子很多时使用更直接的映射。自适应节点布局是在指针空间和分支选择成本之间取舍。五、把这些结构放回数据库需求常见结构核心收益排除某个文件中不存在的键Bloom filter 等过滤器减少无效访问内存中的动态有序集合跳表局部插入与有序扫描利用字符串前缀与编码顺序Trie / Radix tree共享前缀、逐段定位磁盘上的通用有序访问B 树页内局部性与较低树高这些结构可以协作LSM 可以使用跳表组织内存、用 Bloom filter 排除磁盘文件再在文件内使用其他索引定位块。下一篇预告第 07 篇把问题从“键在哪里”扩展到“哪些文档相关”倒排索引怎样支持关键词查询向量索引又怎样在召回率与检索成本之间取舍[上一篇05]数据库内核手记 05B 树下——删除、迭代器与并发控制[下一篇07]数据库内核手记 07从关键词到语义——倒排索引与向量检索