受支持版本: 当前版本 (18) / 17 / 16 / 15 / 14
开发版本: devel

Chapter 67. 哈希索引

Table of Contents

67.1. 概述
67.2. 实现

67.1. 概述 #

PostgreSQL 提供了持久化的磁盘哈希索引实现,并且完全支持崩溃恢复。任何数据类型都可以使用哈希索引,包括那些没有明确定义线性顺序的数据类型。哈希索引只存储被索引数据的哈希值,因此对被索引数据列的大小没有限制。

哈希索引仅支持单列索引,也不支持唯一性检查。

哈希索引仅支持=操作符,因此指定范围操作的 WHERE 子句无法利用哈希索引。

每个哈希索引元组只存储 4 字节的哈希值,而不存储实际的列值。因此,在为 UUID、URL 等较长的数据项建立索引时,哈希索引可能比 B-树小得多。由于没有列值,所有哈希索引扫描也都是有损的。哈希索引可以参与位图索引扫描和反向扫描。

哈希索引最适合于在较大表上执行等值扫描、且以 SELECT 和 UPDATE 为主的工作负载。在 B-树索引中,搜索必须沿树向下直到找到叶页。在拥有数百万行的表中,这种向下遍历会增加访问数据的时间。在哈希索引中,与叶页对应的页称为桶页。相比之下,哈希索引允许直接访问桶页,因此可能减少大表中的索引访问时间。这种“逻辑 I/O”的减少,在索引/数据大于 shared_buffers/RAM 时会更加明显。

哈希索引在设计上能够应对哈希值分布不均的情况。如果哈希值分布均匀,那么直接访问桶页的效果很好。当插入导致桶页填满时,额外的溢出页就会链接到该特定桶页上,从而在局部扩展用于存放匹配该哈希值的索引元组的空间。查询期间扫描某个哈希桶时,需要遍历其全部溢出页。因此,对于某些数据,不平衡的哈希索引在所需块访问次数方面实际上可能比 B-树更差。

由于会出现这些溢出情况,可以说哈希索引最适合用于唯一值、近乎唯一值,或者每个哈希桶中行数较少的数据。 避免问题的一种可能办法,是使用部分索引条件把高度非唯一的值排除在索引之外,但这在很多情况下可能并不适用。

与 B-树一样,哈希索引也会执行简单的索引元组删除。这是一种延迟维护操作,用于删除那些已知可以安全删除的索引元组(即其项标识符的 LP_DEAD 位已经被设置的那些元组)。如果插入操作发现页上没有可用空间,我们会尝试通过移除死索引元组来避免创建新的溢出页。如果该页当时已被钉住,就无法执行移除。死索引指针也会在 VACUUM 期间被删除。

如果可能,VACUUM 还会尝试将索引元组压缩到尽可能少的溢出页上,以最小化溢出链。 如果某个溢出页变为空页,该溢出页就可以被回收并在其他桶中重用,不过我们从不将它们返还给操作系统。 目前除了使用 REINDEX 重建哈希索引之外,还没有缩小哈希索引的方法。 同样也没有减少桶数量的方法。

随着被索引行数的增长,哈希索引可能会扩展桶页数量。哈希键到桶号的映射经过选择,使得索引能够增量扩展。当需要向索引中添加一个新桶时,恰好只需要“拆分”一个现有桶,并根据更新后的键到桶号映射,将其中一部分元组转移到新桶。

这种扩展是在前台进行的,因此可能会增加用户插入操作的执行时间。因此,哈希索引可能不适合行数快速增长的表。

提交更正

如果您发现文档中有不正确的内容、与您使用特定功能的经验不符或需要进一步说明,请使用此表单来报告文档问题。