72.2. 实现#

哈希索引中有四种类型的页面：元页面（页面 0），其中包含静态分配的控制信息；主存储桶页面；溢出页面；以及位图页面，用于跟踪已释放且可供重用的溢出页面。出于寻址目的，位图页面被视为溢出页面的子集。

扫描索引和插入元组都需要找到给定元组应该位于的存储桶。为此，我们需要从元页面中获取存储桶计数、高掩码和低掩码；但是，出于性能原因，不希望对每次此类操作都锁定并固定元页面。相反，我们在每个后端的 relcache 条目中保留元页面的缓存副本。只要目标存储桶自上次缓存刷新以来尚未拆分，这将生成正确的存储桶映射。

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

表中索引的每一行在哈希索引中由单个索引元组表示。哈希索引元组存储在存储桶页面中，如果存在，则存储在溢出页面中。我们通过按哈希码对任何一个索引页面中的索引条目进行排序来加快搜索速度，从而允许在索引页面内使用二分查找。但请注意，对于存储桶的不同索引页面中的哈希码的相对顺序，没有任何假设。

此处不值得提及用于扩展哈希索引的 bucket 分割算法，但会在src/backend/access/hash/README中进行更详细的描述。分割算法是防崩溃的，如果未成功完成，则可以重新启动。