9.3 9.4 9.5 9.6 10 11 12 13 14 15 Current(16) 17
问题报告 纠错本页面

64.6. 哈希索引 #

64.6.1. 概述
64.6.2. 实现

64.6.1. 概述 #

PostgreSQL 包含永久性磁盘上的哈希索引的实现,这些索引可完全崩溃恢复。任何数据类型都可以通过哈希索引进行索引,包括没有明确定义线性排序的数据类型。哈希索引只存储被索引数据的哈希值,因此对被索引数据列的大小没有限制。

哈希索引仅支持单列索引并且不允许唯一性检查。

哈希索引仅支持=运算符,因此使用了范围操作的WHERE子句将无法利用哈希索引。

每个哈希索引元组只存储4字节的哈希值,而不是实际的列值。因此,当索引较长的数据项(如UUID、URL等)时,哈希索引可能比B树小得多。缺少列值也会使所有哈希索引扫描有损。哈希索引可以参与位图索引扫描和反向扫描。

哈希索引最适合于对较大表进行等值扫描的SELECT和UPDATE繁重工作负载。在B树索引中,搜索必须 通过树下降直到找到叶页。在拥有数百万行的表中,这种下降会增加对数据的访问时间。哈希索引中 叶页的等价物被称为桶页。相比之下,哈希索引允许直接访问桶页,从而可能减少较大表中的索引访问时间。 这种“逻辑I/O”的减少在大于shared_buffers/RAM的索引/数据上变得更加显著。

哈希索引被设计用于处理哈希值的不均匀分布。如果哈希值均匀分布,则直接访问桶页效果良好。当插入使得桶页变满时,额外的溢出页链接到该特定的桶页,本地扩展存储来容纳与该哈希值匹配的索引元组。在查询期间扫描哈希桶时,我们需要扫描所有溢出页。因此,就某些数据所需的块访问数而言,不平衡散列索引实际上可能比B树更差。

通过溢出情况得到的结论是,我们可以说哈希索引最适合于唯一、几乎唯一的数据或每个哈希桶的行数较少的数据。 避免问题的一种可能方法是使用部分索引条件从索引中排除高度非唯一的值,但这在许多情况下可能不适用。

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

如果可能的话,VACUUM还会尝试将索引元组挤压到尽可能少的溢出页上,最小化溢出链。 如果一个溢出页变为空,溢出页可以被回收重用在其他桶中,尽管我们从不将它们返回给操作系统。 目前没有任何方法来缩小哈希索引,除非通过使用REINDEX重新构建它。 也没有减少桶的数量的方法。

哈希索引可能会随着索引行数的增加而扩展桶页数。选择哈希键到桶号的映射,以便可以增量扩展索引。当一个新的桶要添加到索引中时,只需要“拆分”一个现有的桶,其中的一些元组将根据更新后的key到桶号的映射转移到新桶。

扩展发生在前端,这可能会增加用户插入的执行时间。因此,哈希索引可能不适用于行数快速增加的表。

64.6.2. 实现 #

哈希索引中有四种页面:元页面(零页),其中包含静态分配的控制信息;主桶页;溢出页;和位图页,它们跟踪已释放并可供重用的溢出页。出于寻址目的,位图页被视为溢出页的子集。

扫描索引和插入元组都需要定位给定元组应该位于的桶。为此,我们需要元页面中的桶计数、highmask和lowmask;然而,出于性能原因,必须为每个此类操作加锁和锁定元页是不可取的。相反,我们在每个后端的relcache条目中保留了元页面的缓存副本。只要目标桶自上次缓存刷新后未被拆分,这将生成正确的桶映射。

主桶页和溢出页是独立分配的,因为任何给定的索引相对于其桶的数量可能需要更多或更少的溢出页。哈希代码使用一组有趣的寻址规则来支持可变数量的溢出页,而不必在创建主桶页后四处移动。

索引表中的每一行由哈希索引中的单个索引元组表示。哈希索引元组存储在桶页中,如果存在,则存储在溢出页中。我们通过将任意一个索引页中的索引项按哈希代码排序来加快搜索速度,从而允许在索引页中使用二进制搜索。但是,请注意,对于一个桶的不同索引页上的哈希代码的相对排序,没有上述排序。

用于扩展哈希索引的桶分割算法过于复杂,不值得在此提及,下面有更详细的描述src/backend/access/hash/README。拆分算法是崩溃安全的,如果未成功完成,可以重新启动。