上一篇的缓冲池解决了“读过的页能不能少读一次”但它并不能告诉数据库目标记录在哪。如果id没有任何可利用的索引查询id 1001仍可能要检查大量记录。索引提供了额外的访问路径。它可以保存键与记录位置的对应关系也可能包含表达式结果、额外列甚至完整记录不能简单定义为“表的一份子集副本”。本篇先讲哈希索引。核心直觉是利用哈希值缩小候选范围再比较实际键来确认结果。先回答标题里的问题普通哈希索引不维护键的大小顺序所以通常不能像有序索引一样高效定位一个连续范围。但数据库仍然可以通过扫描等方式执行范围查询并不是“这条 SQL 无法运行”。一、从 key 到桶计算之后仍然需要比较把哈希表想成一个槽位或桶的集合。给定键k先计算哈希值再根据当前表结构确定候选位置。哈希值 h(k) 候选桶 根据表大小或目录从哈希值中选出一个位置例如为了方便手算设h(k) k有 8 个槽初始槽位取h(k) mod 8。那么 10、18、26 都会落到槽位 2。图 1取模只是便于演示的映射。实际哈希函数还需要考虑键分布、计算成本和攻击性输入。这就是哈希冲突。两个键的哈希值或候选位置相同不代表两个键相等。因此哈希表一般要保留实际键或能取回实际键以完成比较的信息。仅保存一个短哈希值通常不足以实现精确匹配。平均 O(1)省略了哪些前提在哈希分布良好、负载因子受控、键处理成本可视为常数等假设下哈希表查找的期望成本可接近 O(1)。但实际代价还包括计算长字符串等键的哈希值。探测冲突位置或访问桶链。缓存未命中和磁盘 I/O。并发协调、扩容和迁移。最坏情况下冲突处理可能退化到线性成本。平均常数时间也不等于“一定只有一次磁盘 I/O”更不保证在任何点查上都比 B 树快。二、哈希函数与冲突方案是两件事1. 哈希函数负责把键分散开好的哈希函数通常需要计算快、分布较均匀并与键的相等语义一致。如果比较器认为两个键相等哈希设计必须保证它们进入兼容的查找路径。“同一个键总产生同一个结果”也有上下文通常指在算法、种子和编码规则相同的前提下。采用随机种子的内存表不同进程的结果可能不同持久化索引则必须能稳定重现或保存所需规则。xxHash 等非密码学哈希常用于高性能场景但“数据库永远不需要考虑安全性”并不成立。面对可控的恶意输入还可能需要防范碰撞攻击密码、完整性校验等用途也不能套用普通哈希索引的选型。完美哈希也不是“必然极慢、完全不能用”它面向特定键集合避免冲突构建和维护条件与一般动态哈希表不同。2. 冲突方案负责安排已经撞在一起的键方案主要思路常见代价开放寻址在同一槽数组中继续寻找其他位置探测长度、删除标记、扩容成本分离链接一个桶关联多个条目或溢出页指针追踪、桶链变长、额外 I/OCuckoo 哈希每个键有少量候选位置必要时搬移旧条目插入迁移极端情况下重建静态和动态描述的是容量或地址空间怎样变化与“冲突时怎么办”是两个相关但不同的维度。链式表可以接纳更多条目却不会仅靠链变长就自动保持良好性能。三、线性探测删除为什么不能直接留空线性探测把槽数组视为环发生冲突就向后继续探测走到末尾再回到开头。在 8 槽示例里依次插入 10、18、2610 → 初始槽 2 → 放入 2 18 → 初始槽 2 已占用 → 放入 3 26 → 槽 2、3 已占用 → 放入 4查找 26 时同样从槽 2 开始沿着插入所遵循的探测序列找下去。图 2EMPTY表示从未使用或经正确整理后的空槽DEL表示墓碑。两者对查找的含义不同。1. 三种槽位状态状态查找时的处理已占用比较实际键不匹配则继续墓碑 DEL曾经有条目继续探测真正空槽 EMPTY在这种探测协议下可以判定目标不存在若删除 18 后把槽 3 直接当成真正空槽查找 26 就会提前停止错误地报告“不存在”。2. 墓碑解决了查找又给插入留下什么问题插入时可以记住遇到的第一个墓碑位置但对于唯一键表仍需要继续确认后面是否已经有相同键不能一见墓碑就插入一个重复条目。墓碑积累还会拉长探测序列所以需要清理或重建。另一类方案是后移删除移动符合探测规则的条目来修复空洞。它需要处理好环形区间但不能简单等同于“随便把后面的记录前移”。开放寻址还需要监控负载因子α 条目数 / 槽数。适当预留空间可以缩短探测但没有适合所有实现的“一律分配两倍槽位”规则。3. 相同键关联多条记录怎么办数据库索引可能允许重复键。例如很多人的年龄都为 30。可以把同一个键关联到一组 RID也可以保存多个(key, RID)条目。查找不再是“找到一个相等键就结束”而是按索引语义返回所有匹配项并处理可见性和重复记录。高性能内存哈希表还会把控制字节与实际条目分开利用批量比较减少无效键比较。比如 Abseil 的 Swiss Tables使用控制元数据等优化不能简单视为最朴素的一格一格线性探测。四、Cuckoo 哈希把插入的复杂性换给查找Cuckoo 哈希给每个键提供少量候选位置。可以来自两个表也可以是同一张表中的多个候选桶不要求一定维护多张表。假设一个键只有位置h1(k)和h2(k)可选有空位置时直接放入。都被占用时选择一个位置搬走原来的条目。被搬走的条目再尝试自己的其他候选位置。若迁移过长或形成循环则扩容、换种子重建或采用实现允许的备用结构。在经典、已成功构建且候选数固定的模型中查找只需检查少量位置代价主要转移到插入和重建上。加入溢出区、并发迁移或磁盘桶后还需要重新分析实际界限。五、可扩展哈希桶满了是否一定要翻倍目录可扩展哈希extendible hashing用目录把一部分哈希位映射到桶。本文统一使用哈希值的低位避免“前缀、后缀”混用全局深度g目录使用多少位目录共有2^g个入口。桶的局部深度l区分这个桶需要多少位。l ≤ g一个桶可能被多个目录入口引用。一个能手算的例子设每桶最多容纳 2 个条目演示哈希值就是整数本身。现在g 200、10 → 桶 A局部深度 1保存 [0, 2] 01 → 桶 B局部深度 2保存 [1] 11 → 桶 C局部深度 2保存 [3]A 只看最低 1 位是否为 0所以目录00和10都指向 A。向 A 插入 4 后溢出。由于分裂前l 1 g 2不必扩大目录只需按低 2 位重新分配图 3分裂后00指向[0,4]10指向[2]两个桶的局部深度都变为 2全局深度仍为 2。规则应当这样记分裂前的状态处理l g现有目录已含有区分下一位所需的入口分桶并调整相关引用l g先把目录翻倍令g g 1再分桶并调整引用例如随后向[0,4]插入 8这个桶的l已等于g 2就需要使用第 3 位目录扩为 8 项000可指向[0,8]100指向[4]。比较的是分裂之前的局部深度。如果先增加局部深度再套用上述条件就容易写出边界错误。一个桶分裂后仍可能拥挤若多个键的哈希位长期无法区分继续分裂也不是无限有效需要处理最大深度、真正哈希碰撞或其他溢出机制。目录本身也可能大到需要多级或页式组织。六、线性哈希按计划逐桶扩展线性哈希与线性探测不是同一件事。前者是渐进扩容方法后者是开放寻址的冲突处理方法。线性哈希用层级i和分裂指针s逐步完成一轮扩展。设初始桶数为Nh_i(k) h(k) mod (N × 2^i) h_(i1)(k) h(k) mod (N × 2^(i1)) b h_i(k) 如果 b sb h_(i1)(k)b s表示这个桶在本轮已经分裂需要采用下一层的映射。图 4本轮基数为 4s 1时已有桶 0—4。下一次扩展分裂桶 1、增加桶 5随后令s 2。例如基数为 4、s 1时哈希值 4 先得到桶 0由于0 1再按模 8 得到桶 4哈希值 7 先得到桶 3因3 ≥ 1仍进入桶 3。扩展由负载因子或溢出等策略触发但被分裂的是s指定的桶。尚未轮到的拥挤桶可以暂时使用溢出页。一轮结束时层级增加s回到 0。这里通常是在调整同一哈希值的取模范围并不是每次都创造一个全新的哈希算法。收缩则需要相反的、有序的合并过程不能随便删除某个空桶。七、为什么它不能像 B 树那样扫描一个范围普通哈希会打散键的大小关系。10 和 11 不一定落在相邻桶即使偶然相邻也没有可依赖的顺序保证。所以id BETWEEN 1000 AND 2000通常无法先找到一个起点再沿相邻桶只访问该范围。查询普通哈希索引有序 B 树索引完整键等值典型用途也可以有效支持大小范围通常不能直接加速有序范围定位可定位起点后扫描按索引键排序不提供所需顺序顺序兼容时可利用字符串前缀匹配普通完整键哈希通常不能直接利用取决于运算符、排序规则和索引定义复合键只指定前面部分通常无法计算完整键对应的桶常可利用相应前导键具体仍看实现这里讨论的是普通等值哈希不包括专门保留相似性等性质的其他哈希方案。范围条件也并非绝对不能转化为一组点查很小的、可枚举的离散集合就是例子。但这不是哈希索引提供了有序范围扫描能力。PostgreSQL 的官方文档也将普通 Hash 索引定位于等值比较而 B-tree 支持更广的有序比较。参见索引类型说明。八、从哈希表到数据库哈希索引还差什么数据库内部的哈希表可以用于连接、聚合和缓冲池页表它们不一定是用户可创建、需要持久化的表索引。持久化哈希索引还要考虑页式桶、溢出页、记录可见性、并发分裂、日志和崩溃恢复。索引更新本身也有成本不能只比较一次查找的渐进复杂度。下一篇预告第 04 篇进入 B 树怎样把页组织成一棵很矮的有序树又怎样在插入时维持区间与结构[上一篇02]数据库内核手记 02存储引擎——磁盘、文件与缓冲池[下一篇04]数据库内核手记 04B 树上——结构、查找与插入