登录67.4. 实现#
本节介绍 B 树索引实现的详细信息，高级用户可能需要了解这些信息。有关 B 树实现的更详细、更注重内部的描述，请参阅源代码发行版中的src/backend/access/nbtree/README。
67.4.1. B 树结构#
PostgreSQLB 树索引是多级树结构，其中树的每一级都可用作页面的双向链表。单个元页面存储在索引的第一个段文件开始处的固定位置。所有其他页面都是叶页面或内部页面。叶页面是树最底层的页面。所有其他级别都由内部页面组成。每个叶页面都包含指向表行的元组。每个内部页面都包含指向树中下一级的元组。通常，超过 99% 的页面都是叶页面。内部页面和叶页面都使用第 73.6 节中描述的标准页面格式。
当现有叶页面无法容纳传入元组时，将向 B 树索引添加新的叶页面。页面拆分操作通过将部分项目移动到新页面，为原本属于溢出页面的项目腾出空间。页面拆分还必须在父页面中插入一个指向新页面的新下行链接，这可能导致父页面反过来拆分。页面拆分以递归方式“向上级联”。当根页面最终无法容纳新的下行链接时，将执行根页面拆分操作。这通过创建一个比原始根页面高一级的新的根页面，为树结构添加一个新级别。
67.4.2. 自底向上索引删除#
B 树索引并不知道在 MVCC 下同一逻辑表行可能有多个现有版本；对于索引，每个元组都是一个独立的对象，需要自己的索引条目。“版本转换”元组有时可能会累积，并对查询延迟和吞吐量产生不利影响。这通常发生在UPDATE繁重的工作负载中，其中大多数单独更新无法应用HOT优化。在UPDATE期间仅更改一个索引覆盖的一列的值始终需要一组新的索引元组——对于表上的每个索引来说都是如此。特别注意，这包括未被UPDATE“逻辑修改”的索引。所有索引都需要一个后继物理索引元组，指向表中的最新版本。每个索引中的每个新元组通常需要与原始“已更新”元组在短时间内共存（通常在UPDATE事务提交后不久）。
B 树索引通过执行自底向上的索引删除传递来递增删除版本转换索引元组。每次删除传递都是针对预期的“版本转换页面拆分”而触发的。这仅发生在未被UPDATE语句逻辑修改的索引中，否则特定页面中废弃版本的集中累积将发生。通常会避免页面拆分，但某些实现级别的启发式方法可能无法识别和删除甚至一个垃圾索引元组（在这种情况下，页面拆分或重复数据删除传递会解决新传入元组不适合叶页面的问题）。任何索引扫描必须遍历的版本的最坏情况数量（对于任何单个逻辑行）是整体系统响应能力和吞吐量的关键因素。自底向上的索引删除传递基于涉及逻辑行和版本的定性区别，针对单个叶页面中的可疑垃圾元组。这与自动清理工作程序执行的“自顶向下”索引清理形成对比，后者在超过某些定量表级别阈值时触发（请参阅第 25.1.6 节）。
注意
并非所有在 B 树索引中执行的删除操作都是自下而上的删除操作。索引元组删除有一个不同的类别：简单索引元组删除。这是一个延迟维护操作，用于删除已知可以安全删除的索引元组（其项目标识符的LP_DEAD位已设置）。与自下而上的索引删除类似，简单索引删除发生在预期页面拆分时，以此作为避免拆分的一种方式。简单删除是机会主义的，因为只有在最近的索引扫描在经过时设置受影响项目的LP_DEAD位时，它才能发生。在PostgreSQL14 之前，B 树删除的唯一类别是简单删除。它与自下而上删除之间的主要区别在于，只有前者是由经过的索引扫描的活动机会主义驱动的，而后者专门针对不会从逻辑上修改索引列的UPDATE的版本更新。
自下而上的索引删除对具有特定工作负载的特定索引执行绝大多数所有垃圾索引元组清理。对于任何 B 树索引，如果它受到很少或从不从逻辑上修改索引涵盖的列的UPDATE的重大版本更新的影响，则这是预期的。每个逻辑行的平均版本数和最差情况版本数可以通过有针对性的增量删除传递纯粹保持较低。尽管UPDATE的版本更新持续进行，但某些索引的磁盘大小完全有可能不会增加一页/块。即使这样，VACUUM操作（通常在自动清理工作进程中运行）的详尽“彻底清理”最终将作为表及其每个索引的集体清理的一部分而需要。
与VACUUM不同，自下而上的索引删除不会对最旧的垃圾索引元组可能有多旧提供任何强有力的保证。不允许任何索引保留“浮动垃圾”索引元组，这些元组在表和所有索引共同共享的保守截止点之前已变为无效。此基本表级别不变性使得回收表TID变得安全。这就是随着时间的推移，不同的逻辑行可以重复使用同一表TID的方式（尽管对于两个逻辑行来说，如果其生命周期跨越同一VACUUM周期，则永远不会发生这种情况）。
67.4.3. 重复数据删除#
重复项是叶页元组（指向表行的元组），其中所有索引键列的值与同一索引中至少一个其他叶页元组的相应列值匹配。在实践中，重复元组非常常见。当启用可选技术时，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无法使用重复数据删除，因为jsonbB 树操作符类在内部使用numeric。float4和float8无法使用重复数据删除。这些类型对-0和0有不同的表示形式，但仍被视为相等。必须保留此差异。
在未来版本的PostgreSQL中，可能会解除一项进一步的实现级限制
容器类型（例如复合类型、数组或范围类型）不能使用重复数据删除。
有一项进一步的实现级限制适用于无论使用何种运算符类或排序规则
INCLUDE索引永远不能使用重复数据删除。