MIT Notes by Ron

中文

English

中文

English

Appearance

PostgreSQL 索引 — 3（Hash 索引） ​

原文：https://habr.com/en/companies/postgrespro/articles/442776/ （作者 Egor Rogov，PostgresPro）

写在前面 ​

从这一篇开始，系列文章正式进入具体索引类型的讲解，第一个登场的是概念上最简单的 Hash 索引。它只支持等值查询，但原理直观、结构简单，非常适合用来热身，为后面理解更复杂的 B-tree、GiST 等打基础。

哈希函数是什么 ​

哈希索引的核心是一个哈希函数：它把任意类型、任意大小的值映射到一个较小的整数范围（0 到 N-1，一共 N 个可能值）。这解决了一个现实问题——像文本字符串这样的数据类型理论上有近乎无限种可能取值，但我们希望用一个有限、紧凑的数字空间去组织和检索它们。

一个"好"的哈希函数应该让不同的输入尽可能均匀地散布到整个输出区间，而不是扎堆到少数几个桶里。但无论函数设计得多好，哈希碰撞（不同的原始值算出相同的哈希结果）都是理论上无法完全避免的，因为输入空间通常远大于输出空间。

PostgreSQL 内置的哈希函数返回一个 32 位整数（大约 2³² ≈ 40 亿种可能取值）。举例来说：

sql
select hashtext('one');
-- 结果: 127722028

select hashtext('two');
-- 结果: 345620034

索引里存的是什么 ​

哈希索引存储的是"哈希值 —— TID"这样的键值对，而不是原始数据本身。插入一行时，PostgreSQL 大致做这几件事：

  1. 对被索引的键值计算哈希函数；
  2. 通过对哈希结果做位运算，推算出这个值应该落在哪个"桶"（bucket）里；
  3. 只把哈希值本身（而不是原始键）连同 TID 一起存进对应的桶，这样能节省存储空间；
  4. 桶内的哈希值-TID 对会按一定顺序组织，方便快速查找。

正因为索引里存的只是哈希值而非原始值，检索到候选 TID 后，PostgreSQL 还必须回表把原始行取出来，重新核对原始条件是否真的成立——这一步是为了排除哈希碰撞带来的"假阳性"匹配。

页面结构 ​

一个哈希索引由四类页面组成：

  • 元页面（meta page）：始终是 0 号页，存放整个索引的元信息（比如当前桶的数量等）；
  • 桶页面（bucket page）：真正存放"哈希值-TID"数据对的主力页面，每个桶对应一段哈希值区间；
  • 溢出页面（overflow page）：当一个桶里的数据装不下一个页面时，用溢出页面链接扩容，其内部结构和桶页面完全一样；
  • 位图页面（bitmap page）：跟踪记录哪些溢出页面当前是空闲、可以被复用的。

当索引需要扩容时（桶数量不够用了），PostgreSQL 会"瞬间把桶的数量翻倍"——一次性创建和之前数量相当的新桶（也就是页面数量翻倍）。这种粗暴的加倍策略在 PostgreSQL 10 之前会造成扩容时的明显性能抖动；从版本 10 开始，PostgreSQL 引入了更平滑的分裂机制，让桶的增长不再是一次性剧烈翻倍，而是逐步进行。

示例：建索引与查询 ​

sql
create index on flights using hash(flight_no);

explain (costs off) select * from flights where flight_no = 'PG0001';

对应的执行计划呈现为典型的"位图堆扫描（Bitmap Heap Scan）套位图索引扫描（Bitmap Index Scan）"结构——先从哈希索引里拿到候选 TID 集合的位图，再据此去表里批量取行。

用 pageinspect 扩展可以直接窥探索引内部：

sql
create extension pageinspect;

select hash_page_type(get_raw_page('flights_flight_no_idx',0));
-- 结果: metapage

select ntuples, maxbucket
from hash_metapage_info(get_raw_page('flights_flight_no_idx',0));
-- 示例结果: ntuples=33121, maxbucket=127

