PostgreSQLは、標準的なbtree（multi-way balanced tree）インデックスデータ構造を実装しています。 明確に定義された線形順にソート可能なデータ型は、すべてbtreeインデックスで索引付できます。 唯一の制限は、一つのインデックスエントリが（適用可能であれば、TOAST圧縮後）ページの約1/3を超えられないことです。
btree演算子クラスはそのデータ型がソート順を持つことが必要なので、btree演算子クラス（実際には演算子族）は、PostgreSQLの一般的表現として、およびソートセマンティクスを理解するものとして利用されてきました。 ですから、単にbtreeインデックスをサポートするだけに必要なもの以上の機能と、btree AMが使用するものからはかけ離れたシステムの部品を備えなければなりません。
表 36.3で示すように、btree演算子クラスは次の5つの比較演算子を提供しなければなりません。
<、<=、=、>=、そして>です。
<>も演算子クラスの一部であると期待する方もいるかもしれませんが、そうではありません。
インデックス検索のWHERE句で<>を使うのは、ほとんど常に役に立たないからです。
（ある種の目的のためにプランナは<>をbtree演算子クラスに関連しているものとして扱います。
しかし、プランナはpg_amopから検索するのではなく=の否定子リンクから検索します。）
複数のデータ型がほとんど同じソートセマンティクスを共有している場合、それらの演算子クラスは演算子族にまとめることができます。 そうすることによりプランナが型をまたがる比較を推論できるので、これはメリットがあります。 演算子族内の各演算子クラスは、入力データ型のための単一型演算子（および関連するサポート関数）を含むべきです。 一方、型をまたがる比較演算子とサポート関数は演算子族中で「ゆるやか」です。 プランナが推移関係から推論するすべての比較条件を提示できるように、型をまたがる演算子の完全な集合を演算子族に入れておくことをお勧めします。
btree演算子族が満たさなければならない基本的な前提条件があります。
=演算子は等号関係でなければなりません。
つまり、そのデータ型のすべての非NULL値A、B、Cについて、
A = Aが真である（反射律）
A = Bなら、B = Aである（対称律）
A = BかつB= Cなら、A = Cである（推移律）
<は強順序関係でなければなりません。つまり、すべての非NULL値A、B、Cに対して、
A < Aは偽である（非反射律）
A < BかつB < Cなら、A < Cである（推移律）
更に、順序は全である。すなわち、すべての非NULL値A、Bに対して、
厳密にA < B、A = B、B < Aのうちどれか一つが真（三分律）
（もちろん、三分律は比較サポート関数の定義を正当化します。）
他の3つの演算子は=と<に沿って自明に定義され、それらと一貫していなければなりません。
複数のデータ型をサポートする演算子族について、演算子族中のデータ型であるどんなA、B、Cも上記の法則を満たさなければなりません。
型をまたがる場合、2つまたは3つの異なる演算子の動作が一貫している必要があるため、推移律を満たすことが最も困難です。
例をあげると、少なくともfloat8と比較するためにnumeric値をfloat8に変換する現在の意味論のもとでは、float8とnumericを同じ演算子族に加えるのはうまくいかないでしょう。
float8の精度に限りがあるからです。
これは同じfloat8値に対して等号比較する複数の異なるnumeric値が存在することを意味し、したがって推移律は満たされません。
複数データ型族に関する別な要件は、演算子族に含まれるデータ型間に定義される暗黙的あるいは二値型強制(binary-coercion)キャストは、関係するソート順を変更してはならないことです。
単一のデータ型において、btreeインデックスがこれらの法則を守ることを要求するのはかなり明確です。 これらの法則なしにはキー並べる順序がなくなってしまうからです。 また、異なるデータ型の比較キーを使うインデックス検索では、2つのデータ型またがる比較が正常に動作することが必要です。 演算子族中で3つ以上のデータ型に対する拡張はbtreeインデックスの機構自体では要求されませんが、プランナは最適化の目的でそれらに依存します。
表 36.9で示すように、btreeでは一つの必須サポート関数と、4つの省略可能なサポート関数を定義します。 5つのユーザ定義メソッドは以下の通りです。
order
btreeの演算子族が比較演算子を提供する各データ型の組み合わせに対して、比較サポート関数を提供しなければなりません。それらはサポート関数1番でpg_amprocに、また、比較での左右のデータ型と等しいamproclefttype/amprocrighttypeに、登録されます（すなわち、pg_amopに登録されている演算子が対応するものと同じデータ型です）。
比較関数は2つの非NULL値AとBを取り、
A < B、A = B、または、A > Bであるときにそれぞれ、< 0、0、または、> 0であるint32の値を返さなければなりません。
NULLを返すことは許されず、データ型の全ての値は比較可能でなければなりません。
例としてsrc/backend/access/nbtree/nbtcompare.cを参照してください。
比較される値が照合順序が適用可能なデータ型のものである場合、比較サポート関数に適切な照合順序のOIDが渡され、標準のPG_GET_COLLATION()機構が使用されます。
sortsupport
任意で、btree演算子族はソートサポート関数を提供してもよいです。これはサポート関数2番で登録されます。
この関数は、素朴に比較サポート関数を呼び出すよりも、ソート目的により効果的な方法での比較の実装を可能にします。
これに関するAPIはsrc/include/utils/sortsupport.hで定義されています。
in_range
任意で、btree演算子族はin_rangeサポート関数を提供してもよいです。これはサポート関数3番に登録されます。
これはbtreeインデックス操作中には使われません。そうではなく、演算子族のセマンティクスをRANGE offset PRECEDINGとRANGE offset FOLLOWINGフレーム境界タイプ（4.2.8を参照）を含むWINDOW句に対応できるように拡張します。
基本的には、提供される拡張情報はどのように演算子族のデータ並び順と互換性のある方法でoffset値を足すか引くかです。
in_range関数は以下のシグネチャを持たなければなりません。
in_range(valtype1,basetype1,offsettype2,subbool,lessbool) returns bool
valとbaseは同じ型でなければならず、これは演算子族でサポートされる型の一つ（すなわち、並び順を提供する対象の型）です。
しかしながら、offsetは異なる型のものでも可能です。それは演算子族でサポートされないものでもよいです。
例としては、組み込みのtime_ops族がinterval型のoffsetを持つin_range関数を提供しています。
演算子族は、任意のサポートされる型と一つまたは複数のoffset型に対するin_range関数を提供できます。
各in_range関数は、pg_amprocにtype1と等しいamproclefttypeとtype2に等しいamprocrighttypeで登録されるべきです。
in_range関数の本質的なセマンティクスは2つのBooleanフラグパラメータに依存します。
これは以下のように、baseにoffsetを加算または減算して、それからvalを結果と比較すべきです。
!subかつ
!lessであるなら、
val >=
(base +
offset)を返します
!subかつ
lessであるなら、
val <=
(base +
offset)を返します
subかつ
!lessであるなら、
val >=
(base -
offset)を返します
subかつ
lessであるなら、
val <=
(base -
offset)を返します
このように実行する前に、本関数は、offsetの符号を検査すべきです。
すなわち、負であったなら、エラーERRCODE_INVALID_PRECEDING_OR_FOLLOWING_SIZE(22013)、エラー文面としては「invalid preceding or following size in window function(ウィンドウ関数で先行または後続のサイズが不正です)」などを出すことです。
（意味上の必要性が乏しいと見られることから非標準の演算子族はこの制限を無視することを選ぶかもしれませんが、これは標準SQLで必要とされています。）
中核コードが特定のデータ型における「ゼロより小さい」ことの意味を理解しなくても良いように、この要件はin_range関数に委託されます。
さらに期待されることは、in_range関数は、実用的には、base + offsetやbase - offsetがオーバーフローする場合にエラーを投げるのを避けるべきです。
たとえ値がデータ型の範囲を超えたとしても正しい比較結果は決定できます。
データ型が「infinity」や「NaN」などの概念を含む場合には、in_rangeの結果が演算子族の通常のソート順序と一致するように特別な対応が必要となることに注意してください。
in_range関数の結果は、演算子族で規定されるソート順序と整合していなければなりません。
正確には、与えられた任意のoffsetとsubの固定値については以下のようになります。
less = trueのin_rangeがいくつかのval1とbaseに対して真であるなら、同じbaseの全てのval2 <= val1に対して真でなければなりません。
less = trueのin_rangeが、いくつかのval1とbaseに対して偽であるなら、同じbaseの全てのval2 >= val1に対して偽でなければなりません。
less = trueのin_rangeがいくつかのvalとbase1に対して真であるなら、同じvalの全てのbase2 >= base1に対して真でなければなりません。
less = trueのin_rangeが一部のvalとbase1に対して偽であるなら、同じvalの全てのbase2 <= base1に対して偽でなければなりません。
less = falseのときには、逆条件の類似した命題が適用できます。
整列しようとしている型(type1)が照合可能であるなら、標準のPG_GET_COLLATION()機構を使って、in_range関数に適切な照合順序のOIDが渡されます。
in_range関数は、通例STRICTと印付けされ、NULL入力を処理する必要がありません。
equalimage
省略可能ですが、btree演算子族はequalimage (「イメージ等価を意味する等価」)サポート関数を提供してもよいです。これはサポート関数4番で登録されます。
この関数は、中核コードがbtree重複排除の最適化を適用するのが安全かを決定できるようにします。
今のところ、equalimage関数はインデックスの構築または再構築時にのみ呼び出されます。
equalimage関数は以下のシグネチャを持たなければなりません。
equalimage(opcintypeoid) returns bool
戻り値は演算子クラスと照合順序についての静的な情報です。
trueを返すことは、AおよびB引数が何らセマンティック情報を損失すること無しに交換可能でもあるとき、演算子クラスに対するorder関数が0（「引数が等しい」）だけを返すことが保証されていることを示します。
equalimage関数が登録されていなかったり、falseを返すことは、この条件は守られないであろうことを示します。
opcintype引数は演算子クラスタがインデックスを作るデータ型のpg_type.oidequalimage関数を演算子クラスを横断して再利用できるようになる利便性があります。
opcintypeが照合可能なデータ型である場合には、適切な照合順序のOIDが、標準のPG_GET_COLLATION()機構を使って、equalimage関数に渡されます。
演算子クラスに関する限り、trueを返すことは、重複排除が安全（あるいはequalimage関数に渡されたOIDの照合順序について安全）であることを示します。
しかしながら、コアコードは、全てのインデックス列がequalimage関数を登録する演算子クラスを使っていて、各関数が呼ばれたとき実際にtrueを返すときに、そのインデックスに対して重複排除を安全と見做すだけです。
イメージ等価は単純にビット毎に等しいこととほとんど同じ条件です。
一点微妙な違いがあります。varlenaデータ型にインデックス作成するとき、入力時の一貫性のないTOAST圧縮の適用のために、同じdatumの二つのイメージのディスク上の表現はビット毎には等しくないかもしれません。
形式的には、演算子クラスのequalimage関数がtrueを返すときには、datum_image_eq() C関数が常に演算子クラスのorder関数と一致すると想定して安全でした（同じ照合順序のOIDがequalimageとorderの両関数に渡されるとして）。
コアコードは基本的に、複数データ型の族の中の演算子クラスの「等価性がイメージ等価性を含む」状態について、同族の他の演算子クラスの詳細に基づいた、いかなる推測もできません。
また、ある演算子族が型にまたがってequalimage関数を登録していることを認識できず、そのような試みはエラーになります。
これは「等価性がイメージ等価性を含む」状態は、演算子族の階層でおおむね定義されている、ソートと等価性のセマンティクスに依存しているだけでは無いためです。
一般に、ある特定データ型の実装によるセマンティクスは別個に考慮されなければなりません。
PostgreSQLのコア配布物に含まれる演算子クラスが従う慣習は、標準品、すなわち、一般的なequalimage関数を登録することです。
大部分の演算子クラスタはbtequalimage()を登録しています。これは重複排除が無条件に安全であることを示しています。
textなどの照合可能なデータ型に対する演算子クラスはbtvarstrequalimage()を登録します。これは決定的な照合順序では重複排除が安全であることを示します。
サードパーティ拡張におけるベストプラクティスは制御を保つためにそれら自身のカスタム関数を登録することです。
options
省略可能ですが、B-treeの演算子族はoptions（「演算子クラス固有オプション」）サポート関数を提供してもよいです。これはサポート関数5番に登録されます。
この関数はユーザに見える演算子クラスの振る舞いを制御するパラメータの集合を定義します。
optionsサポート関数は以下のシグネチャを持たなければなりません。
options(reloptslocal_relopts *) returns void
関数にはlocal_relopts構造体へのポインタが渡されます。ここには演算子クラス固有のオプションの集合が書かれている必要があります。
このオプションにはPG_HAS_OPCLASS_OPTIONS()およびPG_GET_OPCLASS_OPTIONS()マクロを使って他のサポート関数からアクセスが可能です。
今のところ、optionsサポート関数を持ったB-Treeの演算子クラスはありません。
B-treeはGiST、SP-GiST、GINおよびBRINで行われているような柔軟なキーの表現を許していません。
そのため、おそらくはoptionsが現在のB-treeインデックスアクセスメソッドで多数適用されることはありません。
それでも、統一性のためにサポート関数がB-treeに追加されました。おそらくPostgreSQLでのB-treeの更なる進化の過程で使用法を見つけ出すでしょう。
本節では、上級ユーザに役立つかもしれない、B-Treeインデックスの実装の詳細について説明します。
更なる詳細、B-Tree実装の内部に焦点をあてた記述については、ソース配布物のsrc/backend/access/nbtree/READMEを参照してください。
PostgreSQLのB-Treeインデックスは複数階層のツリー構造で、ツリーの各階層はページの双方向連結リストとして使用できます。 一つのメタページがインデックスの最初のセグメントファイルの固定位置に格納されます。 それ以外の全てのページはリーフページか内部ページのいずれかです。 リーフページはツリーの最下階層にあるページです。 それ以外の全ての階層は内部ページで構成されます。 各リーフページはテーブルの行を指すタプルを含みます。 各内部ページはツリーの次の下位層を指すタプルを含みます。 典型的には、全ページの99％以上がリーフページです。 内部ページとリーフページは共に、65.6に記載されている標準のページ書式を使用します。
既存リーフページがやってくるタプルをはめ込むことができないとき、新たなリーフページがB-Treeインデックスに追加されます。 ページ分割操作は一部のアイテムを新ページに動かすことで、当初は溢れているページに属していたアイテムのために空間を作ります。 ページ分割は、また、新ページへの新たなダウンリンクを親ページに挿入しなければなりません。これは親ページの分割を同様に引き起こすかもしれません。 ページは分割は再帰的に「上向きに連鎖」します。 最終的にルートページが新たなダウンリンクをはめ込みできないときには、ルートページ分割が実施されます。 これは元のルートページの一つ上の階層に新たなルートページを作ることで、ツリー構造に新しい階層を加えます。
B-Treeインデックスは、MVCCの下で同じ論理テーブル行の複数の現存するバージョンが存在する可能性があることを直接認識していません。
インデックスに対して、各タプルは独自のインデックスエントリを必要とする独立したオブジェクトです。
「バージョンチャーン」タプルは蓄積し、クエリ待ち時間とスループットに悪影響を与える可能性があります。
これは通常、個々の更新のほとんどがHOT最適化を適用できないようなUPDATEの重いワークロードで発生します。
UPDATE中にあるインデックスによって、カバーされる一つだけの行の値を変更するには、新しいインデックスタプルのセットをいつも必要とします。
テーブル上にある ありとあらゆるインデックスにつき一つです。
具体的には、UPDATEによって「論理的に変更」されなかったインデックスが含まれることに注意してください。
すべてのインデックスは、テーブル上で最新バージョンを指す後継の物理的なインデックスタプルを必要とします。
各インデックス中のそれぞれの新しいタプルは通常元の「更新された」タプルと短期間共存する必要があります（通常、UPDATEトランザクションのコミットした直後までです）。
B-Treeインデックスは、ボトムアップインデックスの削除パスの実行によって、バージョンチャーンのインデックスタプルを徐々に削除します。
各削除パスは、予期された「バージョンチャーンのページ分割」に対してトリガされます。
これは、UPDATE文によって論理的に変更されてないインデックスだけで発生します。
さもないと、特定のページで使われなくなったバージョンが集中的に蓄積されます。
ある種の実装レベルの発見的手法は、均一のごみインデックスタプルの特定及び削除に失敗する可能がありますが、ページの分割は通常避けることができます（ページ分割もしくは重複排除パスの場合に、リーフページ上の収まらない新しいタプルが入ることの問題が解決します）。
インデックススキャンが（単一の論理行に対して）通過しなければならない最悪の場合のバージョン数は、システム全体の応答性やスループットに重要な影響があります。
ボトムアップインデックス削除パスは、論理行とバージョンを含む定性的な特徴に基づいた単一のリーフページ内の疑わしいごみタプルを対象としています。
これは、一定の定量的なテーブルレベルの閾値が超えられたとき（24.1.6参照）に起動されるautovacuumワーカーによって実行された「トップダウン」インデックスのクリーンアップと対照的です。
B-Treeインデックス内で実行されたすべての削除操作がボトムアップ削除操作とは限りません。
インデックスタプルの削除の異なる分類があります。
それは、単純なインデックスのタプル削除です。
これは、削除が安全であると分かるインデックスタプル(アイテム識別子のLP_DEADビットが既に設定されているタプル)を削除する遅延メンテナンス操作です。
ボトムアップインデックス削除と同様に、単純インデックス削除は分割を回避する方法としてページ分割が予測された時点で実行されます。
単純削除は、最近のインデックススキャンでは影響があるアイテムにLP_DEADビットをセットする際に、ついでに実行できる機会の場合のみに実行されるという意味で、機会主義と言えます。
PostgreSQL 14より前では、B-Treeの削除の種類は単純な削除のみでした。
単純な削除とボトムアップ削除の主な違いは、前者だけがインデックススキャンの動きによって機会を狙って駆動されることに対して、後者だけがインデックスカラムが論理的に変更されないUPDATEからのバージョンチャーンを具体的に対象とすることです。
ボトムアップインデックス削除は、明確なワークロードによる特定インデックスのすべてのゴミインデックスタプルの掃除の大多数を実行します。
これは、インデックスがカバーするカラムを論理的に変更することが滅多にまたは決してないUPDATEからの有意なバージョンチャーンに依存するB-Treeインデックスで予想されます。
論理行ごとのバージョン数の平均と最も悪いケースは、対象とされた増分削除パスによって純粋に低く維持することができます。
特定インデックスのディスク上のサイズは、UPDATEからの一定のバージョンチャーンがあるにも関わらず、ページやブロックが一つも増加することがない可能性が十分にあります。
そのような場合でも、VACUUM操作（通常、自動バキュームワーカープロセスで実行します）による、徹底的な「一掃」が、テーブルとその各インデックスの共通のクリーンアップの一部として最終的に要求されます。
VACUUMとは異なり、ボトムアップインデックス削除は最も古いゴミのインデックスタプルがどのくらい経過しているかについて強い保証を提供しません。
テーブルと全てのインデックスの合計によって共通する保守的な切り捨て点より前に、不要になる「浮いているゴミ」インデックスタプルの維持を許可することはできません。
この基本的なテーブルレベルの不変条件は、テーブルのTIDを安全にリサイクルします。
これにより、時間の経過と共に異なる論理行が同じテーブルTIDを再利用することが可能です（ただし、これは存続期間が同じVACUUMサイクルにまたがる、二つの論理行に同時には発生しません）。
重複とは、同じインデックスで全てのインデックスキー列が少なくとも一つの他のリーフページタプルの該当する列の値と一致する値をもっている、リーフページタプル（テーブルの行を指すタプル）です。 重複タプルは実際によくあります。 オプションの技法「重複排除」が有効にされているとき、B-Treeインデックスは、特別な重複に対する空間効率の良い表現方法を使用できます。
重複排除は重複タプルのグループを定期的に合併して、各グループに対する単一のポスティングリストタプルを形成することで機能します。 この表現方法では列のキー値は一度だけ現れます。 テーブルの行を指すTIDのソートされた配列がこれに続きます。 概して各値（あるいは列値の異なる組み合わせ）が複数回出現する場合に、これは顕著にインデックスの格納サイズを減らします。 問い合わせの遅延も顕著に削減できます。 全体的な問い合わせのスループットも顕著に増加するかもしれません。 インデックスのバキューム処理のオーバーヘッドも顕著に削減されるかもしれません。
B-Tree重複排除は、B-Tree演算子クラスの=項に従ってNULL値が決して互いに等しくならないとしても、NULL値を含む「重複」に対しても同様に効果的です。
ディスク上のB-Tree構造を理解するいかなる実装部分に関しても、NULLはインデックス値の定義域からの他の値に過ぎません。
既存のリーフページに収まらない新たな要素が挿入されたとき、重複排除の処理は怠惰に実行されますが、インデックスタプルの削除は新しいアイテムのための十分なスペースを解放できなかった場合に限ります（通常、削除は簡易に検討した上で無視されます）。 GINのポスティングリストのタプルと違って、B-Treeのポスティングリストのタプルは新たな重複が挿入される度に拡張する必要がありません。それらはリーフページの元の論理内容に対する単なる代替の物理表現にすぎません。 この設計は読み書き混合のワークロードでの性能の一貫性を重視しています。 ほとんどのクライアントアプリケーションは重複排除を使うことで少なくとも控えめな性能の恩恵を確認することができるでしょう。 重複排除はデフォルトで有効になっています。
CREATE INDEXとREINDEXは、使用する手順が若干異なりますが、ポスティングリストタプルを作って重複排除を適用します。
テーブルから取得されてソートされた入力で遭遇した重複した通常タプルの各グループは、現在のペンディングリーフページに追加される前に、ポスティングリストタプルにマージされます。
個別のポスティングリストタプルには、可能な限り多数のTIDが詰め込まれます。
リーフページは、重複排除用の別パスではなく、通常の方法で書き出されます。
この戦略はCREATE INDEXとREINDEXに良く適合します。これらは1回で終わるバッチ操作であるからです。
インデックスの値に重複が無いか殆ど無いために重複排除から利益を得られない、書き込みの多いワークロードには、（重複排除が明示的に無効化されて居ない限り）固定のペナルティによる小さい負荷増があります。
deduplicate_items格納パラメータは個別のインデックス内で重複排除を無効化するのに使うことができます。
ポスティングリストタプルの読み込みは少なくとも通常タプル表現の読み込み程度に効率的であるため、読み込みのみのワークロードで性能ペナルティは一切ありません。
通常は重複排除を無効化することは有益ではありません。
一意性インデックス（や一意性制約）が重複排除に使用できる場合があります。 これにより、リーフページは余分なバージョンチャーンの重複を一時的に「吸収」することができます。 一意性インデックス内の重複排除は、特に時間のかかるトランザクションがガベージコレクションを妨げるスナップショットを保持している場合にボトムアップインデックス削除を増強します。 目的は、ボトムアップインデックス削除の戦略が再び有効になるための時間を稼ぐことです。 一つの時間のかかるトランザクションが自然に消えるまでページ分割を遅らせることで、以前の削除パスが失敗した場所でボトムアップ削除パスを成功することができます。
一意性インデックスで重複排除パスを実行すべきかどうかの判断には、特別なヒューリスティックが適用されます。
これは、しばしばリーフページ分割まで連続してスキップして、無益な重複排除パスでの無駄なサイクルによる性能ペナルティを回避できます。
重複排除のオーバーヘッドを懸念するなら、選択的に設定deduplicate_items = offを検討してください。
一意性インデックスで重複排除を有効にしておいてもほとんどデメリットはありません。
実装レベルの制限により、重複排除は全ての場合に使えるわけではありません。
重複排除の安全性はCREATE INDEXあるいはREINDEXが実行されたときに決定されます。
等しいデータの間で意味的に明らかな違いを伴う以下の場合には、重複排除は安全でないと見做されて使用できないことに注意してください。
非決定的な照合順序が使われているときtext、varchar、および、charは重複排除を使えません。
等しいデータの間で大文字小文字やアクセントの違いが維持されなければなりません。
numericは重複排除を使えません。
等しいデータの間で数の表示スケールが維持されなければなりません。
jsonbのB-Tree演算子クラスは内部的にnumericを使っているため、jsonbは重複排除を使えません。
float4およびfloat8は重複排除を使えません。
これらの型は-0と0に異なる表現を持ち、にもかかわらずこれらは等しいと見做されます。
この違いは維持されなければなりません。
さらに以下の実装レベルの制限があります。これはPostgreSQLの将来バージョンで解消されるかもしれません。
コンテナ型（複合型、配列型、あるいは、範囲型など）は、重複排除を使えません。
さらに以下の実装レベルの制限があります。これは使われている演算子クラスや照合順序にかかわりなく該当します。
INCLUDEインデックスには重複排除は使えません。