Postgresql 中文操作指南

72.2. Implementation #

哈希索引中有四种类型的页:存储静态分配的控制信息的元页(页面 0);主存储桶页;溢出页;以及跟踪已释放并可供重新使用的溢出页的位图页。出于寻址目的,位图页被视为溢出页的子集。

扫描索引和插入元组都需要找到一个给定元组应该所在的位置。为此,我们需要元页中的存储桶计数、highmask 和 lowmask;但是,出于性能原因,不希望为每次此类操作锁定和固定元页。相反,我们在每个后端的 relcache 条目中保留元页的缓存副本。只要目标存储桶在上次缓存刷新后没有被拆分,这将产生正确的存储桶映射。

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

索引表中的每一行都由哈希索引中的单个索引元组表示。哈希索引元组存储在存储桶页(如果存在存储)中和溢出页中。我们通过按哈希码对任何索引页中的索引条目进行排序来加快搜索速度,从而可以在索引页内使用二分查找。但是,请注意,对存储桶的不同索引页中的哈希码的相对顺序存在 no 假设。

扩展哈希索引的存储桶拆分算法过于复杂,不值得在此提及,尽管在 src/backend/access/hash/README 中以更详细的方式描述。拆分算法具有防崩溃功能,如果未成功完成,则可以重新启动。