PostgreSQL包括了对标准btree（多路平衡树）索引数据结构的一个实现。任何能够被排序为良定义线性顺序的数据结构都可以用一个btree来索引。唯一的限制是一个索引项不能超过大约三分之一个页面（如果适用，可以是TOAST压缩后的大小）。
因为每个 btree 操作符类都会对其数据类型施加排序顺序，btree 操作符类（或者说操作符族）已经成为 PostgreSQL对排序语义的一般表示和理解。因此，它们获得了一些超出仅支持 btree 索引所需的功能，系统中与 btree AM 相距甚远的部分也会使用它们。
如Table 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放在同一个操作符族中是行不通的，至少在当前的语义（为了和一个float8比较，numeric值会被转换成float8）下不行。因为float8有限的精度，这意味着不同的numeric值将被认为等于同一个float8值，因此传递律将被破坏。
对于多数据类型操作符族的另一个要求是，其中包括的定义在数据类型之间的任何隐式或者二进制强制造型不能改变相关的排序顺序。
为何一个btree索引要求这些定律在单一数据类型中必须保持的原因应该相对比较清楚：没有这些定律就不存在用于安排键的顺序。此外，使用不同数据类型键的比较的索引搜索也要求比较操作在两种数据类型之间表现得稳定。btree索引机制本身并不严格要求在一个操作符族中扩展到三种或者更多种数据类型，但是规划器依赖于这种扩展来实现其优化的目的。
如Table 36.9中所示，btree定义了一种必需的和四种可选的支持函数。这五种用户定义的方法为：
order
对于btree操作符族为其提供了比较操作符的每一种数据类型组合，操作符族必须提供一个比较支持函数，在pg_amproc中注册：支持函数编号为1，amproclefttype/amprocrighttype等于比较的左右数据类型（即匹配的操作符注册在pg_amop中的数据类型）。
比较函数必须接收两个非空值A和B并且返回一个int32值，返回值在A < B、A = B以及A > B时分别为< 0、0和> 0。
不允许空值结果：该数据类型的所有值必须是可比较的。
例子请见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窗口帧界类型（见Section 4.2.8）的窗口子句。
归根到底，这些函数所提供的额外信息是如何以一种与该操作符族的数据排序相兼容的方式加上或者减去一个offset值。
An in_range 函数必须有签名
in_range(valtype1,basetype1,offsettype2,subbool,lessbool) returns bool
val和base必须是同一种类型，该类型也是操作符族所支持的类型之一（即它提供排序的一种类型）。
不过，offset可以是一种不同的类型，该类型有可能不被该操作符族所支持。例如内建的time_ops族提供了一个in_range函数，其offset是类型interval。
一个操作符族可以为其所支持的任意类型提供in_range函数以及一个或者更多种offset类型。
每一个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函数，这样核心代码不需要理解对一种特定数据类型“less than zero”表示什么。
一个额外的期望是，如果可行，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为假, name它对于每一个有相同val的base2 <= base1也必须为假。
当less = false时，类似的具有相逆条件的语句成立。
如果被排序的类型（type1）是可排序的，合适的排序规则OID将使用标准的PG_GET_COLLATION()机制被传递给in_range函数。
in_range函数不需要处理NULL输入，并且通常将被标记为strict。
equalimage
可选地，btree 操作符系列可以提供equalimage（“equality implies image equality”）支持功能，注册在支持函数 4 下面。
这些函数允许核心代码确定何时可以安全地应用 btree 重复数据消除进行优化。
目前，equalimage函数仅在生成或重建索引时调用。
一个 equalimage 函数必须包含签名
equalimage(opcintypeoid) returns bool
返回值是有关运算符类和排序规则的静态信息。
返回true表示运算符类的 order 函数保证仅返回0 (“arguments are equal”) 时，A和 B参数也可以互换，而不会丢失任何语义信息。
不注册equalimage函数或返回false表示不能假定此条件成立。
opcintype参数是操作符类索引的数据类型的pg_type.oidequalimage函数。
如果opcintype是可排序数据类型，则相应的排序规则 OID 将传递给 equalimage 函数，使用标准的 PG_GET_COLLATION() 机制。
就操作符类而言，返回true意味着重复数据删除是安全的（或安全排序规则，其OID传递给它的equalimage函数）。
但是，核心代码只有在every 索引列使用注册了 equalimage 函数的操作符类时，并且每个函数在调用时实际返回 true 时，才会认为重复数据删除是安全的。
图像相等几乎与简单位元(simple bitwise)相等的条件相同。
有一个细微的区别：在索引 varlena 数据类型时，由于输入上TOAST压缩应用不一致，两个图像相等基准的磁盘表示可能不是位相等的。
从形式上看，当操作符类的 equalimage函数返回 true 时，可以安全的地假定 datum_image_eq() C 函数将始终与操作符类的 order 函数一致（前提是将同一个排序规则 OID 传递给 equalimage 和 order 函数）。
核心代码从根本上无法推断出任何关于基于同一系列中其他运算符类的详细信息的具有多数据类型系列中的操作符类的“equality implies image equality”状态。
此外，操作符系列注册跨类型 equalimage函数是不明智的，尝试这样做将导致错误。
这是因为“equality implies image equality”状态不仅仅取决于排序/相等语义，这些语义或多或少在操作符系列级别定义。
通常，特定数据类型实现的语义必须单独考虑。
核心 PostgreSQL 分发中包含的操作符类所遵循的约定是注册股票(register a stock)，通用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-Tree 操作符类具有 options支持功能。
B-tree不允许灵活表示键， 例如 GiST, SP-GiST, GIN 和 BRIN。
因此，options在当前的B-tree索引访问方法中可能没有太多的应用。
不过，此支持函数已添加到 B-tree中以保持一致性，并且可能会在PostgreSQL中B-tree的进一步演进中找到更多应用。
本节介绍 B-Tree 索引实现详细信息，这些对高级用户可能有用。
更多信息请参见在源分发中的src/backend/access/nbtree/README文件，内部聚焦的 B-Tree实现描述。
PostgreSQL B-Tree 索引是多级树结构，其中树的每个级别都可以用作双链接的页列表。 单个元页存储在索引的第一个段文件开始时的固定位置。所有其他页都是叶页或内部页。叶页是在树的最低层上的页。 所有其他层级由内部页组成。每个叶页都包含指向表行的元组。每个内部页都包含指向树中下一级别的元组。 通常，超过 99% 的页面是叶页。 内部页和叶页都使用 Section 65.6中描述的标准页格式。
当已有叶页不能适应传入元组时，新叶页将添加到B-Tree索引中。 page split操作通过将部分项目移动到新页面为最初属于溢出页上的项目提供空间。 页拆分还必须插入新的downlink到父页中的新页，这可能会导致父页依次拆分。 页拆分“cascade upwards”以递归的方式。 当根页最终无法适合新的下行链接时，发生root page split操作。 通过创建比原始根页高一个级别的新根页，为树结构添加新级别。
B-Tree索引并不直接意识到在MVCC下，同一个逻辑表行可能存在多个现存版本；对于索引，每个元组都是一个独立的对象，需要自己的索引条目。“版本变动”的元组有时会累积并对查询延迟和吞吐量产生不利影响。这通常发生在以UPDATE为主的工作负载中，其中大多数单个更新无法应用HOT优化。在UPDATE期间仅更改一个索引覆盖的列的值总是需要一组新的索引元组 — 对于表上的每一个索引都需要一个。特别注意，这包括那些并未被UPDATE“逻辑修改”的索引。所有索引都需要一个指向表中最新版本的后继物理索引元组。每个索引中的新元组通常需要与原始“更新”元组共存一段时间（通常直到UPDATE事务提交后不久）。
B-Tree索引通过执行bottom-up index deletion传递，增量地删除版本混杂索引元组。
每个删除传递都是在预期的“version churn page split”反应时触发的。
这只发生在没有被UPDATE语句逻辑修改的索引上，否则将会出现集中生成特定页面中的过时版本。
通常会避免页分割，尽管某些实现级别的启发式方法可能无法识别和删除即使一个垃圾索引元组(在这种情况下，页分割或重复数据删除传递解决传入的新元组不适合叶页的问题)。
任何索引扫描必须遍历的最坏版本数(对于单个逻辑行)，是整个系统响应能力和吞吐量的重要因素。
自下而上的索引删除通道基于涉及逻辑行和版本的定性区分，针对单个叶页中的可疑垃圾元组。
bottom-up的索引删除传递针对单个叶页中的可疑垃圾元组，基于涉及逻辑行和版本的quantitative差异。
这与autovacuum workers执行的“top-down”索引清理形成对比，其在某些quantitative表级阈值超过时触发(参见 Section 24.1.6)。
不是所有在B-Tree索引中执行的删除操作，都是bottom-up删除操作。
这有一个索引元组删除的独特类别：simple index tuple deletion.
这是一个延迟维护操作，用以删除已知的可以安全删除的索引元组(那些项标识符LP_DEAD位已经被设置的)。
就像bottom-up索引删除，简单索引删除发生在预期将进行页分割的时候，作为避免分割的一种方式。
某种意义上说，简单删除是具有机会性的，因为它只能在当前索引扫描设定传递所影响项目的LP_DEAD位的时候发生。
在PostgreSQL 14之前，唯一的B-Tree删除类别是简单删除。
它和bottom-up删除的主要区别是，前者(简单删除)是由传递索引扫描活动在适当的时候驱动的，而后者专门针对没有进行逻辑修改索引列的UPDATE所带来的版本混杂。
Bottom-up索引删除为具有某些工作负载的特定索引执行绝大多数垃圾索引元组清理。
对任何B-Tree索引，如果它从UPDATE受到明显的版本混杂，而几乎没有或从未有逻辑更改该索引所覆盖的列，这是可以预见的。
每个逻辑行的平均和最坏情况的版本数可以通过目标增量删除传递以保持较低。
尽管从 UPDATEconstant 进行了版本混杂，但某些索引的磁盘大小很可能永远不会增加哪怕一个页面/块。
尽管如此，一个由VACUUM操作(通常在autovacuum worker进程中运行)的彻底的“clean sweep” 将最终需要作为表和它的每个索引的集体清理的一部分。
不像VACUUM，bottom-up索引删除不提供任何关于最古老的垃圾索引元组有多长时间的强保证。
没有索引可以被允许保留在由表和所有它的索引共享的保守截止点之前已经失效的“floating garbage”索引元组。
这个基本的表级不变量使得回收利用表的TID是安全的。
这就是为什么不同的逻辑行可以随着时间的推移而重新使用相同的表TID(尽管这在生命周期跨越相同的VACUUM周期的两个逻辑行中永远不会发生)。
重复项是叶页元组（指向表行的元组），其中所有 索引键列的值与同一索引中至少一个其他叶页元组的相应列值匹配。 重复元组在实践中很常见。 当启用可选技术：重复时，B-Tree 索引可以对重复项使用特殊的、节省空间的表达方式。
重复数据删除的工作为通过定期将重复元组合并在一起，为每个组构建一个posting list元组。 列键值在此表示形式中仅显示一次。 后面跟着指向表中行的TID的排序数组。 这显著减少了索引的存储大小，在其中每个值（或列值的每个不同组合）平均出现多次时。 查询的延迟可以显著降低。 总体查询吞吐量可能会显著增加。 常规索引清空的开销也可以显著降低。
B-Tree重复数据删除对于包含 NULL 值的“duplicates”同样有效，即使根据任何 B-Tree 操作符类的 = 成员，NULL 值永远不会彼此相等。
对于理解磁盘上 B-Tree 结构的实现的任何部分，NULL 只是索引值域中的另一个值。
当插入的新项无法适应现有叶页时，重复数据删除过程进行缓慢，虽然只有当索引元组删除不能为新项释放足够的空间时(通常删除会被简单考虑然后跳过) 不像 GIN 倒排列表元组，B-Tree倒排列表元组不需要在每次插入新重复项时展开;它们仅仅是叶页原始逻辑内容的替代物理表示方式。 此设计优先考虑混合读写工作负载的一致性能。 大多数客户端应用程序可以从使用重复数据删除中获得适度的性能收益。默认情况下，将启用重复数据删除。
CREATE INDEX和 REINDEX 应用重复数据删除来创建倒排列表元组，尽管它们使用的策略有所不同。
每组重复的普通元组遇到从表中取出的排序输入将合并到倒排列表元组，在添加到当前挂起的叶页之前。
单独倒排列表元组尽可能以TIDs封装。 叶页以通常的方式写出，没有任何分开的重复数据删除步骤。
此策略非常适合CREATE INDEX和REINDEX，因为它们是一次性的批处理操作。
由于索引中重复值很少或没有重复值，因此无法从重复数据删除中获益的写频繁工作负载将产生少量的、固定性能损耗（除非显式禁用重复数据删除）。
deduplicate_items存储参数可用于禁用单个索引中的重复数据消除。
只读工作负载永远不会有任何性能损失，因为读取倒排列表元组至少与读取标准元组表示一样高效。 禁用重复数据删除通常没有帮助。
有的时候惟一索引(以及惟一约束)可能被使用重复数据删除。 这允许叶页临时“absorb” 额外的版本混杂副本。 唯一索引中的重复数据删除增强了bottom-up索引删除，特别是在长时间运行的事务持有块垃圾收集的快照的情况下。 目的是为了bottom-up索引删除策略变得再次生效争取时间。 延迟分页分割，直到单个长时间运行的事务自然消失，可以允许bottom-up删除传递成功，在较早的删除传递失败的地方。
应用一种特殊的启发式方法来确定是否应在唯一索引中进行重复数据删除操作。
它通常可以直接跳到拆分叶页，避免在无益的重复数据删除传递上浪费周期会降低性能。
如果你担心重复数据删除的开销，可以考虑deduplicate_items = off。 在唯一索引中启用重复数据删除没有什么坏处。
由于实现级别的限制，不能在所有情况下使用重复数据消除。
在CREATE INDEX 或 REINDEX时决定重复数据删除安全性。
请注意，重复数据删除被认为是不安全的，不能用于下列涉及相同数据之间语义显著差异的情况:
text, varchar, 和 char在使用nondeterministic排序规则时不能使用重复数据删除。
在等值基准之间必须保留大小写和重音差异。
numeric重复数据删除。 数字显示比例必须在相等的基准之间保留。
jsonb不能使用重复数据消除，因为jsonbB-Tree操作符类在内部使用numeric。
float4和float8不能使用重复数据删除。
这些类型对 -0 和 0具有不同的表示形式，但被视为相等。 必须保留此差异。
在未来版本的PostgreSQL中，还有一个实现级限制可能取消：
容器类型（例如复合类型、数组或范围类型）不能使用重复数据删除。
无论使用操作符类或排序规则如何，还有一个实现级别限制适用：
INCLUDE 索引不能使用重复数据删除.