本文为摘录，原文为： ../../../Work/pg_master/src/backend/access/hash/README
1 Hash Indexing
这个目录包含了 Postgres 的散列索引实现。其中大部分核心思想来自于 Margo Seltzer 和 Ozan Yigit 在 1991 年 1 月举行的冬季 USENIX 会议上的论文《A New Hashing Package for UNIX》。我们 的内存哈希表实现（src/backend/utils/hash/dynahash.c）也依赖于相同的概念；它源自于 Esmond Pitt 编写的代码，后来又由 Margo 和其他人进行了改进。
哈希索引由两个或更多“桶”组成，每当元组的哈希键映射到桶号时，就将其放入其中一个桶中。选择 键到桶号的映射，以便可以增量扩展索引。当要向索引中添加新桶时，必须“拆分”一个现有的桶，将 其中一些元组根据更新的键到桶号映射转移到新桶中。这与 src/backend/utils/hash/dynahash.c 中的内存哈希表管理技术本质上相同。
哈希索引中的每个桶包含一个或多个索引页面。当创建桶时，该桶的第一个页面被永久分配给它。如 果桶接收的元组过多，无法放入主桶页面中，则添加附加页面（称为“溢出页面”）。桶的页使用索引 页面特殊空间中的字段作为双向链表链接在一起。
目前不存在缩小哈希索引的方法，除非使用 REINDEX 重新构建它。可以重新利用溢出页面以在其他 桶中重用，但我们永远不会将它们返回到操作系统。也没有减少桶数的方法。
截至 PostgreSQL 8.4，哈希索引条目仅存储每个索引项的哈希代码，而不是实际的数据值。这使得 索引条目更小（可能非常大），并加速了各种操作。特别是，我们可以通过将任何一个索引页面中的 索引条目按哈希码排序来加快搜索速度，从而在索引页面内使用二进制搜索。但请注意，对于同一桶 的不同索引页面之间的哈希码相对排序没有任何假设。
2 Page Addressing
哈希索引中有四种页面：
- 元页面（第 0 页），其中包含静态分配的控制信息；
- 主桶页面；
- 溢出页面；
- 位图页面，它们跟踪已被释放且可供重新使用的溢出页面。
为 addressing purposes，位图页面 被认为是溢出页面的子集。
主桶页面和溢出页面是独立分配的（因为任何给定的索引可能相对于其桶的数量需要更多或更少的溢 出页面）。哈希码使用一组有趣的 addressing rules 来支持可变数量的溢出页面，而不必在创建主 桶页面后移动它们。
主桶页面（以下简称“桶页面”）以 2 的幂组分配，称为代码中的 “分割点” 。这意味着每次新的 分割点时，我们都会将现有的桶数加倍。一次性分配大量桶页面并不理想，我们需要很长时间才能消 耗它们。
为避免指数级增长的索引大小，我们使用了一个技巧，将分割点处的桶分配拆分为 4 个相等的阶段。 如果（2 ^ x）是要在分割点分配的总桶数（从现在开始我们将其称为分割点组），则在分割点组的 每个阶段中分配总桶数的 1/4（2 ^（x-2））。下一四分之一的分配只会发生在之前的一相桶已经被 消耗完了。对于初始分割点组 < 10，我们将仅在单个阶段中分配它们的所有桶，因为初始组分配的 桶数很少。对于组 >= 10，分配过程分为四个相等阶段。在组 10 中，我们将 4 个不同阶段（{2 ^ 7，2 ^ 7，2 ^ 7，2 ^ 7}）分配了（2 ^ 9）个桶，括号中的数字表示分割点组的每个阶段分配的桶 数 10。对于分割点组 11 和 12，分配阶段将分别为{2 ^ 8，2 ^ 8，2 ^ 8，2 ^ 8}和{2 ^ 9，2 ^ 9，2 ^ 9，2 ^ 9}。我们可以看到，在每个分割点组中，我们将前一个组中桶的总数加倍，但是在增 量阶段中完成。同一分割点组中分配的 bucket 页面将依次出现在索引中。这种 addressing scheme 允许相对轻松地通过使用仅少量的控制信息将桶页面的物理位置从桶号计算出来。如果我们看一下给 定的桶号的函数 _hash_spareindex，我们首先计算它所属的分割点组，然后计算桶所属的阶段。将 它们加起来我们得到桶所属的全局分割点阶段号 S，然后只需添加“hashm_spares[S] + 1”（其中 hashm_spares[] 是存储在元页面中的数组）就可以计算其物理地址。hashm_spares [S] 可以解释为 已分配分割点阶段 S 的 bucket 页面之前分配的溢出页面的总数。hashm_spares [0] 始终为 0，因 此桶 0 和 1 总是出现在元页后的块编号 1 和 2 中。我们始终有 hashm_spares [N] <= hashm_spares [N