PostgreSQL B-Tree 索引是多级树结构，其中树的每个级别都可以用作双链接的页列表。 单个元页存储在索引的第一个段文件开始时的固定位置。所有其他页都是叶页或内部页。叶页是在树的最低层上的页。 所有其他层级由内部页组成。每个叶页都包含指向表行的元组。每个内部页都包含指向树中下一级别的元组。 通常，超过 99% 的页面是叶页。 内部页和叶页都使用 第 70.6 节中描述的标准页格式。

当已有叶页不能适应传入元组时，新叶页将添加到B-Tree索引中。 page split操作通过将部分项目移动到新页面为最初属于溢出页上的项目提供空间。 页拆分还必须插入新的downlink到父页中的新页，这可能会导致父页依次拆分。 页拆分“cascade upwards”以递归的方式。 当根页最终无法适合新的下行链接时，发生root page split操作。 通过创建比原始根页高一个级别的新根页，为树结构添加新级别。

在 MVCC下B-Tree索引不能直接感知，同一个逻辑表行可能存在多个现存版本;对于一个索引来说，每个元组都是一个需要其自己的索引条目的独立的对象。 “Version churn”元组有时可能会积累，并且对查询延迟和吞吐量产生影响。 这通常发生在UPDATE较为繁重的工作负载中，其中大多数单独的更新不能应用HOT优化。 在UPDATE更改仅一个被一个索引覆盖的列期间，总是 需要一个新的索引元组 —一个用于表上的each and every索引。 特别注意，这包括没有被UPDATE进行“logically modified”的索引。 所有索引将需要一个后继的物理索引元组，用于指向表中的最新版本。 每个索引中的每个新元组通常需要与原始的“updated”元组共存很短一段时间(通常直到UPDATE事务提交后不久)。

B-Tree索引通过执行bottom-up index deletion传递，增量地删除版本混杂索引元组。 每个删除传递都是在预期的“version churn page split”反应时触发的。 这只发生在没有被UPDATE语句逻辑修改的索引上，否则将会出现集中生成特定页面中的过时版本。 通常会避免页分割，尽管某些实现级别的启发式方法可能无法识别和删除即使一个垃圾索引元组(在这种情况下，页分割或重复数据删除传递解决传入的新元组不适合叶页的问题)。 任何索引扫描必须遍历的最坏版本数(对于单个逻辑行)，是整个系统响应能力和吞吐量的重要因素。 自下而上的索引删除通道基于涉及逻辑行和版本的定性区分，针对单个叶页中的可疑垃圾元组。 bottom-up的索引删除传递针对单个叶页中的可疑垃圾元组，基于涉及逻辑行和版本的quantitative差异。 这与autovacuum workers执行的“top-down”索引清理形成对比，其在某些quantitative表级阈值超过时触发(参见 第 25.1.6 节)。

Bottom-up索引删除为具有某些工作负载的特定索引执行绝大多数垃圾索引元组清理。 对任何B-Tree索引，如果它从UPDATE受到明显的版本混杂，而几乎没有或从未有逻辑更改该索引所覆盖的列，这是可以预见的。 每个逻辑行的平均和最坏情况的版本数可以通过目标增量删除传递以保持较低。 尽管从 UPDATEconstant 进行了版本混杂，但某些索引的磁盘大小很可能永远不会增加哪怕一个页面/块。 尽管如此，一个由VACUUM操作(通常在autovacuum worker进程中运行)的彻底的“clean sweep” 将最终需要作为表和它的每个索引的集体清理的一部分。

不像VACUUM，bottom-up索引删除不提供任何关于最古老的垃圾索引元组有多长时间的强保证。 没有索引可以被允许保留在由表和所有它的索引共享的保守截止点之前已经失效的“floating garbage”索引元组。 这个基本的表级不变量使得回收利用表的TID是安全的。 这就是为什么不同的逻辑行可以随着时间的推移而重新使用相同的表TID(尽管这在生命周期跨越相同的VACUUM周期的两个逻辑行中永远不会发生)。

重复项是叶页元组（指向表行的元组），其中所有 索引键列的值与同一索引中至少一个其他叶页元组的相应列值匹配。 重复元组在实践中很常见。 当启用可选技术：重复时，B-Tree 索引可以对重复项使用特殊的、节省空间的表达方式。

重复数据删除的工作为通过定期将重复元组合并在一起，为每个组构建一个posting list元组。 列键值在此表示形式中仅显示一次。 后面跟着指向表中行的TID的排序数组。 这显著减少了索引的存储大小，在其中每个值（或列值的每个不同组合）平均出现多次时。 查询的延迟可以显著降低。 总体查询吞吐量可能会显著增加。 常规索引清空的开销也可以显著降低。

当插入的新项无法适应现有叶页时，重复数据删除过程进行缓慢，虽然只有当索引元组删除不能为新项释放足够的空间时(通常删除会被简单考虑然后跳过) 不像 GIN 倒排列表元组，B-Tree倒排列表元组不需要在每次插入新重复项时展开;它们仅仅是叶页原始逻辑内容的替代物理表示方式。 此设计优先考虑混合读写工作负载的一致性能。 大多数客户端应用程序可以从使用重复数据删除中获得适度的性能收益。默认情况下，将启用重复数据删除。

CREATE INDEX和 REINDEX 应用重复数据删除来创建倒排列表元组，尽管它们使用的策略有所不同。 每组重复的普通元组遇到从表中取出的排序输入将合并到倒排列表元组，在添加到当前挂起的叶页之前。 单独倒排列表元组尽可能以TIDs封装。 叶页以通常的方式写出，没有任何分开的重复数据删除步骤。 此策略非常适合CREATE INDEX和REINDEX，因为它们是一次性的批处理操作。

由于索引中重复值很少或没有重复值，因此无法从重复数据删除中获益的写频繁工作负载将产生少量的、固定性能损耗（除非显式禁用重复数据删除）。 deduplicate_items存储参数可用于禁用单个索引中的重复数据消除。 只读工作负载永远不会有任何性能损失，因为读取倒排列表元组至少与读取标准元组表示一样高效。 禁用重复数据删除通常没有帮助。

有的时候惟一索引(以及惟一约束)可能被使用重复数据删除。 这允许叶页临时“absorb” 额外的版本混杂副本。 唯一索引中的重复数据删除增强了bottom-up索引删除，特别是在长时间运行的事务持有块垃圾收集的快照的情况下。 目的是为了bottom-up索引删除策略变得再次生效争取时间。 延迟分页分割，直到单个长时间运行的事务自然消失，可以允许bottom-up删除传递成功，在较早的删除传递失败的地方。

由于实现级别的限制，不能在所有情况下使用重复数据消除。 在CREATE INDEX 或 REINDEX时决定重复数据删除安全性。

请注意，重复数据删除被认为是不安全的，不能用于下列涉及相同数据之间语义显著差异的情况:

在未来版本的PostgreSQL中，还有一个实现级限制可能取消：

无论使用操作符类或排序规则如何，还有一个实现级别限制适用：