Postgresql 中文操作指南
72.2. Implementation #
哈希索引中有四种类型的页：存储静态分配的控制信息的元页（页面 0）；主存储桶页；溢出页；以及跟踪已释放并可供重新使用的溢出页的位图页。出于寻址目的，位图页被视为溢出页的子集。
There are four kinds of pages in a hash index: the meta page (page zero), which contains statically allocated control information; primary bucket pages; overflow pages; and bitmap pages, which keep track of overflow pages that have been freed and are available for re-use. For addressing purposes, bitmap pages are regarded as a subset of the overflow pages.
扫描索引和插入元组都需要找到一个给定元组应该所在的位置。为此，我们需要元页中的存储桶计数、highmask 和 lowmask；但是，出于性能原因，不希望为每次此类操作锁定和固定元页。相反，我们在每个后端的 relcache 条目中保留元页的缓存副本。只要目标存储桶在上次缓存刷新后没有被拆分，这将产生正确的存储桶映射。
Both scanning the index and inserting tuples require locating the bucket where a given tuple ought to be located. To do this, we need the bucket count, highmask, and lowmask from the metapage; however, it’s undesirable for performance reasons to have to have to lock and pin the metapage for every such operation. Instead, we retain a cached copy of the metapage in each backend’s relcache entry. This will produce the correct bucket mapping as long as the target bucket hasn’t been split since the last cache refresh.
主存储桶页和溢出页独立分配，因为任何给定的索引可能需要相对于其存储桶数更多或更少的溢出页。哈希码使用一组有趣的寻址规则来支持可变数量的溢出页，同时无需在创建主存储桶页后移动它们。
Primary bucket pages and overflow pages are allocated independently since any given index might need more or fewer overflow pages relative to its number of buckets. The hash code uses an interesting set of addressing rules to support a variable number of overflow pages while not having to move primary bucket pages around after they are created.
索引表中的每一行都由哈希索引中的单个索引元组表示。哈希索引元组存储在存储桶页（如果存在存储）中和溢出页中。我们通过按哈希码对任何索引页中的索引条目进行排序来加快搜索速度，从而可以在索引页内使用二分查找。但是，请注意，对存储桶的不同索引页中的哈希码的相对顺序存在 no 假设。
Each row in the table indexed is represented by a single index tuple in the hash index. Hash index tuples are stored in bucket pages, and if they exist, overflow pages. We speed up searches by keeping the index entries in any one index page sorted by hash code, thus allowing binary search to be used within an index page. Note however that there is no assumption about the relative ordering of hash codes across different index pages of a bucket.
扩展哈希索引的存储桶拆分算法过于复杂，不值得在此提及，尽管在 src/backend/access/hash/README 中以更详细的方式描述。拆分算法具有防崩溃功能，如果未成功完成，则可以重新启动。
The bucket splitting algorithms to expand the hash index are too complex to be worthy of mention here, though are described in more detail in src/backend/access/hash/README. The split algorithm is crash safe and can be restarted if not completed successfully.