PostgreSQL 实现

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

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

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

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

当插入的新项无法适应现有叶页时，重复数据删除过程进行缓慢。这可以防止（或至少延迟）叶页拆分。 不像 GIN 倒排列表元组，B-Tree倒排列表元组不需要在每次插入新重复项时展开;它们仅仅是叶页原始逻辑内容的替代物理表示方式。 此设计优先考虑混合读写工作负载的一致性能。 大多数客户端应用程序可以从使用重复数据删除中获得适度的性能收益。默认情况下，将启用重复数据删除。

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

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

在 MVCC下B-Tree 索引不能直接感知，同一逻辑表行可能有多个现存版本;对于索引，每个元组都是一个独立对象，需要自己的索引条目。 “Version duplicates”有时可能会累积并对其查询延迟和吞吐量产生不利影响。 这通常发生在UPDATE重的工作负载中，其中大多数单独的更新无法应用HOT优化（通常因为至少修改了一个索引列，需要一组新的索引元组版本 —一个新的元组对each and every索引）。 实际上，B-Tree重复数据删除可以改善由版本变动引起的索引膨胀。 请注意，即使唯一索引中的元组也不一定物理上唯一的，在版本变化而存储在磁盘上时。 重复数据删除优化有选择地应用于唯一索引中。它针对那些看起来具有重复版本的页面。 高级目标是给VACUUM更多的时间，在版本改动导致 “unnecessary”页面拆分之前。

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

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

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

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