PostgreSQL 包含标准 btree(多路平衡树)索引数据结构的一种实现。 任何能够被排序成明确线性顺序的数据类型都可以由 btree 索引来建立 索引。唯一的限制是索引条目不能超过大约一页的三分之一(在适用的情况下 经过 TOAST 压缩之后)。
由于每个 btree 操作符类都对它的数据类型施加一种排序顺序,btree 操作符 类(或者实际上是操作符族)已经演变为 PostgreSQL 对排序语义的一般性表示和理解。 因此,它们获得了一些超出支持 btree 索引所需范围的特征,系统中远离 btree AM 的部分也会利用它们。
如 Table 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 放进同一个操作符族是行不通的,至少在
numeric 值为与 float8 比较而被转换为
float8 的当前语义下不行。由于
float8 的精度有限,这意味着存在不同的
numeric 值会与同一个 float8 值比较相等,
于是传递律就会失效。
多数据类型族的另一个要求是:在包含于操作符族中的数据类型之间定义的 任何隐式或二进制强转都不得改变相关的排序顺序。
btree 索引为什么要求这些定律在单一数据类型内成立应当相当清楚:没有 它们就没有可用来排列键的顺序。此外,使用不同数据类型的比较键进行 索引搜索,要求比较在两种数据类型之间保持合理。把一个族扩展到三种或 更多数据类型并非 btree 索引机制本身的严格要求,但规划器出于优化目的 依赖这些性质。
如 Table 36.9 所示,btree 定义了 一个必需的和五个可选的支持函数。这六个 用户定义的方法是:
order
对于 btree 操作符族提供比较操作符的每种数据类型组合,它必须提供
一个比较支持函数,在
pg_amproc 中以支持函数编号 1
注册,且
amproclefttype/amprocrighttype
等于比较的左右数据类型(即与匹配操作符在
pg_amop 中注册的数据类型相同)。
比较函数必须接收两个非空值
A 和 B,并
返回一个 int32 值:当 A
< B、
A =
B 或 A
> B 时,分别返回
< 0、
0 或 >
0。不允许空结果:该数据类型的所有值都必须可
比较。
示例参见
src/backend/access/nbtree/nbtcompare.c。
如果被比较的值属于可排序(collatable)数据类型,适当的排序规则
OID 会通过标准的
PG_GET_COLLATION() 机制传给比较
支持函数。
sortsupport
btree 操作符族可以选择性地提供排序
支持函数,注册在支持函数编号 2 下。
这些函数允许以比直接调用比较支持函数更高效的方式实现用于排序的
比较。相关的 API 定义在
src/include/utils/sortsupport.h 中。
in_range
btree 操作符族可以选择性地提供
in_range 支持函数,注册
在支持函数编号 3 下。它们不用于 btree 索引操作;而是扩展操作符族
的语义,使它能够支持包含 RANGE
offset
PRECEDING 和 RANGE
offset FOLLOWING
帧边界类型(见 Section 4.2.8)的窗口子句。
从根本上说,提供的额外信息是:如何以一种与族内数据排序兼容的方式
加上或减去一个 offset 值。
in_range 函数必须具有签名
in_range(valtype1,basetype1,offsettype2,subbool,lessbool) returns bool
val 和
base 必须是相同类型,该类型是操作符族
支持的类型之一(即它为其提供排序的类型)。
而 offset 可以是不同的类型,它可以是
族原本不支持的类型。例如,内建的 time_ops 族
提供了一个 offset 为 interval
类型的 in_range 函数。
操作符族可以为它的任何受支持类型以及一个或多个
offset 类型提供
in_range 函数。每个
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),错误文本类似
“invalid preceding or
following size in window function”。(这是 SQL 标准要求的,
不过非标准操作符族也许可以选择忽略这一限制,因为这似乎没有什么
语义上的必要。)这一要求被委托给
in_range 函数,这样核心代码就不必理解对特定
数据类型而言“小于零”意味着什么。
另一个额外的期望是:in_range
函数应尽可能避免在 base
+
offset 或
base -
offset 溢出时抛出错误。
即使该值超出数据类型的范围,也能确定正确的比较结果。
注意,如果数据类型包含“无穷”或
“NaN” 之类的概念,可能需要额外的注意,以确保
in_range 的结果与操作符族的正常排序顺序
一致。
in_range 函数的结果必须与操作符族施加的排序
顺序一致。准确地说,给定任何固定的
offset 和
sub 值,则:
如果 less = true 的
in_range 对某个
val1 和
base 为真,那么对具有相同
base 的每个
val2 <=
val1 也必须为真。
如果 less = true 的
in_range 对某个
val1 和
base 为假,那么对具有相同
base 的每个
val2 >=
val1 也必须为假。
如果 less = true 的
in_range 对某个
val 和
base1 为真,那么对具有相同
val 的每个
base2 >=
base1 也必须为真。
如果 less = true 的
in_range 对某个
val 和
base1 为假,那么对具有相同
val 的每个
base2 <=
base1 也必须为假。
当 less = false 时,条件反转的类似陈述
同样成立。
如果被排序的类型(type1)是可排序的,适当的排序规则
OID 会通过标准
PG_GET_COLLATION() 机制传给
in_range 函数。
in_range 函数无需处理 NULL
输入,通常会被标记为严格。
equalimage
btree 操作符族可以选择性地提供
equalimage(“相等即镜像相等”)
支持函数,注册在支持函数编号 4 下。
这些函数允许核心代码判断何时可以安全地应用 btree 去重
优化。目前,equalimage
函数只在构建或重建索引时被调用。
equalimage 函数必须具有
签名
equalimage(opcintypeoid) returns bool
返回值是关于操作符类和排序规则的静态信息。
返回 true 表示
该操作符类的 order 函数保证只在
其 A 和
B 参数互换且不损失任何语义信息时才返回
0(“参数相等”)。
不注册 equalimage 函数或返回
false 表示不能假定这一条件成立。
opcintype 参数是该操作符类建立索引的
数据类型的
。
这是一个便利设计,允许跨操作符类复用同一个底层
pg_type.oidequalimage 函数。
如果 opcintype 是可排序数据
类型,适当的排序规则 OID 会通过标准
PG_GET_COLLATION() 机制传给
equalimage 函数。
就操作符类而言,返回
true 表示去重是安全的(或对其
equalimage 函数收到的 OID 对应的排序规则
安全)。不过,只有当每个被索引列都使用注册
了 equalimage 函数的操作符类,且每个函数被
调用时确实返回 true 时,核心代码才会认为某个
索引的去重是安全的。
镜像相等与简单的按位相等几乎是同一个条件。
存在一个微妙的区别:当为 varlena 数据类型建立索引时,
两个镜像相等的 datum 的磁盘表示可能因为输入上不一致地应用
TOAST 压缩而并非按位相等。
形式上说,当操作符类的
equalimage 函数返回
true 时,可以安全地假定
datum_image_eq() C 函数将始终与操作符类的
order 函数一致
(前提是相同的排序规则 OID 被同时传给
equalimage 和 order
函数)。
核心代码从根本上无法根据同一族内其他操作符类的细节来推断多数据
类型族中某个操作符类的
“相等即镜像相等”状态。此外,让操作符族注册跨类型的
equalimage 函数是不合理的,尝试这样做会导致
错误。这是因为
“相等即镜像相等”状态不只取决于更多在操作符族层面
定义的排序/相等语义。一般而言,某个特定数据类型实现的语义必须
单独考虑。
核心 PostgreSQL 发行版所含操作符类
遵循的约定是注册一个通用的现成
equalimage 函数。
大多数操作符类注册
btequalimage(),它表明去重无条件地安全。
text 等可排序数据类型的操作符类注册
btvarstrequalimage(),它表明在确定性排序规则
下去重是安全的。第三方扩展的最佳实践是注册自己的自定义函数,以
保留控制权。
options
B-tree 操作符族可以选择性地提供
options(“操作符类特有
选项”)支持函数,注册在支持
函数编号 5 下。这些函数定义一组控制操作符类行为的用户可见
参数。
options 支持函数必须具有
签名
options(reloptslocal_relopts *) returns void
该函数会接收一个指向 local_relopts
结构的指针,该结构需要被填充为一组操作符类特定的选项。
其他支持函数可以使用
PG_HAS_OPCLASS_OPTIONS() 和
PG_GET_OPCLASS_OPTIONS() 宏来访问这些选项。
目前,没有任何 B-Tree 操作符类拥有
options
支持函数。B-tree 不像 GiST、SP-GiST、GIN 和 BRIN 那样允许键的
灵活表示。因此,options
在当前的 B-tree 索引访问方法中可能没有太大用处。
尽管如此,为了统一性,这个支持函数仍被加入了 B-tree,在
PostgreSQL 中 B-tree 的进一步演化过程
中可能会找到用途。
skipsupport
btree 操作符族可以选择性地提供一个
skip
支持函数,注册在支持函数编号 6 下。
这些函数为 B-tree 代码提供了一种按键空间顺序遍历操作符类底层输入
类型所能表示的每个可能值的方法。
核心代码在应用 skip scan 优化时会使用它。
相关的 API 定义在
src/include/utils/skipsupport.h 中。
未提供 skip 支持函数的操作符类仍然有资格使用 skip scan。 核心代码仍可以使用其回退策略,但对某些离散类型而言那可能是次优 的。对连续类型上的操作符类而言,提供 skip 支持函数通常没有意义 (甚至可能不可行)。
让操作符族注册跨类型的
skipsupport 函数是不合理的,尝试这样做会导致
错误。这是因为确定下一个可索引值必须通过递增从索引元组复制来的值
来完成。生成的值必须都属于相同的底层数据类型
(即被 skip 的索引列的操作符类输入类型)。
本节介绍可能对高级用户有用的 B-Tree 索引实现细节。
有关 B-Tree 实现的更详细、更侧重内部机制的描述,请参阅源码发行版中的
src/backend/access/nbtree/README。
PostgreSQL B-Tree 索引是多级树结构,树的 每一层都可以被用作页面的双向链表。 一个元页面被存储在索引第一个段文件的固定起始位置。 所有其他页面要么是叶页面,要么是内部页面。 叶页面是树最底层的页面。所有其他层级由内部页面组成。 每个叶页面包含指向表行的元组。每个内部页面包含指向树中下一层级的 元组。通常,所有页面中超过 99% 都是叶页面。 内部页面和叶页面都使用 Section 66.6 中描述的标准页面格式。
当现有的叶页面无法容纳到来的元组时,就会向 B-Tree 索引添加新的叶 页面。页面 拆分操作通过把一部分条目移到新页面,为原本属于溢出页面的 条目腾出空间。 页面拆分还必须在父页面中插入指向新页面的新 下行链接,这又可能导致父页面拆分。 页面拆分以递归的方式 “向上级联”。 当根页面最终无法容纳新的下行链接时,会发生 根页面拆分操作。 这会通过创建一个位于原根页面之上一个层级的新根页面,为树结构添加 一个新的层级。
B-Tree 索引并不直接知道在 MVCC 之下,同一个逻辑表行可能存在多个
现存版本;对索引来说,每个元组都是一个需要自己的索引条目的独立
对象。“版本搅动”元组有时会累积,并对查询延迟和吞吐量
产生不利影响。
这通常发生在 UPDATE 密集的工作负载中,而且大多数
单个更新无法应用
HOT 优化。
在 UPDATE 期间只改变被某个索引覆盖的一列的值
总是需要一组新的索引元组
— 对表中
每一个索引各一个。
特别注意,这包括那些没有被该 UPDATE
“逻辑修改”的索引。
所有索引都需要一个指向表中最新版本的后继物理索引元组。
每个索引中的每个新元组一般都需要与原始的
“被更新的”元组共存一小段时间(通常持续到
UPDATE 事务提交后不久)。
B-Tree 索引通过执行自底向上的索引删除轮次
来增量地删除版本搅动索引元组。
每个删除轮次都是针对一次预料中的
“版本搅动页面拆分”而触发的。
这只发生在没有被 UPDATE 语句逻辑修改的索引上,
否则过时版本会在特定页面集中堆积。
页面拆分通常会被避免,不过某些实现层面的启发式方法有可能连一个
垃圾索引元组都识别和删除不了(这种情况下,页面拆分或去重轮次会
解决到来的新元组放不进叶页面的问题)。
任何索引扫描必须遍历的版本数(对任何单个逻辑行而言)的最坏情况
对整个系统的响应能力和吞吐量有重要影响。
自底向上的索引删除轮次基于涉及逻辑行和版本的
定性区别,来定位单个叶页面中疑似垃圾的
元组。
这与 autovacuum 工作进程执行的
“自顶向下”索引清理形成对比,后者在超过某些
定量的表级阈值时被触发(见
Section 24.1.6)。
并非在 B-Tree 索引内执行的所有删除操作都是自底向上的删除操作。
还有一类独特的索引元组删除:简单索引元组
删除。这是一种延迟维护操作,删除那些已知可以安全
删除的索引元组(其条目标识符的 LP_DEAD 位
已被置位的那些)。与自底向上索引删除一样,简单索引删除也发生在
页面拆分被预料到的时刻,作为避免拆分的手段。
简单删除是机会性的,也就是说它只能在最近的索引扫描顺路设置了受
影响条目的 LP_DEAD 位时发生。
在 PostgreSQL 14 之前,B-Tree 删除的
唯一类别就是简单删除。
它与自底向上删除的主要区别在于:只有前者由经过的索引扫描活动
机会性地驱动,而只有后者专门针对不逻辑修改被索引列的
UPDATE 所产生的版本搅动。
对于某些工作负载下的特定索引而言,自底向上索引删除承担了全部垃圾
索引元组清理的绝大部分。
对于任何一个会受到极少或从不逻辑修改其覆盖列的
UPDATE 所带来的显著版本搅动影响的 B-Tree
索引,这都是预期行为。
每个逻辑行的平均和最坏情况版本数可以纯粹通过有针对性的增量删除
轮次保持在较低水平。
尽管 UPDATE 带来
持续的版本搅动,某些索引的磁盘大小完全可能
一个页面/块都不增加。
即便如此,由 VACUUM 操作(通常在 autovacuum
工作进程中运行)进行的彻底
“大扫除”最终仍会被要求,作为对表及其每个索引进行
集体清理的一部分。
与 VACUUM 不同,自底向上索引删除对最老的垃圾
索引元组的年龄不提供任何强保证。
不允许任何索引保留
“悬浮垃圾”索引元组,即死于一由表及其所有索引集体共享
的保守截止点之前的索引元组。
这条基本的表级不变式使得回收表
TID 变得安全。
正因如此,不同的逻辑行才有可能在一段时间后重用同一个表
TID(不过生命周期跨越同一个
VACUUM 周期的两个逻辑行绝不会发生这种事)。
重复项是一种叶页面元组(指向表行的元组),它的 所有被索引键列的值都与同一索引中至少另一个 叶页面元组的对应列值匹配。重复元组在实践中相当常见。 当一种可选技术被启用时,B-Tree 索引可以对重复项使用一种特殊的、 节省空间的表示:去重。
去重的工作方式是周期性地把重复元组合并成组,为每组形成一个单独的 posting list 元组。 列键值在这种表示中只出现一次。 其后是一个指向表中各行的、已排序的 TID 数组。 这显著降低了每个值(或每个不同的列值组合)平均出现多次的索引的 存储大小。 查询的延迟可以显著降低。整体查询吞吐量可能显著提升。 例行索引清理的开销也可能显著减少。
即使重复项包含 NULL 值,B-Tree 去重也同样有效,尽管根据任何
B-Tree 操作符类的 = 成员,NULL 值彼此从不
相等。就任何理解磁盘上 B-Tree 结构的实现部分而言,
NULL 只是被索引值域中的另一个值。
去重过程是懒惰进行的:当无法放进现有叶页面的新条目被插入时才 发生,而且只在索引元组删除无法为新条目腾出足够空间时进行 (通常删除只是被短暂考虑一下然后跳过)。 与 GIN posting list 元组不同,B-Tree posting list 元组不需要在每次 插入新重复项时扩展;它们只是叶页面原始逻辑内容的一种替代物理 表示。这一设计优先考虑混合读写工作负载下的稳定性能。 大多数客户端应用至少能从去重中获得适度的性能收益。 去重默认是启用的。
CREATE INDEX 和 REINDEX
会应用去重来创建 posting list 元组,不过它们使用的策略略有不同。
在从表中取得的已排序输入中遇到的每组重复普通元组,都会在被加入
当前待处理的叶页面之前被合并为一个 posting
list 元组。
单个 posting list 元组会被尽量多地打包
TID。
叶页面按常规方式写出,没有任何单独的去重轮次。
这一策略非常适合 CREATE INDEX 和
REINDEX,因为它们是一次性的批处理操作。
索引中很少或没有重复值、因而无法从去重中获益的重写工作负载,会
承担一个小的固定性能惩罚(除非显式禁用去重)。
deduplicate_items 存储
参数可用于在单个索引内禁用去重。
只读工作负载从来没有任何性能惩罚,因为读取 posting list 元组至少
与读取标准元组表示一样高效。
禁用去重通常没什么帮助。
有时唯一索引(以及唯一约束)也可以使用去重。 这允许叶页面暂时 “吸收”额外的版本搅动重复项。 唯一索引中的去重是对自底向上索引删除的补充,尤其是在长事务持有 阻止垃圾回收的快照的情况下。 其目标是为自底向上索引删除策略重新发挥作用争取时间。 把页面拆分推迟到单个长事务自然消失,可以让一次自底向上删除轮次 在先前失败的场合取得成功。
有一个特殊的启发式方法用来决定唯一索引中是否应当进行去重
轮次。
它常常可以直接跳到叶页面拆分,避免把周期浪费在无益的去重轮次上
造成的性能惩罚。
如果您担心去重的开销,可以考虑有选择地设置
deduplicate_items = off。
在唯一索引中保留去重启用几乎没有什么坏处。
由于实现层面的限制,去重无法在所有情况下使用。
去重的安全性在 CREATE INDEX 或
REINDEX 运行时决定。
注意,在以下涉及相等 datum 之间存在语义上显著差异的情况下,去重 被视为不安全且不能使用:
使用非确定性排序规则时,
text、varchar 和 char
不能使用去重。
大小写和重音差异必须在相等的 datum 之间保留。
numeric 不能使用去重。
数值显示精度必须在相等的 datum 之间保留。
jsonb 不能使用去重,因为
jsonb B-Tree 操作符类在内部使用
numeric。
float4 和 float8 不能使用
去重。这些类型对 -0 和
0 有不同的表示,尽管它们被视为相等。
这一差异必须保留。
还有一个实现层面的限制,可能会在 PostgreSQL 的未来版本中被移除:
容器类型(例如复合类型、数组或范围类型)不能使用去重。
还有一个实现层面的限制,无论使用何种操作符类或排序规则都适用:
INCLUDE 索引永远不能使用去重。