# 64.4.实施

64.4.1. B-树结构

64.4.2. 自下而上索引删除

64.4.3. 重复数据消除

本节介绍可能对高级用户有用的B树索引实现细节。看见src/backend/access/nbtree/README在源代码发行版中,我们将对B-Tree实现进行更详细、更注重内部的描述。

# 64.4.1.B-树结构

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

当现有叶页无法容纳传入元组时,会将新叶页添加到B树索引中。A.分页符该操作通过将部分项目移动到新页面,为原本属于溢出页面的项目腾出空间。页面拆分还必须插入新的下行链路到父页面中的新页面,这可能会导致父页面依次拆分。页面以递归方式拆分“向上级联”。当根页面最终无法适应新的下行链路时根页拆分行动开始了。这将通过创建比原始根页面高一级的新根页面,向树结构添加一个新级别。

# 64.4.2.自下而上索引删除

B树索引并不直接知道在MVCC下,同一逻辑表行可能存在多个现存版本;对于索引,每个元组都是一个独立的对象,需要自己的索引项。“版本搅动”元组有时可能会累积,并对查询延迟和吞吐量产生不利影响。这通常发生在使现代化-大多数个别更新无法应用热优化的繁重工作负载。在搜索过程中仅更改一个索引所覆盖的一列的值使现代化 总是需要一组新的索引元组——一个用于每一个桌子上的索引。请特别注意,这包括未被使现代化。所有索引都需要一个指向表中最新版本的后续物理索引元组。每个索引中的每个新元组通常需要与原始“更新”元组在短时间内共存(通常直到更新后不久)使现代化事务提交)。

B树索引通过执行自下而上的索引删除通行证。每次删除都会触发,以响应预期的“版本搅动页面分割”。这种情况只会发生在未按逻辑修改的索引上使现代化语句,否则会在特定页面集中构建过时版本。通常可以避免页面分割,尽管某些实现级别的启发式算法可能无法识别和删除哪怕是一个垃圾索引元组(在这种情况下,页面分割或重复数据消除过程可以解决传入的新元组不适合叶页的问题)。任何索引扫描(对于任何单个逻辑行)必须遍历的最坏版本数对整个系统的响应性和吞吐量都有重要影响。自下而上的索引删除过程基于质量的涉及逻辑行和版本的区别。这与autovacuum workers执行的“自上而下”索引清理形成对比,后者在某些情况下会触发定量性的超过表级阈值(请参阅第25.1.6节).

# 笔记

并非在B树索引中执行的所有删除操作都是自底向上的删除操作。索引元组删除有一个独特的类别:简单索引元组删除。这是一个延迟维护操作,用于删除已知可以安全删除的索引元组(其项标识符为LP_死亡位已设置)。与自底向上的索引删除一样,简单的索引删除发生在预期页面拆分时,作为避免拆分的一种方式。

简单删除是机会主义的,因为它只能在最近的索引扫描设置LP_死亡一些受影响的物品正在传递。在PostgreSQL 14之前,B-树删除的唯一类别是简单删除。它和自底向上删除的主要区别在于,只有前者是由通过索引扫描的活动机会性地驱动的,而只有后者专门针对来自使现代化不在逻辑上修改索引列的。

自下而上的索引删除对具有特定工作负载的特定索引执行绝大多数垃圾索引元组清理。这是预期的任何B-树索引,是受重大版本流失从使现代化它很少或从不在逻辑上修改索引覆盖的列。每个逻辑行的平均版本数和最坏版本数可以通过有针对性的增量删除过程保持在较低水平。某些索引的磁盘大小很可能永远不会增加一个页面/块,尽管常数版本从使现代化s、 即使在那时,一场彻底的“大扫除”真空操作(通常在自动真空工作过程中运行)最终将作为操作的一部分集体的清理表及其每个索引。

不像真空,自下而上的索引删除并不能很好地保证最早的垃圾索引元组的年龄。不允许任何索引保留“浮动垃圾”索引元组,这些元组在表及其所有索引共同共享的保守截止点之前已失效。这个基本的表级不变量使回收表TID变得安全。这就是为什么不同的逻辑行可以随着时间的推移重用同一个表TID(尽管这永远不会发生在两个生命周期相同的逻辑行上)真空循环)。

# 64.4.3.重复数据消除

