7.1 哈希索引：等值访问、冲突与动态扩容

哈希索引用 hash function 把 search key 映射到 bucket，擅长 equality predicate。它不保留 key order，因此通常不能直接服务 range scan、ordered output 或 prefix ordering。所谓 O(1) 是在负载与分布合理时的 expected probe complexity，不是固定一次 I/O 的保证。

本课目标

• 区分 hash table、persistent hash index 与 hash join；
• 解释 bucket、slot、collision、overflow 与 load factor；
• 理解 extendible hashing 和 linear hashing 的增长方式；
• 分析 equality、NULL、duplicate 与 collation 语义；
• 知道何时 B+ tree 反而更合适。

从 hash value 到 bucket

hash(search_key) -> hash bits
directory/bucket mapping -> bucket page
scan matching fingerprints/keys in bucket
follow overflow or retry probes when necessary
verify actual key equality

最后一步不能省。hash collision 意味着不同 keys 可能得到同一 hash/bucket，index 必须保存并比较 actual key 或足够的 collision-resolution information。

Expected O(1) 的前提

in-memory hash table 在以下条件下能提供 expected constant probes：

• hash function 对真实 key distribution 足够均匀；
• load factor 受控；
• resize/overflow 能跟上增长；
• adversarial keys 不造成集中冲突；
• key comparison cost 有界。

persistent hash index 还要考虑 directory/cache miss、bucket page I/O、overflow chain、WAL、latch 与 base-row lookup。一次 equality query 可能返回很多 duplicate keys，输出成本本身就是 O(result size)。

Collision resolution

Separate chaining / overflow pages

bucket 满后链接 overflow page。实现简单，但 skew/hot key 会形成长 chain、随机 reads 和 latch hotspot。

directory[17] -> bucket page -> overflow page -> overflow page

Open addressing

冲突后按 probe sequence 寻找其他 slots，例如 linear/quadratic probing 或 double hashing。cache locality 好，但 deletion、high load factor 和 resize 复杂；on-disk page layout 还需控制 probes 跨页。

Cuckoo hashing

key 有多个候选位置，插入冲突时踢出已有 key 并搬到其其他位置。lookup probes 少，但 insertion 可能形成 relocation chain，需要 stash/rehash。它是实现选择，不是所有数据库 hash index 的默认结构。

Hash function 不是密码 hash 的同义词

index hash 追求速度、distribution 与稳定 encoding；password hashing 追求昂贵、salted、抗暴力破解。不要用快速 non-cryptographic hash 保存密码，也不要默认把昂贵 password KDF 用作高吞吐 index hash。

针对不可信输入，engine 还需考虑 hash-flooding DoS；可能采用 keyed hash、collision limits 或 alternative structure。

Static hashing

固定 B buckets：

bucket = h(key) mod B

数据增长后 load factor/overflow 增大；一次性 rehash 全部 entries 会产生大 latency 与 I/O。预留过多 buckets 又浪费 directory/page space。

Extendible hashing

extendible hash 维护 directory depth d，使用 hash 的固定一侧 d bits 索引 2^d directory entries。每个 bucket 有 local depth l；多个 directory entries 可指向同一 bucket。

bucket full：

1. 若 l < d，split bucket、l += 1，重新分配其 entries，并更新相关 directory pointers；
2. 若 l == d，directory double、d += 1，再 split bucket；
3. retry insertion。

示意：

global depth = 2
00 -> A (local depth 1)
01 -> B (local depth 2)
10 -> A (local depth 1)
11 -> C (local depth 2)

上例使用最低位：00 与 10 的末位都是 0，因此共享 local depth 为 1 的 A。也可以另行设计使用最高位的目录，但那时共享 A 的应是 00 与 01，不能保持上图指针不变。

directory 可常驻 memory，但大 global depth、sparse distribution 与 persistence/concurrency 仍是成本。实现还会合并低 occupancy buckets 或收缩 directory，策略各异。

Linear hashing

linear hashing 不用一次 directory doubling，而用 level i 和 split pointer p 渐进 split buckets：

h_i(key) = h(key) mod (2^i * initial_buckets)
if bucket < p:
    use h_{i+1}(key)

每次按 split pointer 分裂一个 bucket，p 扫完整轮后 level 增加。它平滑扩容成本，但 lookup/metadata 与 overflow management 仍需实现。

Equality semantics

hash index 必须与 query operator 的 equality semantics 一致：

• data type canonicalization；
• collation/case sensitivity；
• numeric representations；
• NaN/-0 等边界；
• composite key 与 NULL；
• database operator class。

若 equality comparator 认为两个 values 相等，hash function 必须给它们兼容的 hash。否则 index 会漏结果。

SQL = 对 NULL 返回 UNKNOWN。IS NOT DISTINCT FROM/MySQL <=> 等 null-safe equality 是否能用某 hash index，取决于产品/operator support，不能从 hash structure 本身推出。

Duplicate 与 unique

non-unique hash bucket 可保存多个相同 key 的 record locators。unique hash index 在并发下必须原子检查“无现有可见/冲突 key”并插入；单纯先 lookup 再 insert 会 race。

uniqueness 是 correctness constraint，不能因为 table 小就删掉；是否由 hash/B-tree 实现是 physical choice。

Hash index、hash join、hash aggregation

• hash index：持久/内存 access path，从 key 找 rows；
• hash join：query operator，build 一侧 hash table、probe 另一侧；
• hash aggregation：按 group keys 建 hash table；
• application key-value hash map：进程内 data structure。

它们共享 hashing 概念，但 lifecycle、spill、durability、concurrency 与 semantics 不同。数据库执行 hash join 不要求 schema 上存在 hash index。

产品差异

PostgreSQL 的 hash index 支持 WAL 恢复和等值查找，但不支持唯一索引或多列索引。索引项只存哈希值和记录定位信息，需要回到 heap 复查实际相等性，不能据此提供 index-only scan；桶数量会随 split 增长。B-tree 的支持范围更广。MySQL MEMORY engine 支持 HASH/BTREE indexes，但 table durability、locking、data type 和容量边界由当前版本定义。

不要写“Redis 就是生产数据库 hash index 的替代”。Redis 是 networked data-structure server，持久化、eviction、replication 和 transaction model 与 relational index 完全不同。

官方资料：

• PostgreSQL Hash Indexes
• MySQL MEMORY Storage Engine

何时选择 ordered index

以下需求通常偏向 B+ tree：

• BETWEEN, <, >；
• ORDER BY / min/max；
• prefix/lexicographic scan；
• composite leading-key queries；
• range lock/predicate access；
• one index 同时服务 equality 与 range。

hash index 只有在 equality-heavy workload、engine implementation 成熟且 benchmark 证明收益时才值得额外 write/storage cost。

本课小结

哈希索引用 unordered mapping 换取 equality probe，实际代价由 collision、load factor、bucket I/O、result cardinality 与 equality semantics 决定。下一课处理完全相反的目标：在 memory 放不下时，仍生成全局有序结果。