PostgreSQLのB-Treeインデックスは複数階層のツリー構造で、ツリーの各階層はページの双方向連結リストとして使用できます。 一つのメタページがインデックスの最初のセグメントファイルの固定位置に格納されます。 それ以外の全てのページはリーフページか内部ページのいずれかです。 リーフページはツリーの最下階層にあるページです。 各リーフページはテーブルの行を指すタプルを含みます。 各内部ページはツリーの次の下位層を指すタプルを含みます。 典型的には、全ページの99％以上がリーフページです。 内部ページとリーフページは共に、70.6に記載されている標準のページ書式を使用します。

既存リーフページがやってくるタプルをはめ込むことができないとき、新たなリーフページがB-Treeインデックスに追加されます。 ページ分割操作は一部のアイテムを新ページに動かすことで、当初は溢れているページに属していたアイテムのために空間を作ります。 ページ分割は、また、新ページへの新たなダウンリンクを親ページに挿入しなければなりません。これは親ページの分割を同様に引き起こすかもしれません。 ページは分割は再帰的に「上向きに連鎖」します。 最終的にルートページが新たなダウンリンクをはめ込みできないときには、ルートページ分割が実施されます。 これは元のルートページの一つ上の階層に新たなルートページを作ることで、ツリー構造に新しい階層を加えます。

B-Treeインデックスは、MVCCの下で同じ論理テーブル行の複数の現存するバージョンが存在する可能性があることを直接認識していません。 インデックスに対して、各タプルは独自のインデックスエントリを必要とする独立したオブジェクトです。 「バージョンチャーン」タプルは蓄積し、クエリ待ち時間とスループットに悪影響を与える可能性があります。 これは通常、個々の更新のほとんどがHOT最適化を適用できないようなUPDATEの重いワークロードで発生します。 UPDATE中にあるインデックスによって、カバーされる一つだけの行の値を変更するには、新しいインデックスタプルのセットをいつも必要とします。 テーブル上にある ありとあらゆるインデックスにつき一つです。 具体的には、UPDATEによって「論理的に変更」されなかったインデックスが含まれることに注意してください。 すべてのインデックスは、テーブル上で最新バージョンを指す後継の物理的なインデックスタプルを必要とします。 各インデックス中のそれぞれの新しいタプルは通常元の「更新された」タプルと短期間共存する必要があります（通常、UPDATEトランザクションのコミットした直後までです）。

B-Treeインデックスは、ボトムアップインデックスの削除パスの実行によって、バージョンチャーンのインデックスタプルを徐々に削除します。 各削除パスは、予期された「バージョンチャーンのページ分割」に対してトリガーされます。 これは、UPDATE文によって論理的に変更されてないインデックスだけで発生します。 さもないと、特定のページで使われなくなったバージョンが集中的に蓄積されます。 ある種の実装レベルの発見的手法は、均一のごみインデックスタプルの特定及び削除に失敗する可能がありますが、ページの分割は通常避けることができます（ページ分割もしくは重複排除パスの場合に、リーフページ上の収まらない新しいタプルが入ることの問題が解決します）。 インデックススキャンが（単一の論理行に対して）通過しなければならない最悪の場合のバージョン数は、システム全体の応答性やスループットに重要な影響があります。 ボトムアップインデックス削除パスは、論理行とバージョンを含む定性的な特徴に基づいた単一のリーフページ内の疑わしいごみタプルを対象としています。 これは、一定の定量的なテーブルレベルの閾値が超えられたとき（25.1.6参照）に起動されるautovacuumワーカーによって実行された「トップダウン」インデックスのクリーンアップと対照的です。

ボトムアップインデックス削除は、明確なワークロードによる特定インデックスのすべてのゴミインデックスタプルの掃除の大多数を実行します。 これは、インデックスがカバーするカラムを論理的に変更することが滅多にまたは決してないUPDATEからの有意なバージョンチャーンに依存するB-Treeインデックスで予想されます。 論理行ごとのバージョン数の平均と最も悪いケースは、対象とされた増分削除パスによって純粋に低く維持することができます。 特定インデックスのディスク上のサイズは、UPDATEからの一定のバージョンチャーンがあるにも関わらず、ページやブロックが一つも増加することがない可能性が十分にあります。 そのような場合でも、VACUUM操作（通常、自動バキュームワーカプロセスで実行します）による、徹底的な「一掃」が、テーブルとその各インデックスの共通のクリーンアップの一部として最終的に要求されます。

