69.2. 实现

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

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

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

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

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