重复是一个叶页元组(指向表行的元组),其中全部的索引键列的值与同一索引中至少一个其他叶页元组的对应列值相匹配。重复元组在实践中很常见。启用可选技术时,B树索引可以对重复项使用特殊的、节省空间的表示:重复数据消除.

重复数据消除的工作原理是定期将多组重复元组合并在一起,形成一个倒排表每组的元组。列键值在此表示形式中仅出现一次。然后是指向表中行的TID排序数组。这显著减少了索引的存储大小,其中每个值(或列值的每个不同组合)平均出现几次。查询的延迟可以显著减少。总体查询吞吐量可能会显著增加。常规索引清理的开销也可以显著减少。

# 笔记

B-Tree重复数据消除对于包含空值的“副本”同样有效,尽管根据不同的定义,空值永远不相等=任何B-树运算符类的成员。就理解磁盘上B树结构的实现的任何部分而言,NULL只是索引值域中的另一个值。

重复数据消除过程会缓慢进行,即插入的新项不能放在现有叶页上,但仅当索引元组删除无法为新项释放足够的空间时(通常会短暂考虑删除,然后跳过)。与GIN发布列表元组不同,B树发布列表元组不需要在每次插入新副本时展开;它们只是叶页原始逻辑内容的另一种物理表示。这种设计优先考虑混合读写工作负载的一致性能。大多数客户端应用程序至少会从使用重复数据消除中看到适度的性能优势。默认情况下启用重复数据消除。

创建索引重新索引应用重复数据消除来创建发布列表元组,尽管它们使用的策略略有不同。从表中获取的排序输入中遇到的每组重复的普通元组被合并到一个发布列表元组中之前正在添加到当前挂起的叶页。单个发布列表元组中包含尽可能多的TID。叶页以通常的方式写入,没有任何单独的重复数据消除过程。这种策略非常适合于创建索引重新索引因为它们是一次性的批处理操作。

写繁重的工作负载时,如果由于索引中的重复值很少或没有重复值而无法从重复数据消除中获益,则会导致较小的固定性能损失(除非明确禁用重复数据消除)。这个重复数据消除_项storage参数可用于禁用单个索引中的重复数据消除。只读工作负载永远不会有任何性能损失,因为读取发布列表元组至少与读取标准元组表示一样高效。禁用重复数据消除通常没有帮助。

有时,唯一索引(以及唯一约束)可以使用重复数据消除。这允许叶页暂时“吸收”多余的翻版副本。在唯一索引中进行重复数据消除会增强自底向上的索引删除,尤其是在长时间运行的事务包含阻止垃圾收集的快照的情况下。我们的目标是为自下而上的索引删除策略重新生效争取时间。如果将页面拆分延迟到单个长时间运行的事务自然消失,则在早期删除过程失败的情况下,自底向上的删除过程可以成功。

# 提示

使用一种特殊的启发式方法来确定是否应在唯一索引中进行重复数据消除。它通常可以直接跳到拆分一个叶页,从而避免因在无用的重复数据消除过程中浪费周期而导致的性能损失。如果你担心重复删除的开销,考虑设置重复数据消除_项=关闭选择性地。在唯一索引中启用重复数据消除几乎没有负面影响。

由于实施级别的限制,无法在所有情况下使用重复数据消除。重复数据消除的安全性取决于创建索引重新索引他跑了。

请注意,重复数据消除被视为不安全的,并且不能在以下情况下使用,这些情况涉及相同基准之间的语义显著差异:

  • 文本, 瓦尔查尔烧焦不能使用重复数据删除时非确定性的使用排序规则。大小写和重音差异必须保留在相同的基准之间。

  • 数字不能使用重复数据删除。数字显示比例必须保留在相等的基准之间。

  • jsonb不能使用重复数据删除,因为jsonbB-Tree 运算符类使用数字内部。

  • 浮动4浮动8不能使用重复数据删除。这些类型有不同的表示-00,但仍被认为是相等的。必须保留这种差异。

    在 PostgreSQL 的未来版本中可能会取消另一个实现级别的限制:

  • 容器类型(例如复合类型、数组或范围类型)不能使用重复数据删除。

    无论使用何种操作符类或排序规则,还有一个实现级别的限制适用:

  • 包括索引永远不能使用重复数据删除。