VACUUMとは異なり、ボトムアップインデックス削除は最も古いゴミのインデックスタプルがどのくらい経過しているかについて強い保証を提供しません。 テーブルと全てのインデックスの合計によって共通する保守的な切り捨て点より前に、不要になる「浮いているゴミ」インデックスタプルの維持を許可することはできません。 この基本的なテーブルレベルの不変条件は、テーブルのTIDを安全にリサイクルします。 これにより、時間の経過と共に異なる論理行が同じテーブルTIDを再利用することが可能です（ただし、これは存続期間が同じVACUUMサイクルにまたがる、二つの論理行に同時には発生しません）。

重複とは、同じインデックスで全てのインデックスキー列が少なくとも一つの他のリーフページタプルの該当する列の値と一致する値をもっている、リーフページタプル（テーブルの行を指すタプル）です。 重複タプルは実際によくあります。 オプションの技法「重複排除」が有効にされているとき、B-Treeインデックスは、特別な重複に対する空間効率の良い表現方法を使用できます。

重複排除は重複タプルのグループを定期的に合併して、各グループに対する単一のポスティングリストタプルを形成することで機能します。 この表現方法では列のキー値は一度だけ現れます。 テーブルの行を指すTIDのソートされた配列がこれに続きます。 概して各値（あるいは列値の異なる組み合わせ）が複数回出現する場合に、これは顕著にインデックスの格納サイズを減らします。 問い合わせの遅延も顕著に削減できます。 全体的な問い合わせのスループットも顕著に増加するかもしれません。 インデックスのバキューム処理のオーバーヘッドも顕著に削減されるかもしれません。

既存のリーフページに収まらない新たな要素が挿入されたとき、重複排除の処理は怠惰に実行されますが、インデックスタプルの削除は新しいアイテムのための十分なスペースを解放できなかった場合に限ります（通常、削除は簡易に検討した上で無視されます）。 GINのポスティングリストのタプルと違って、B-Treeのポスティングリストのタプルは新たな重複が挿入される度に拡張する必要がありません。それらはリーフページの元の論理内容に対する単なる代替の物理表現にすぎません。 この設計は読み書き混合のワークロードでの性能の一貫性を重視しています。 ほとんどのクライアントアプリケーションは重複排除を使うことで少なくとも控えめな性能の恩恵を確認することができるでしょう。

CREATE INDEXとREINDEXは、使用する手順が若干異なりますが、ポスティングリストタプルを作って重複排除を適用します。 テーブルから取得されてソートされた入力で遭遇した重複した通常タプルの各グループは、現在のペンディングリーフページに追加される前に、ポスティングリストタプルにマージされます。 個別のポスティングリストタプルには、可能な限り多数のTIDが詰め込まれます。 リーフページは、重複排除用の別パスではなく、通常の方法で書き出されます。 この戦略はCREATE INDEXとREINDEXに良く適合します。これらは1回で終わるバッチ操作であるからです。

インデックスの値に重複が無いか殆ど無いために重複排除から利益を得られない、書き込みの多いワークロードには、（重複排除が明示的に無効化されて居ない限り）固定のペナルティによる小さい負荷増があります。 deduplicate_items格納パラメータは個別のインデックス内で重複排除を無効化するのに使うことができます。 ポスティングリストタプルの読み込みは少なくとも通常タプル表現の読み込み程度に効率的であるため、読み込みのみのワークロードで性能ペナルティは一切ありません 通常は重複排除を無効化することは有益ではありません。

一意性インデックス(や一意制約)が重複排除に使用できる場合があります。 これにより、リーフページは余分なバージョンチャーンの重複を一時的に「吸収」することができます。 一意性インデックス内の重複排除は、特に時間のかかるトランザクションがガベージコレクションを妨げるスナップショットを保持している場合にボトムアップインデックス削除を増強します。 目的は、ボトムアップインデックス削除の戦略が再び有効になるための時間を稼ぐことです。 一つの時間のかかるトランザクションが自然に消えるまでページ分割を遅らせることで、以前の削除パスが失敗した場所でボトムアップ削除パスを成功することができます。

実装レベルの制限により、重複排除は全ての場合に使えるわけではありません。 重複排除の安全性はCREATE INDEXあるいはREINDEXが実行されたときに決定されます。

等しいデータの間で意味的に明らかな違いを伴う以下の場合には、重複排除は安全でないと見做されて使用できないことに注意してください。

さらに以下の実装レベルの制限があります。これはPostgreSQLの将来バージョンで解消されるかもしれません。

さらに以下の実装レベルの制限があります。これは使われている演算子クラスや照合順序にかかわりなく該当します。