PostgreSQL 包含对标准的一种实现btree(多路平衡树) 索引数据结构。任何可以按明确线性顺序分类的数据类型都可由 B 树索引建立索引。唯一的限制是单个索引项不能超过大约三分之一的页面（若可应用，则在 TOAST 压缩后）。
由于每个 B 树操作符类都对自身数据类型施加排序顺序，因此 B 树操作符类（或实际上的操作符族）最终被用作 PostgreSQL 对排序语义进行一般表示和理解的方式。因此，它们获取了某些超出 B 树索引支持需求的功能，并且与 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 放入同一操作符族是行不通的，至少在当前语义下，与 float8 进行比较之前，numeric 值会被转换为 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 下注册的 sort support 函数。这些函数允许以比直接调用比较支持函数更有效的方式执行比较以便于进行排序。此过程涉及的 API 在 src/include/utils/sortsupport.h 中定义。
in_range一个 btree 算子族可以选择提供在支持函数编号 3 下注册的 in_range 支持函数。这些函数在 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 类型的。系列可以为其支持的任何类型提供 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)，错误文本类似于 “窗口函数中无效的前置或后置大小”。（这是 SQL 标准所要求的，尽管非标准运营符系列可能会选择忽略此限制，因为对于特定数据类型来说很少有语义必要性。）此要求委派给了 in_range 函数，以便核心代码不必理解 “小于零” 对特定数据类型的含义。
额外的预期是，如果可行，in_range 函数应避免在 base + offset 或 base - offset 将溢出时引发错误。即使该值不在数据类型的范围内，也可以确定正确的比较结果。请注意，如果数据类型包括诸如 “无穷大” 或 “NaN” 等概念，则可能需要格外小心才能确保 in_range 的结果与运算符系列的正常排序顺序相一致。
in_range 函数的结果必须与运算符系列施加的排序顺序一致。确切地说，在给定任何固定值的 offset 和 sub 的情况下，
如果对某些 val1 和 base，in_range 的 less = true 为真，对于具有相同的 base 的每个 val2 <= val1，它都必须为真。
如果对某些 val1 和 base，in_range 的 less = true 为假，对于具有相同 base 的每个 val2 >= val1，它都必须为假。
如果对某些 val 和 base1，in_range 的 less = true 为真，对于具有相同 val 的每个 base2 >= base1，它都必须为真。
如果对某些 val 和 base1，in_range 的 less = true 为假，对于具有相同 val 的每个 base2 <= base1，它都必须为假。
当 less = false 时，带有倒置条件的类似语句成立。
如果正在排序的类型（type1）是可并列的，使用标准 PG_GET_COLLATION() 机制会将适当的校对 OID 传递给 in_range 函数。
in_range 函数不需要处理 NULL 输入，并且通常会标记为严格的。
等像 images一个 btree 操作符族可以选择提供 equalimage（“相等暗示图像相等”）支持函数，在支持函数编号 4 下注册。这些函数允许核心代码确定何时可以安全地应用 btree 去重优化。目前，仅在构建或重建索引时调用 equalimage 函数。
一个 equalimage 函数必须具有如下代码签名
equalimage(opcintypeoid) returns bool
返回值是关于一个操作符类和校对的静态信息。返回 true 表示操作符类的 order 函数保证仅在它的 A 和 B 参数也不损失语义信息的情况下可以互换时，返回 0（“参数相等”）。不注册一个 equalimage 函数或返回 false 表示不能认为这个条件成立。
opcintype 参数是操作符类索引的数据类型 pg_type.oidequalimage 函数跨操作符类的便利方式。如果 opcintype 是一个可校对数据类型，合适的校对 OID 将传递给 equalimage 函数，使用标准 PG_GET_COLLATION() 机制。
就操作符类而言，返回 true 表示去重是安全的（或对于其 equalimage 函数传递 OID 的校对而言是安全的）。然而，核心代码仅当 每个 索引列使用注册了 equalimage 函数的操作符类时才会认为去重对索引而言是安全的，并且当调用时每个函数也确实返回 true。
图像相等是 几乎 与简单按位相等相同的条件。有一个细微差别：当索引一个 varlena 数据类型时，由于TOAST输入的压缩应用不一致，两个图像相等的数据的磁盘表示法可能无法按位相等。正式来说，当一个操作符类的 equalimage 函数返回 true 时，可以安全地假设 datum_image_eq() C 函数始终会与操作符类的 order 函数一致（前提是向 equalimage 和 order 函数传递相同的校对 OID）。
核心代码根本无法根据同一多数据类型系列中其他操作符类的详细信息，推断出该操作符类中的“相等暗示图像相等”状态。而且，操作符系列为跨类型“equalimage”函数注册是不明智的，这样做会产生错误。这是因为“相等暗示图像相等”状态不仅取决于在操作符系列级别（或多或少是定义的）的排序/相等语义。通常，必须分别考虑一个特殊数据类型实现语义。
随附的核心PostgreSQL分发的操作符系列遵循约定，以注册现成的通用“equalimage”函数。大多数操作符系列注册“btequalimage()”，这表明去重是无条件安全的。用于可排序数据类型（例如“text”）的操作符系列注册“btvarstrequalimage()”，这表明去重是安全且确定排序的。第三方扩展的最佳做法是注册其自己的自定义函数以保留控制权。
选项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 所做的那样。因此，在当前的 B 树索引访问方法中，“options”可能没有太多应用程序。尽管如此，此支持函数还是出于统一性的考虑而添加到 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语句逻辑修改的索引上，否则将导致特定页中废弃版本集中堆积。通常会避免页拆分，尽管某些实现级别的启发式算法可能会识别并删除甚至一个垃圾索引元组（在这种情况下，页拆分或重复数据消除传递将解决新元组不适合叶页问题）。对于任何单个逻辑行，索引扫描必须遍历的最大版本数是整体系统响应能力和吞吐量的重要影响因素。基于涉及逻辑行和版本的定性区别，自下而上的索引删除传递以单个叶页中可疑的垃圾元组为目标。这与“自上而下”索引清理形成对比，该清理由自动清理工作程序执行，当超过特定定量表级别阈值时触发（请参阅第 24.1.6 节）。
并非在 B 树索引内执行的所有删除操作都是自下而上的删除操作。存在一种不同的索引元组删除类别：简单的索引元组删除。这是一种延迟维护操作，它删除已知可以安全删除的索引元组（其项目标识符的LP_DEAD位已设置）。与自下而上的索引删除类似，在预计页拆分时进行简单索引删除，以避免拆分。
简单删除是机会主义的，因为它只能在最近的索引扫描顺便设置受影响项目的LP_DEAD位时进行。在 PostgreSQL 14 之前，唯一的 B 树删除类别是简单删除。它与自下而上的删除之间的主要区别在于，只有前者是由经过索引扫描的活动机会主义驱动的，而后者仅专门针对不会逻辑修改已编制索引列的UPDATE版本变动。
自底向上的索引删除对特定索引中的所有垃圾索引元组清理执行绝大多数任务，某些工作负载也是如此。对于由 UPDATE 引起的大量版本变更而很少或从不从逻辑上修改索引所覆盖的列的任何 B 树索引，会出现这种情况。每个逻辑行的平均版本数和最差情况版本数可通过有针对性的增量删除路径保持较低值。很有可能，某些索引的磁盘大小甚至不会增加一页/区块，即使 UPDATE 引起版本变更保持不变。即使如此，作为表及其每个索引的集合清理的一部分，VACUUM 操作（通常在自动清理工作进程中运行）的彻底“彻底清理”最终仍是必需的。
与 VACUUM 不同，自底向上的索引删除不提供有关最旧垃圾索引元组可能有多旧的任何强力担保。不能允许任何索引保留在表及其所有索引共享的保守截止点之前已死掉的“悬浮垃圾”索引元组。此基本表级不变性使得能够安全回收表TIDs。这是不同的逻辑行能够随着时间的推移重新使用同一张表的方式（不过，对于生命周期跨越相同 VACUUM 周期的两个逻辑行，这种情况永远不会发生）。TID
重复项是叶页元组（指向表行的元组），其中所有索引键列的都有多个值，这些值与同一索引中至少一个其他叶页元组的相应列值相匹配。重复元组在实践中相当常见。当启用可选技术时，B-Tree 索引可以使用一种特殊的节省空间的表示形式：重复数据删除。
重复数据删除通过定期合并重复元组组一起发挥作用，为每个组形成一个过帐单元组。列键值只在此表示形式中出现一次。然后是一系列指向表中行的已排序数组TIDs。这显著降低了索引的存储大小，每个值（或列值的每个不同组合）平均出现多次。查询的延迟可以显著降低。总体查询吞吐量可能会显著增加。例程索引清理的开销也可能显著降低。
B-Tree 去重与包含 NULL 值的“重复项”同样有效，即使在 B-Tree 运算符类的任何成员 = 中，NULL 值永远不等于彼此。对于了解磁盘上 B-Tree 结构的任何实现部分，NULL 仅仅是从已编制索引的值域中的另一个值。
在无法放入现有叶页的新项目插入时，去重进程会以延迟方式进行，但仅在索引元组删除无法为新项目释放足够空间时才会进行（通常会短暂考虑删除，然后跳过）。B-Tree 发帖列表元组不同于 GIN 发帖列表元组，它不需要在每次插入新重复项时进行扩展。它仅仅是叶页的原始逻辑内容的另一种物理表示。此设计优先考虑混合读写工作负载的一致性能。大多数客户端应用程序至少会看到使用去重带来的适度性能优势。默认情况下，启用了去重。
CREATE INDEX 和 REINDEX 通过创建发帖列表元组来应用去重，但它们使用的策略略有不同。在从表中提取的已排序输入中遇到的每个重复普通元组组会合并到发帖列表元组中 在 将其添加到当前待定叶页之前。单独的发帖列表元组将尽可能多的TID打包到 s。叶页会以通常方式写出，没有任何单独的去重传递。此策略非常适用于 CREATE INDEX 和 REINDEX，因为它们是一次性的批处理操作。
对由于索引中重复值少或没有重复值而不能从去重中受益的写密集型工作负载将产生细微的固定性能损失（除非明确禁用去重）。deduplicate_items 存储参数可用于在各个索引内禁用去重。因读取发帖列表元组至少与读取标准元组表示法一样高效，所以只读工作负载永远不会产生任何性能损失。禁用去重通常没有帮助。
唯一索引（以及唯一约束）有时会使用去重。这使得叶页可以暂时“吸收”额外的版本变化重复项。唯一索引中的去重会增强自底向上的索引删除，尤其在长事务持有会阻止垃圾回收的快照时。目标是为自底向上的索引删除策略再次生效争取时间。延迟页面拆分，直到单个长事务自然消失，可以使自底向上的删除传递成功，而较早的删除传递失败。
当确定唯一索引中是否应该执行重复数据删除时，会应用一个特殊的启发式方法。通常，这可以直接跳到分割叶页面，避免在无帮助的重复数据删除上浪费周期，从而避免性能损失。如果你担心重复数据删除的大开销，可以考虑有选择性地设置 deduplicate_items = off
由于实现级别的限制，并不总可以使用重复数据删除。重复数据删除的安全性在运行 CREATE INDEXREINDEX
请注意，在以下情况中，由于相等的数据项之间存在语义上的显著差异，因此重复数据删除被认为不安全，不能使用
当使用非确定性校对时，textvarcharchar
numeric
jsonbjsonbnumeric
float4float8-00
还有另一个实现级别的限制，可能会在未来的 PostgreSQL
版本中解除容器类型（如复合类型、数组或范围类型）无法使用重复数据删除。
无论使用的运算符类或校对是什么，都适用另一个实现级别的限制
INCLUDE
如果你在文档中看到任何内容不正确，与你对特定功能的体验不符或需要进一步澄清，请使用 此表单 报告文档问题。