maxbucket 反映了当前索引已经扩容到的桶编号上限，ntuples 则是索引里存储的行数。

哈希函数与操作符族的绑定关系 ​

哈希索引不仅服务于索引本身，它选用的哈希函数还会被 PostgreSQL 其他需要"哈希语义"的场景复用——比如哈希连接（hash join）、哈希聚合（hash aggregate/GROUP BY）等。这意味着"某个数据类型该用哪个哈希函数"这件事，是通过操作符族统一登记的，而不是各处各写各的：

sql
select   opf.opfname as opfamily_name,
         amproc.amproc::regproc AS opfamily_procedure
from     pg_am am,
         pg_opfamily opf,
         pg_amproc amproc
where    opf.opfmethod = am.oid
and      amproc.amprocfamily = opf.oid
and      am.amname = 'hash'
order by opfamily_name, opfamily_procedure;

比如 text_ops 这个操作符族就关联着 hashtext 这个具体函数。这种设计让新增数据类型的哈希支持变得统一、可插拔，而不需要在数据库各个用到哈希语义的模块里分别硬编码。

能力边界 ​

只支持等值查询 ​

由于哈希函数从设计上就会破坏原始值之间的顺序关系（相邻的原始值哈希后可能天差地别），哈希索引只能用来加速 = 等值查询，完全无法支持范围查询、排序或前缀匹配。

不支持的特性一览 ​

对照上一篇讲到的属性框架，哈希索引在多个维度上都是"不支持"：

  • can_order（排序能力）：不支持，哈希索引没有任何有意义的顺序；
  • 唯一约束：不支持，不能用哈希索引实现 UNIQUE 或主键；
  • 多列索引：不支持，只能对单个字段/表达式建哈希索引；
  • 仅索引扫描（index-only scan）：不支持，因为索引里只存了哈希值，并没有存原始键值,无法仅凭索引内容还原出原始数据来满足查询;
  • NULL 处理：由于"等于"这个操作对 NULL 本身语义未定义（NULL 不等于任何值，包括它自己），哈希索引对 NULL 的支持是缺失的；
  • 反向扫描（backward scan）：不支持。

历史遗留问题：WAL 日志 ​

在 PostgreSQL 10 之前，哈希索引有一个相当严重的历史缺陷——不记录 WAL（预写日志）。这直接带来两个后果：

  • 数据库崩溃后无法可靠恢复哈希索引的内容，只能重建；
  • 哈希索引不参与流复制,主备之间无法同步哈希索引数据。

正因如此，早期版本的官方文档明确建议"不鼓励使用哈希索引"。这个问题在 PostgreSQL 10 中被彻底解决——哈希索引获得了完整的 WAL 支持，性能也经过重新设计得到大幅提升，此后哈希索引才真正成为一个在生产环境中可用的选项（当然仅限于等值查询场景）。

空间无法自动收缩 ​

原文特别指出一个容易被忽视的运维细节：哈希索引的物理体积不会自动缩小。即便大量删除了索引对应的行，被释放的页面也不会归还给操作系统，只有在后续 VACUUM 过程中，这些空闲页面才可能被复用给新插入的数据。如果想彻底把索引文件压缩回真实需要的大小，必须显式执行 REINDEX 或 VACUUM FULL。

小结 ​

Hash 索引的设计目标非常单一：极致优化等值查询。它把原始键压缩成哈希值存储,通过桶和溢出页面的结构组织数据,换来的是紧凑的存储和 O(1) 量级的等值查找,但代价是彻底放弃了排序、范围查询、多列组合、仅索引扫描等能力,并且早期版本因缺乏 WAL 支持而不建议在生产环境使用。自 PostgreSQL 10 起,随着 WAL 日志和平滑扩容机制的引入,哈希索引才摆脱了"鸡肋"的历史包袱,成为在纯等值查询场景下,相较 B-tree 更紧凑、有时更快的可用选项。后续文章将转向功能更全面、结构也更复杂的 B-tree 索引。