哈希、倒排与位图索引

一句话定义

哈希索引用散列函数把键直接映射到桶，等值查询 O(1) 但天然不支持范围；倒排索引从「词 → 文档列表」反向组织文本检索；位图索引用每个取值一个位向量表示行归属，擅长低基数列的压缩与位运算聚合。

为什么重要

B+ 树不是唯一答案：Redis/KV 存储用哈希、搜索引擎与全文检索用倒排、数仓对状态列用位图——认识三者的能力边界才能看懂 NoSQL 图谱（kp-027）。
日常工程会「无意中」依赖它们：InnoDB 自适应哈希索引、PostgreSQL GIN 索引、ClickHouse 的位图函数，都在这三类结构之上。
理解「等值快、范围废」的哈希本质，就明白为什么内存 KV 库做不了排序分页的性价比之选。

前置知识

kp-009（B+ 树作为对照系）。

核心概念

哈希索引（Hash Index）：h(key) mod 桶数 定位；冲突用链地址或开放寻址解决；扩容需重哈希。
倒排索引（Inverted Index）：词典（Term Dictionary）+ 倒排表（Posting List，按 doc_id 排序）；词典常用 FST/跳表压缩。
位图索引（Bitmap Index）：值 v 的位图 B_v[i] = 1 表示第 i 行取值 v；多条件查询用按位与/或。
三者的核心差异维度：等值读、范围读、写放大、空间、并发结构。

原理与机制

哈希索引把键空间打散到桶，定位一步到位，但键的有序性被散列函数完全抹除，因此 BETWEEN、前缀匹配、排序全部退化为全扫；扩容（rehash）是批量重写，天然与在线服务冲突，工程上用增量扩容（新旧桶并存、渐进迁移）化解。倒排索引的写入流程是「分词 → 查词典 → 追加 doc_id 到倒排表」；查询「词 A AND 词 B」对两个有序倒排表做归并求交——列表按 doc_id 排序正是为了归并高效。位图索引的威力在组合谓词：gender='F' AND age=25 变成两个位向量的按位与，CPU 一次处理 64 行；但取值基数一高位图数量爆炸，因此只适合低基数列，且行级更新要改多个位图、写放大严重，OLTP 场景不用。

实例或案例

Redis 的 HSET/GET 是哈希索引的产品化：会话缓存按 key 秒级读取，但 KEYS 模式匹配需走 SCAN 全量迭代。
PostgreSQL 对 jsonb 与全文检索用 GIN（广义倒排索引）：WHERE doc @@ '数据库' 先查词典得 doc 列表再回表。
数仓对「订单状态」列建位图：state='paid' AND channel='app' 两个位向量按位与，十亿行毫秒级出命中数。

常见误区

给范围查询列建哈希索引：范围谓词完全用不上，应保留 B+ 树。
认为全文检索「LIKE '%x%' 也能做」：% 开头的 LIKE 无法走 B+ 树，中英文分词后走倒排才是正解。
在高基数列（用户 ID）上建位图：位图个数等于取值个数，空间爆炸且更新代价高，高基数等值场景应回 B+ 树或哈希。

自测题

哈希索引为什么无法支持 ORDER BY 优化？答：散列打散了键序，桶间无序、桶内也无序，有序输出必须额外排序，索引本身不提供任何顺序信息。
倒排表为什么按 doc_id 排序？答：多词查询的交/并/差用有序表归并即可线性完成，无需哈希探测；同时差分编码能大幅压缩存储。

公式或模型

哈希索引等值期望探测次数（链地址法、负载因子 α）：E ≈ 1 + α/2（成功查找）；位图 AND 的代价 ≈ ⌈N/字长⌉ 次按位运算，N 为行数——64 位字长下十亿行约 1560 万次字运算，SIMD 下毫秒级。

图示

本节不适用：三类结构都是「键 → 位置」的映射表，用文字与公式描述定位过程已足够精确。

直观类比

哈希索引像按「姓名首字母散列格」存快递：报姓名一步到位，但「取所有周三到的件」无能为力；倒排索引像图书馆的主题卡片柜：先查「数据库」卡片，卡片上列着所有相关书的编号；位图索引像考勤表：每个选项一行打孔位，两行重叠一眼看出都打了孔的人。

与其他知识点的关系

kp-009 是主对照结构；kp-021 中 LSM 的 memtable 就是一棵内存哈希/跳表结构；kp-027 的 KV/搜索/列存产品家族分别对应本篇三类索引；kp-013 说明优化器如何按谓词形状选索引类型。

前置知识点

相关知识点