PostgreSQL 包含标准btree(多路平衡树)索引数据结构的实现。任何可以排序成明确线性顺序的数据类型都可以通过 btree 索引进行索引。唯一的限制是索引条目不能超过页面大小的约三分之一（如果适用，则在 TOAST 压缩之后）。
由于每个 btree 操作符类都会对其数据类型施加排序顺序，因此 btree 操作符类（或者实际上是操作符族）已被用作 PostgreSQL 对排序语义的通用表示和理解。因此，它们获得了一些超出仅支持 btree 索引所需的功能，并且系统中与 btreeAM相距甚远的部分也利用了它们。
如 表 36.3 所示，btree 操作符类必须提供五个比较运算符 <、 <=、=、 >= 和 >。有人可能会认为 <> 也应该是操作符类的一部分，但事实并非如此，因为在索引搜索中使用 <> WHERE 子句几乎没有任何用处。（出于某些目的，规划器将 <> 视为与 btree 操作符类相关联；但它通过 = 运算符的否定链接找到该运算符，而不是来自 pg_amop。）
当多个数据类型共享几乎相同的排序语义时，它们的操作符类可以分组到一个操作符族中。这样做是有利的，因为它允许规划器对跨类型比较进行推断。族中的每个操作符类都应该包含其输入数据类型的单类型运算符（和相关的支持函数），而跨类型比较运算符和支持函数在族中是“松散的”。建议在族中包含完整的跨类型运算符集，从而确保规划器可以表示它从传递性推导出的任何比较条件。
btree 操作符族必须满足一些基本假设
= 运算符必须是等价关系；也就是说，对于数据类型的所有非空值 A、B、C
A = A 为真（自反律）
如果 A = B，则 B = A（对称律）
如果 A = B 且 B = C，则 A = C（传递律）
< 运算符必须是强排序关系；也就是说，对于所有非空值 A、B、C
A < A 为假（非自反律）
如果 A < B 且 B < C，则 A < C（传递律）
此外，排序是完全的；也就是说，对于所有非空值 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 中注册的数据类型相同）。比较函数必须接受两个非空值 A 和 B，并返回一个 int32 值，当 A < B、A = B 或 A > B 时，该值分别为 < 0、 0 或 > 0。不允许为 null 结果：数据类型的所有值都必须是可比较的。有关示例，请参见 src/backend/access/nbtree/nbtcompare.c。
如果比较的值是可排序的数据类型，则将使用标准的 PG_GET_COLLATION() 机制将适当的排序规则 OID 传递给比较支持函数。
sortsupport可选地，btree 操作符族可以提供 排序支持 函数，在支持函数编号 2 下注册。这些函数允许以比简单地调用比较支持函数更有效的方式实现用于排序目的的比较。此中涉及的 API 在 src/include/utils/sortsupport.h 中定义。
in_range可选地，B 树操作符族可以提供 in_range 支持函数，注册在支持函数编号 3 下。这些函数不会在 B 树索引操作期间使用；相反，它们扩展了操作符族的语义，使其可以支持包含 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)，错误文本类似于 “窗口函数中无效的前置或后置大小”。（这是 SQL 标准要求的，尽管非标准的操作符族可能选择忽略此限制，因为似乎没有太大的语义必要性。）此要求被委托给 in_range 函数，以便核心代码不必了解对于特定数据类型，“小于零”意味着什么。
另一个期望是，如果 base + offset 或 base - offset 会溢出，则 in_range 函数应在实践中避免抛出错误。即使该值超出数据类型的范围，也可以确定正确的比较结果。请注意，如果数据类型包含诸如 “无穷大”或 “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）是可排序的，则将使用标准的 PG_GET_COLLATION() 机制将适当的排序规则 OID 传递给 in_range 函数。
in_range 函数不需要处理 NULL 输入，并且通常会被标记为严格的。
equalimage可选地，B 树操作符族可以提供 equalimage（“相等意味着镜像相等”）支持函数，注册在支持函数编号 4 下。这些函数允许核心代码确定何时可以安全地应用 B 树去重优化。目前，仅在构建或重建索引时调用 equalimage 函数。
equalimage 函数必须具有以下签名：
equalimage(opcintypeoid) returns bool
返回值是关于操作符类和排序规则的静态信息。返回 true 表示操作符类的 order 函数保证仅在其 A 和 B 参数在不丢失任何语义信息的情况下也可以互换时才返回 0（“参数相等”）。不注册 equalimage 函数或返回 false 表示不能假定此条件成立。
opcintype 参数是操作符类索引的数据类型的 pg_type.oidequalimage 函数。如果 opcintype 是可排序的数据类型，则将使用标准的 PG_GET_COLLATION() 机制将适当的排序规则 OID 传递给 equalimage 函数。
就操作符类而言，返回 true 表示去重是安全的（或对于将其 OID 传递给其 equalimage 函数的排序规则是安全的）。但是，当 每个 索引列都使用注册了 equalimage 函数的操作符类，并且每个函数在被调用时都实际返回 true 时，核心代码才会认为索引的去重是安全的。
镜像相等与简单的按位相等 几乎 是相同的条件。有一个细微的差别：当索引 varlena 数据类型时，由于不一致地应用以下操作，两个镜像相等的数据的磁盘表示形式可能不是按位相等的：TOAST输入时的压缩。形式上，当操作符类的 equalimage 函数返回 true 时，可以安全地假定 datum_image_eq() C 函数将始终与操作符类的 order 函数一致（前提是将相同的排序规则 OID 传递给 equalimage 和 order 函数）。
核心代码从根本上无法根据同一族中其他操作符类的详细信息推断出多数据类型族中操作符类的 “相等意味着镜像相等” 状态。此外，操作符族注册跨类型 equalimage 函数是不明智的，并且尝试这样做会导致错误。这是因为 “相等意味着镜像相等” 状态不仅取决于排序/相等语义，这些语义在操作符族级别或多或少地定义。通常，必须单独考虑一个特定数据类型实现的语义。
核心 PostgreSQL 发行版中包含的操作符类遵循的惯例是注册一个标准的通用 equalimage 函数。大多数操作符类注册 btequalimage()，这表示去重是无条件安全的。可排序数据类型（如 text）的操作符类注册 btvarstrequalimage()，这表示去重对于确定性排序规则是安全的。第三方扩展的最佳实践是注册他们自己的自定义函数以保留控制权。
options可选地，B 树操作符族可以提供 options（“操作符类特定选项”）支持函数，注册在支持函数编号 5 下。这些函数定义了一组用户可见的参数，用于控制操作符类的行为。
options 支持函数必须具有以下签名：
options(reloptslocal_relopts *) returns void
该函数被传递一个指向 local_relopts 结构的指针，该结构需要填充一组操作符类特定的选项。可以使用 PG_HAS_OPCLASS_OPTIONS() 和 PG_GET_OPCLASS_OPTIONS() 宏从其他支持函数访问这些选项。
目前，没有 B 树操作符类具有 options 支持函数。B 树不允许像 GiST、SP-GiST、GIN 和 BRIN 那样灵活地表示键。因此，options 在当前的 B 树索引访问方法中可能没有太多应用。尽管如此，为了统一性，已将此支持函数添加到 B 树中，并且在 PostgreSQL 中进一步发展 B 树期间可能会找到用途。
本节介绍 B 树索引的实现细节，这些细节可能对高级用户有用。有关 B 树实现的更多以内部为中心的详细描述，请参见源发行版中的 src/backend/access/nbtree/README。
PostgreSQL B 树索引是多层树结构，树的每一层都可以用作页面的双向链表。一个单独的元页面存储在索引的第一个段文件的起始固定位置。所有其他页面要么是叶子页面，要么是内部页面。叶子页面是树的最底层页面。所有其他层都由内部页面组成。每个叶子页面包含指向表行的元组。每个内部页面包含指向树中下一层的元组。通常，超过 99% 的页面是叶子页面。内部页面和叶子页面都使用第 65.6 节中描述的标准页面格式。
当现有叶子页面无法容纳传入的元组时，会将新的叶子页面添加到 B 树索引中。一个页面分割操作通过将一部分项目移动到新页面来为原来属于溢出页面的项目腾出空间。页面分割还必须在父页面中插入一个指向新页面的新下行链接，这可能会导致父页面也进行分割。页面分割以递归方式“向上级联”。当根页面最终无法容纳新的下行链接时，会执行根页面分割操作。这通过创建一个比原始根页面高一级的新的根页面，为树结构添加一个新级别。
B 树索引并不直接知道在 MVCC 下，同一逻辑表行可能存在多个版本；对于索引，每个元组都是一个独立的、需要自己的索引条目的对象。“版本变更” 元组有时会累积，并对查询延迟和吞吐量产生不利影响。这通常发生在UPDATE 频繁的工作负载中，其中大多数单独的更新无法应用HOT优化。在UPDATE期间，仅更改一个索引覆盖的列的值总是需要一组新的索引元组——对于表上的每个索引，都需要一个。特别要注意的是，这包括那些没有被UPDATE“逻辑修改”的索引。所有索引都需要一个指向表中最新版本的后继物理索引元组。每个索引中的每个新元组通常都需要与原始的“更新”元组共存一小段时间（通常在UPDATE事务提交后不久）。
B 树索引通过执行自下而上的索引删除过程来增量删除版本变更索引元组。每个删除过程都是对预期的“版本变更页面分割”的反应而触发的。这只会发生在未被UPDATE语句逻辑修改的索引中，否则，过时版本会在特定页面中集中累积。通常会避免页面分割，但某些实现级别的启发式方法可能无法识别甚至删除一个垃圾索引元组（在这种情况下，页面分割或重复数据删除过程会解决传入的新元组不适合叶子页面的问题）。任何索引扫描必须遍历的版本（对于任何单个逻辑行）的最坏情况数量是影响整体系统响应速度和吞吐量的重要因素。自下而上的索引删除过程基于逻辑行和版本的定性区别，针对单个叶子页面中的可疑垃圾元组。这与 autovacuum 工作进程执行的“自上而下”索引清理形成对比，后者是在超出某些定量表级别阈值时触发的（参见第 24.1.6 节）。
并非在 B 树索引中执行的所有删除操作都是自下而上的删除操作。还有一类不同的索引元组删除：简单索引元组删除。这是一种延迟维护操作，它删除已知可以安全删除的索引元组（那些项目标识符的 LP_DEAD 位已设置的元组）。与自下而上的索引删除类似，简单索引删除发生在预期页面分割时，以此避免分割。
简单删除是机会主义的，因为它只能在最近的索引扫描在经过时设置了受影响项目的 LP_DEAD 位时进行。在 PostgreSQL 14 之前，B 树删除的唯一类型是简单删除。它与自下而上删除的主要区别在于，前者是由经过的索引扫描的活动机会主义地驱动的，而后者专门针对来自UPDATE的版本变更，而这些UPDATE不会逻辑修改索引列。
对于某些工作负载，自下而上的索引删除操作为特定索引执行了绝大多数的垃圾索引元组清理工作。对于任何受到UPDATE导致的显著版本变更影响的 B 树索引来说，这都是预期的，这些UPDATE很少或从不逻辑修改索引覆盖的列。每个逻辑行的平均和最坏情况版本数可以通过有针对性的增量删除过程保持在较低水平。某些索引的磁盘大小可能永远不会增加哪怕一个页面/块，即使来自UPDATE的持续版本变更也是如此。即便如此，VACUUM 操作（通常在 autovacuum 工作进程中运行）的彻底“全面清理”最终还是需要作为表及其每个索引的集体清理的一部分。
与 VACUUM 不同，自下而上的索引删除并不提供关于最旧的垃圾索引元组可能有多旧的任何强有力保证。不允许任何索引保留在保守的截止点之前死亡的“浮动垃圾”索引元组，该截止点由表及其所有索引共同共享。这种基本的表级别不变量使得回收表TID成为可能。这就是为什么不同的逻辑行可以随着时间的推移重复使用同一个表的原因TID（尽管对于生命周期跨越同一 VACUUM 周期的两个逻辑行来说，这永远不会发生）。
重复项是一个叶子页面元组（指向表行的元组），其中所有索引键列的值与同一索引中至少一个其他叶子页面元组的对应列值匹配。重复元组在实践中很常见。当启用可选技术：重复数据删除时，B 树索引可以使用一种特殊的、节省空间的重复项表示形式。
重复数据删除的工作原理是定期将成组的重复元组合并在一起，为每个组形成一个单独的发布列表元组。列键值只在此表示形式中出现一次。接下来是一个排序的TID列表，其中包含指向表中行的列表。这显著减少了每个值（或每种不同的列值组合）平均出现多次的索引的存储大小。查询的延迟可以显著减少。总体查询吞吐量可能会显著增加。例行索引清理的开销也可能会显著减少。
B 树重复数据删除对于包含 NULL 值的“重复项”也同样有效，即使根据任何 B 树运算符类的 = 成员，NULL 值也永远不等于彼此。就任何理解磁盘上 B 树结构的实现部分而言，NULL 只是索引值域中的另一个值。
重复数据删除过程会在插入新项时延迟发生，该新项不适合现有叶子页面，但仅在索引元组删除无法为新项释放足够的空间时（通常会短暂考虑删除，然后跳过）。与 GIN 发布列表元组不同，B 树发布列表元组不需要在每次插入新重复项时都扩展；它们只是叶子页面原始逻辑内容的另一种物理表示形式。此设计优先考虑混合读写工作负载的一致性能。大多数客户端应用程序至少会从使用重复数据删除中看到适度的性能提升。默认情况下启用重复数据删除。
CREATE INDEX 和 REINDEX 应用重复数据删除来创建发布列表元组，但它们使用的策略略有不同。在从表中获取的排序输入中遇到的每组重复的普通元组，会在添加到当前待处理的叶子页面之前被合并到发布列表元组中。单个发布列表元组会尽可能多地打包TID列表。叶子页面以通常的方式写出，没有任何单独的重复数据删除过程。此策略非常适合 CREATE INDEX 和 REINDEX，因为它们是一次性批处理操作。
由于索引中很少或没有重复值，因此无法从重复数据删除中受益的写入密集型工作负载将产生较小的固定性能损失（除非显式禁用重复数据删除）。deduplicate_items 存储参数可用于禁用单个索引中的重复数据删除。对于只读工作负载，永远不会有任何性能损失，因为读取发布列表元组至少与读取标准元组表示形式一样高效。禁用重复数据删除通常没有帮助。
有时，唯一索引（以及唯一约束）可以使用重复数据删除。这允许叶子页面暂时“吸收”额外的版本变更重复项。唯一索引中的重复数据删除增强了自下而上的索引删除，尤其是在长时间运行的事务持有快照阻止垃圾回收的情况下。其目的是为自下而上的索引删除策略再次生效争取时间。将页面分割延迟到单个长时间运行的事务自然消失可以使自下而上的删除过程在早期删除过程失败的情况下获得成功。
应用了一种特殊的启发式方法来确定唯一索引中的重复数据删除过程是否应该进行。它通常可以直接跳到拆分叶子页，避免因在无益的重复数据删除过程上浪费周期而导致的性能损失。如果您担心重复数据删除的开销，请考虑有选择地设置 deduplicate_items = off。在唯一索引中启用重复数据删除几乎没有缺点。
由于实现级别的限制，并非所有情况下都可以使用重复数据删除。重复数据删除的安全性在运行 CREATE INDEX 或 REINDEX 时确定。
请注意，在以下涉及等值数据之间存在语义差异的情况下，重复数据删除被认为是不安全的，并且不能使用：
当使用非确定性排序规则时，text、varchar 和 char 不能使用重复数据删除。在等值数据之间必须保留大小写和重音符号的差异。
numeric 不能使用重复数据删除。在等值数据之间必须保留数值显示比例。
jsonb 不能使用重复数据删除，因为 jsonb B 树运算符类在内部使用 numeric。
float4 和 float8 不能使用重复数据删除。这些类型对于 -0 和 0 有不同的表示形式，但它们仍然被认为是相等的。必须保留这种差异。
还有一个实现级别的限制，可能会在未来版本的 PostgreSQL 中解除。
容器类型（例如复合类型、数组或范围类型）不能使用重复数据删除。
还有一个实现级别的限制，无论使用什么运算符类或排序规则都适用：
INCLUDE 索引永远不能使用重复数据删除。
如果您在文档中发现任何不正确的内容，与您使用特定功能的体验不符，或需要进一步澄清的内容，请使用此表单来报告文档问题。