PostgreSQL 包含標準btree(多路平衡樹) 索引資料結構的實現。任何可以排序成明確定義的線性順序的資料型別都可以透過 btree 索引進行索引。唯一的限制是索引項不能超過大約一頁的三分之一（在應用 TOAST 壓縮後，如果適用）。
由於每個 btree 運算子類都對其資料型別施加了一個排序順序，因此 btree 運算子類（或者更確切地說，運算子族）已成為 PostgreSQL 表示和理解排序語義的通用表示。因此，它們獲得了一些超出僅支援 btree 索引所需的功能，並且系統中一些遠離 btreeAM的部分會使用它們。
如表 36.3 所示，一個 btree 運算子類必須提供五個比較運算子：<、<=、=、>= 和 >。有人可能會期望 <> 也應該作為運算子類的一部分，但事實並非如此，因為在索引搜尋中使用 <> 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（三分律）
（三分律當然證明了比較支援函式的定義。）
其他三個運算子以顯而易見的方式根據 = 和 < 定義，並且必須與它們保持一致。
對於支援多種資料型別的運算子族，上述定律必須在 A、B、C 來自族中任何資料型別時成立。傳遞定律是最難確保的，因為在跨型別情況下，它們表示兩個或三個不同運算子的行為是一致的。例如，將 float8 和 numeric 放入同一個運算子族中是行不通的，至少在當前將 numeric 值轉換為 float8 以便與 float8 進行比較的語義下是行不通的。由於 float8 的精度有限，這意味著存在不同的 numeric 值將與同一個 float8 值比較相等，因此傳遞定律會失敗。
多資料型別族還有一個要求是，運算子族中包含的資料型別之間定義的任何隱式或二進位制強制轉換都不得改變相關的排序順序。
對於 btree 索引來說，需要這些定律在單個數據型別內成立是相當清楚的：沒有它們，就沒有可以排列鍵的順序。另外，使用不同資料型別的比較鍵進行索引搜尋要求比較在兩種資料型別之間表現得合理。擴充套件到族中的三個或更多資料型別並非 btree 索引機制本身嚴格必需的，但規劃器依賴它們進行最佳化。
如表 36.9 所示，btree 定義了一個必需的和一個可選的五個支援函式。六個使用者定義的方法是
order對於 btree 運算子族提供比較運算子的每一種資料型別組合，它都必須提供一個比較支援函式，在 pg_amproc 中註冊，支援函式編號為 1，並且 amproclefttype/amprocrighttype 等於比較的左側和右側資料型別（即，與在 pg_amop 中註冊的匹配運算子相同的資料型別）。比較函式必須接受兩個非 NULL 值 A 和 B，並返回一個 int32 值，當 A < B、A = B 或 A > B 時，分別返回 < 0、0 或 > 0。不允許返回 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 節）。根本上，提供的額外資訊是如何以與族的資料排序相容的方式新增或減去 offset 值。
一個 in_range 函式必須具有簽名
in_range(valtype1,basetype1,offsettype2,subbool,lessbool) returns bool
val 和 base 必須是同一型別，這是運算子族支援的型別之一（即，它提供排序的型別）。然而，offset 可以是不同型別，可能是族本身不支援的型別。例如，內建的 time_ops 族提供了一個 in_range 函式，其中 offset 的型別是 interval。一個族可以為它支援的任何型別以及一個或多個 offset 型別提供 in_range 函式。每個 in_range 函式都應該在 pg_amproc 中註冊，其中 amproclefttype 等於 type1，amprocrighttype 等於 type2。
一個 in_range 函式的基本語義取決於兩個布林標誌引數。它應該新增或減去 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 會溢位時丟擲錯誤。即使該值超出資料型別的範圍，也可以確定正確的比較結果。請注意，如果資料型別包含“無窮大”或“NaN”等概念，則可能需要格外小心，以確保 in_range 的結果與運算子族的正常排序一致。
in_range 函式的結果必須與運算子族施加的排序一致。精確地說，給定任何固定的 offset 和 sub 值，則
如果在某些 val1 和 base 下，具有 less = true 的 in_range 為真，則對於具有相同 base 的每一個 val2 <= val1，它都必須為真。
如果在某些 val1 和 base 下，具有 less = true 的 in_range 為假，則對於具有相同 base 的每一個 val2 >= val1，它都必須為假。
如果在某些 val 和 base1 下，具有 less = true 的 in_range 為真，則對於具有相同 val 的每一個 base2 >= base1，它都必須為真。
如果在某些 val 和 base1 下，具有 less = true 的 in_range 為假，則對於具有相同 val 的每一個 base2 <= base1，它都必須為假。
當 less = false 時，具有相反條件的類似陳述也成立。
如果被排序的型別（type1）是可排序的，則相應的排序 OID 將使用標準的 PG_GET_COLLATION() 機制傳遞給 in_range 函式。
in_range 函式不需要處理 NULL 輸入，通常會被標記為嚴格（strict）。
equalimage可選地，btree 運算子族可以提供 equalimage（“相等蘊含映像相等”）支援函式，在支援函式編號 4 下注冊。這些函式允許核心程式碼確定何時應用 btree 的去重最佳化是安全的。目前，equalimage 函式僅在構建或重建索引時被呼叫。
一個 equalimage 函式必須具有簽名
equalimage(opcintypeoid) returns bool
返回值是關於運算子類和排序的靜態資訊。返回 true 表示運算子類的 order 函式保證僅在 A 和 B 引數也互換時才返回 0（“引數相等”），且不丟失任何語義資訊。不註冊 equalimage 函式或返回 false 表示不能假定此條件成立。
opcintype 引數是運算子類索引的資料型別的 pg_type.oidequalimage 函式。如果 opcintype 是可排序的資料型別，則相應的排序 OID 將使用標準的 PG_GET_COLLATION() 機制傳遞給 equalimage 函式。
就運算子類而言，返回 true 表示去重是安全的（或者對於傳遞給其 equalimage 函式的排序 OID 是安全的）。但是，核心程式碼只有在 每個 索引列都使用註冊了 equalimage 函式的運算子類，並且每個函式在被呼叫時實際返回 true 時，才會認為對該索引的去重是安全的。
映像相等 幾乎 與簡單的按位相等相同。有一個細微的區別：當索引 varlena 資料型別時，兩個映像相等的 datum 的磁碟表示可能不按位相等，因為在輸入時應用了不一致的TOAST壓縮。形式上，當運算子類的 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() 宏從其他支援函式訪問這些選項。
目前，沒有 B-Tree 運算子類具有 options 支援函式。B-tree 不像 GiST、SP-GiST、GIN 和 BRIN 那樣允許靈活地表示鍵。因此，options 在當前的 B-tree 索引訪問方法中可能應用不多。儘管如此，此支援函式為了統一性被新增到了 B-tree 中，並且可能會在 B-tree 的進一步發展中找到用途。
skipsupport可選地，btree 運算子族可以提供 skip support 函式，在支援函式編號 6 下注冊。這些函式為 B-tree 程式碼提供了一種迭代運算子類底層輸入型別可以表示的每個可能值的方法，按鍵空間順序。核心程式碼在應用跳躍掃描最佳化時使用此功能。涉及的 API 定義在 src/include/utils/skipsupport.h 中。
不提供跳躍支援函式的類仍然有資格使用跳躍掃描。核心程式碼仍然可以使用其回退策略，儘管這對於某些離散型別可能不是最優的。對於連續型別上的運算子類提供跳躍支援函式通常沒有意義（甚至可能不可行）。
運算子族註冊跨型別 skipsupport 函式是不合理的，嘗試這樣做會導致錯誤。這是因為確定下一個可索引值必須透過遞增從索引元組複製的值來完成。生成的值都必須是相同的底層資料型別（“被跳過”的索引列的 opclass 輸入型別）。
本節介紹可能對高階使用者有用的 B-Tree 索引實現細節。有關 B-Tree 實現的更詳細、側重於內部的描述，請參閱原始碼分發中的 src/backend/access/nbtree/README。
PostgreSQL B-Tree 索引是多級樹結構，樹的每個級別都可以用作頁的雙向連結串列。一個單獨的元頁儲存在索引第一個段檔案的固定位置。所有其他頁要麼是葉子頁，要麼是內部頁。葉子頁是樹最低級別的頁。所有其他級別都由內部頁組成。每個葉子頁包含指向錶行的元組。每個內部頁包含指向樹下一層的元組。通常，99% 以上的頁都是葉子頁。內部頁和葉子頁都使用第 66.6 節中描述的標準頁格式。
當現有的葉子頁無法容納傳入元組時，B-Tree 索引會新增新的葉子頁。一個 頁分裂 操作透過將一部分項移動到新頁來為原本屬於溢位頁的項騰出空間。頁分裂還必須在父頁中插入指向新頁的新 下行連結，這可能會導致父頁也分裂。頁分裂以遞迴方式“向上級聯”。當根頁最終無法容納新的下行連結時，會發生 根頁分裂 操作。這透過建立一個比原始根頁高一級的根頁來為樹結構新增一個新級別。
B-Tree 索引不直接知道在 MVCC 下可能存在同一邏輯錶行的多個現有版本；對索引而言，每個元組都是一個需要自己的索引條目的獨立物件。“版本交錯”元組有時可能會累積並對查詢延遲和吞吐量產生不利影響。這通常發生在 UPDATE 密集型工作負載中，其中大多數單個更新都無法應用 HOT 最佳化。 僅更改由一個索引覆蓋的列的值在 UPDATE 中 總是 需要一組新的索引元組——為表上的每一個索引建立一個。請特別注意，這包括沒有被 UPDATE “邏輯修改”的索引。所有索引都需要一個指向表中最新版本的後繼物理索引元組。每個索引中的每個新元組通常都需要與原始的“已更新”元組短暫共存（通常直到 UPDATE 事務提交後不久）。
B-Tree 索引透過執行 自底向上索引刪除 傳遞來增量刪除版本交錯索引元組。每次刪除傳遞都是響應預期的“版本交錯頁分裂”而觸發的。這隻發生在未被 UPDATE 語句邏輯修改的索引中，否則會在特定頁中集中積累過時版本。通常會避免頁分裂，儘管有可能某些實現級別的啟發式演算法未能識別和刪除任何一個垃圾索引元組（在這種情況下，頁分裂或去重傳遞會解決新元組不適合葉子頁的問題）。任何索引掃描（針對任何單個邏輯行）必須遍歷的版本數是影響整體系統響應能力和吞吐量的一個重要因素。自底向上索引刪除傳遞基於邏輯行和版本的定性區別，針對單個葉子頁中可疑的垃圾元組。這與 autovacuum 工作程序執行的“自頂向下”索引清理形成對比，後者在滿足某些定量表級閾值時觸發（參見 第 24.1.6 節）。
並非 B-Tree 索引中執行的所有刪除操作都是自底向上刪除操作。還有一類獨立的索引元組刪除：簡單索引元組刪除。這是一個延遲的維護操作，它刪除已知可以安全刪除的索引元組（其項識別符號的 LP_DEAD 位已設定）。與自底向上索引刪除一樣，簡單索引刪除發生在預期的頁分裂點，以避免分裂。
簡單刪除是機會性的，因為它只能在最近的索引掃描在透過時設定受影響項的 LP_DEAD 位時發生。在 PostgreSQL 14 之前，B-Tree 刪除的唯一類別是簡單刪除。它與自底向上刪除的主要區別在於，前者是由透過的索引掃描活動機會性地驅動，而後者專門針對不會邏輯修改索引列的 UPDATE 產生的版本交錯。
自底向上索引刪除負責執行特定索引在某些工作負載下的大部分垃圾索引元組清理。對於任何 B-Tree 索引，如果它受到很少或從不邏輯修改索引覆蓋的列的 UPDATE 產生的大量版本交錯，則預期會如此。平均和最壞情況下每個邏輯行的版本數可以透過有針對性的增量刪除傳遞來保持較低水平。即使在持續的版本交錯 UPDATE 下，某些索引的磁碟大小也可能永遠不會增加一個頁面/塊。即便如此，VACUUM 操作（通常在 autovacuum 工作程序中執行）的一次詳盡的“全面清理”最終將作為表及其每個索引集體清理的一部分而需要。
與 VACUUM 不同，自底向上索引刪除不對最舊的垃圾索引元組的年齡提供任何強有力的保證。任何索引都不能保留在表及其所有索引 collectively 的保守截止點之前的“浮動垃圾”索引元組。這個基本的表級不變數使得回收表TID是安全的。這就是不同的邏輯行如何能夠隨著時間重用相同的表TID（儘管這永遠不會發生在生命週期跨越同一 VACUUM 週期的兩個邏輯行之間）。
重複項是葉子頁元組（指向錶行的元組），其中所有索引鍵列的值都與其他索引中的至少一個葉子頁元組的相應列值匹配。在實踐中，重複元組非常普遍。當啟用一個可選技術：去重時，B-Tree 索引可以使用一種特殊的、節省空間的表示法來表示重複項。
去重透過定期將一組重複元組合並在一起，為每個組形成一個單獨的釋出列表元組來工作。列鍵值僅出現一次。然後是一個指向錶行的TID的排序陣列。這極大地減小了索引的儲存大小，其中每個值（或每個不同的列值組合）平均出現幾次。查詢的延遲可以顯著降低。整體查詢吞吐量可能顯著提高。例行索引真空的開銷也可能顯著降低。
B-Tree 去重對於包含 NULL 值的“重複項”同樣有效，即使根據任何 B-Tree 運算子類的 = 成員，NULL 值也永遠不會彼此相等。就理解磁碟上 B-Tree 結構的任何部分而言，NULL 只是索引值域中的另一個值。
去重過程是惰性的，當新項被插入但無法放入現有葉子頁時發生，但前提是索引元組刪除未能為新項騰出足夠的空間（通常會短暫考慮刪除然後跳過）。與 GIN 釋出列表元組不同，B-Tree 釋出列表元組不需要在每次插入新重複項時擴充套件；它們只是葉子頁原始邏輯內容的替代物理表示。此設計優先考慮混合讀寫工作負載的一致性能。大多數客戶端應用程式至少會看到使用去重帶來的適度效能提升。預設啟用去重。
CREATE INDEX 和 REINDEX 應用去重來建立釋出列表元組，儘管它們使用的策略略有不同。從表中獲取的排序輸入中遇到的每個重複普通元組組在新增到當前待定葉子頁之前會合併到一個釋出列表元組中。單個釋出列表元組儘可能地打包了TID。葉子頁以通常的方式寫入，沒有單獨的去重傳遞。此策略非常適合 CREATE INDEX 和 REINDEX，因為它們是一次性的批次操作。
如果索引中重複值很少或沒有重複值，則寫密集型工作負載不會從去重中受益，但會承擔一個小的、固定的效能損失（除非明確停用去重）。deduplicate_items 儲存引數可用於停用單個索引內的去重。對於只讀工作負載，永遠不會有效能損失，因為讀取釋出列表元組至少與讀取標準元組表示一樣高效。停用去重通常沒有益處。
在某些情況下，唯一索引（以及唯一約束）也可以使用去重。這允許葉子頁暫時“吸收”額外的版本交錯重複項。唯一索引中的去重增強了自底向上索引刪除，特別是在長時間執行的事務持有阻止垃圾回收的快照的情況下。目的是為自底向上索引刪除策略再次生效爭取時間。將頁分裂延遲到單個長時間執行的事務自然消失，可以使刪除傳遞成功，而之前的刪除傳遞失敗。
會應用一種特殊的啟發式方法來確定唯一索引中的去重傳遞是否應該發生。它通常可以跳到分裂葉子頁，避免了在無用的去重傳遞上浪費週期的效能損失。如果您擔心去重的開銷，可以考慮選擇性地設定 deduplicate_items = off。在唯一索引中保持啟用去重幾乎沒有缺點。
由於實現級別的限制，去重並非在所有情況下都可用。去重安全性在執行 CREATE INDEX 或 REINDEX 時確定。
請注意，在涉及語義上重要的相等 datum 差異的情況下，去重被視為不安全且無法使用
text、varchar 和 char 在使用非確定性排序時不能使用去重。大小寫和重音差異必須在相等的 datum 中保留。
numeric 不能使用去重。數字顯示精度必須在相等的 datum 中保留。
jsonb 不能使用去重，因為 jsonb B-Tree 運算子類在內部使用 numeric。
float4 和 float8 不能使用去重。這些型別具有 -0 和 0 的不同表示，但它們被視為相等。必須保留此差異。
還有一個實現級別的限制，在未來的 PostgreSQL 版本中可能會被解除
容器型別（如複合型別、陣列或範圍型別）不能使用去重。
還有一個實現級別的限制，該限制適用於所有運算子類或排序
INCLUDE 索引永遠不能使用去重。
如果您在文件中發現任何不正確、與您對特定功能的使用經驗不符或需要進一步澄清的內容，請使用 此表單 報告文件問題。