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. ハッシュインデックスには4種類のページがあります。 静的に確保された制御情報を持つメタページ(ページ0)、主バケットページ、オーバーフローページ、解放されて再利用が可能なオーバーフローページを追跡するビットマップページ、です。 アドレッシング目的という点では、ビットマップページはオーバーフローページのサブセットと見なされます。

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. インデックスを操作すること、タプルを挿入することの両方には、与えられたタプルに位置づけられるべきバケットを特定する必要があります。 これを実施するためには、バケット数、メタページの上位マスク、下位マスクが必要です。 しかし、性能上の観点からは、そのような操作を行うたびにメタページをロックしてピンを立てるのは好ましいことではありません。 そうする代わりに、それぞれのバックエンドのリレーションキャッシュ(relcache)のエントリにキャッシュされたメタページの複製を保持します。 最後にキャッシュが更新された以降に目的のバケットが分割されていない限り、これは正しいバケットのマッピングを生成します。

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. 与えられたインデックスにおいて、バケット数に対する必要な溢れページは多いかもしれないし少ないかもしれないので、主バケットページと溢れページは独立して確保されます。 ハッシュのコードは、作成後は主バケットページを動かす必要がなく、しかも可変数のオーバーフローページをサポートするために興味深いアドレス付規則を使用しています。

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. インデックス付されたテーブル内の各行はハッシュインデックスにおいては単一のインデックスタプルで表現されています。 ハッシュインデックスタプルはバケットページに格納され、オーバーフローページが存在するならそこにも存在します。 インデックスエントリをハッシュコードによりソートされた一つのインデックスページに保持し、一つのインデックスページ内での二分探索を可能にすることにより、探索を高速化しています。 しかし、バケット内の異なるインデックスページ間において、ハッシュコードの間に相対的な順序付けがあるという前提はないことに留意してください。

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 <filename>src/backend/access/hash/README</filename>. The split algorithm is crash safe and can be restarted if not completed successfully. ハッシュインデックスを拡張するためにバケットを分割するアルゴリズムは複雑過ぎてここで言及するには及びませんが、より詳細がsrc/backend/access/hash/READMEに記載されています。 分割アルゴリズムはクラッシュ耐性があり、正常に完了していなくても再スタートできます。