ハッシュインデックスには4種類のページがあります。 静的に確保された制御情報を持つメタページ(ページ0)、主バケットページ、オーバーフローページ、解放されて再利用が可能なオーバーフローページを追跡するビットマップページ、です。 アドレッシング目的という点では、ビットマップページはオーバーフローページのサブセットと見なされます。
インデックスを操作すること、タプルを挿入することの両方には、与えられたタプルに位置づけられるべきバケットを特定する必要があります。 これを実施するためには、バケット数、メタページの上位マスク、下位マスクが必要です。 しかし、性能上の観点からは、そのような操作を行うたびにメタページをロックしてピンを立てるのは好ましいことではありません。 そうする代わりに、それぞれのバックエンドのリレーションキャッシュ(relcache)のエントリにキャッシュされたメタページの複製を保持します。 最後にキャッシュが更新された以降に目的のバケットが分割されていない限り、これは正しいバケットのマッピングを生成します。
与えられたインデックスにおいて、バケット数に対する必要な溢れページは多いかもしれないし少ないかもしれないので、主バケットページと溢れページは独立して確保されます。 ハッシュのコードは、作成後は主バケットページを動かす必要がなく、しかも可変数のオーバーフローページをサポートするために興味深いアドレス付規則を使用しています。
インデックス付されたテーブル内の各行はハッシュインデックスにおいては単一のインデックスタプルで表現されています。 ハッシュインデックスタプルはバケットページに格納され、オーバーフローページが存在するならそこにも存在します。 インデックスエントリをハッシュコードによりソートされた一つのインデックスページに保持し、一つのインデックスページ内での二分探索を可能にすることにより、探索を高速化しています。 しかし、バケット内の異なるインデックスページ間において、ハッシュコードの間に相対的な順序付けがあるという前提はないことに留意してください。
ハッシュインデックスを拡張するためにバケットを分割するアルゴリズムは複雑過ぎてここで言及するには及びませんが、より詳細がsrc/backend/access/hash/README
に記載されています。
分割アルゴリズムはクラッシュ耐性があり、正常に完了していなくても再スタートできます。