B树索引（postgres）

Posted on 2025-07-10 In database

存储引擎之所以能够快速定位数据，离不开索引。B树索引是历经考验、使用最广泛的一种索引结构。pg中的B树索引是为ordinal data types（可以比较和排序）设计的。

一结构

每一个节点就是一个页（Page）。page的大小定义决定了索引node的容量；每个节点（node）由多个element组成（element包括索引key 和一个指针）。内部节点中的元素指向下一层的节点；叶子节点中的元素则指向堆中的元组。这种结构就是 PostgreSQL 中 B-Tree 索引的基础：内部节点用于导航，叶子节点保存指向真实数据的引用。

二特性

有序(Orderable): 所有 B-Tree 索引按照给定的顺序存储值，支持 ASC/DESC 和 NULLS FIRST/LAST 等排序选项
叶子结点存储数据（key以及tuple的指针），内部结点存储key
每一层除了最有结点，均存储一个高键（high key）：每个节点中最大的值。The first entry in this page contains the high key
叶子页之间有双向链表指针（左兄弟/右兄弟），用于范围扫描（BETWEEN、ORDER BY 等范围查询优化）。

三多列索引

一个索引文件，存储多列键值组合：索引条目（index tuple）中存储这几列的值作为一个组合键。
多列索引的比较是逐列进行的，先比较第1列 a，如果相等，再比较第2列 b，依次类推。pg使用逐字段比较器（每列使用其数据类型对应的 < 运算符）逐列比较
默认情况下，索引值是按照升序（ASC）排列的，但如果需要，你也可以指定为降序（DESC）。如果索引是基于单列创建的，排序顺序通常无所谓，因为扫描可以沿任意方向进行。但在多列索引中，排序顺序就变得很重要了。

PostgreSQL 多列 B-tree 索引的匹配原则

PostgreSQL 的多列索引（比如 (a, b)）是按列的最左前缀（left-prefix）顺序构建的。
能有效利用索引的条件，必须从第一列开始匹配，且满足索引的顺序关系。

PostgreSQL 多列索引中，当你只指定了“非第一列”的查询条件时，理论上有一种优化方法叫做 Skip Scan:
例如：

1 2	CREATE INDEX idx_ab ON mytable(a, b); SELECT * FROM mytable WHERE b = 42;

这个时候由于没有给出 a 的值，PostgreSQL 的 B-tree 无法用这个索引来直接查找。

但是，理论上如果第一列（a）的取值不多，比如只有 v1, v2, …, vn，查询可以被改写为多次扫描：

SELECT * FROM mytable WHERE a = v1 AND b = 42;
SELECT * FROM mytable WHERE a = v2 AND b = 42;
...
SELECT * FROM mytable WHERE a = vn AND b = 42;

每次都能利用索引 (a, b) 的“最左前缀”性质进行查找，然后再合并结果。这就是 Skip Scan 的思路。

PostgreSQL 当前不支持 Skip Scan

四 include

B-tree 索引还可以通过 INCLUDE 子句扩展额外的列，这些列不参与查找，但可以包含在索引中。

1	CREATE INDEX idx_ab_inc ON t(a, b) INCLUDE (c, d);

这样可以使某些 SELECT 查询满足 Index-Only Scan（覆盖索引），避免回表. 类似于mysql 的聚族索引（和聚族索引不同的是：include属于冗余存储）

索引属性

 SELECT p.name,
       pg_index_has_property('flights_pkey', p.name)
FROM unnest(array[
  'clusterable',
  'index_scan',
  'bitmap_scan',
  'backward_scan'
]) p(name);

      name        | pg_index_has_property
------------------+-----------------------
 clusterable      | t
 index_scan       | t
 bitmap_scan      | t
 backward_scan    | t

clusterable

clusterable 表示索引是否支持用于 CLUSTER 操作。
CLUSTER 命令会按照指定的索引顺序，对表中的数据行进行物理重排，让表的数据页顺序与索引顺序一致。
这样可以提高基于该索引的扫描性能，因为数据的物理顺序和索引顺序相同，减少随机 I/O。

使用示例

1	CLUSTER my_table USING my_index;

会根据 my_index 的顺序，重新排列 my_table 的物理存储。
聚簇后的表，在按该索引扫描时性能更好

影响和注意点

聚簇是一次性操作，执行后数据会按索引顺序存储，但后续的 INSERT、UPDATE 可能打乱这个顺序。
如果表数据频繁更新，聚簇效果会逐渐减弱，需要定期重新执行 CLUSTER。
聚簇对大表的操作比较重，执行时表会被锁。

index_scan

索引是否支持普通的 Index Scan（例如 WHERE id = 123）

bitmap_scan

Bitmap Scan 是 PostgreSQL 查询计划中的一种索引访问方法，主要用于当多个条件组合过滤时，或者单个索引扫描返回大量行时，提高访问效率的技术。
它分两步完成：

Bitmap Index Scan：先扫描索引，找到所有符合条件的行的 TID（物理行指针），把它们用一个“位图”（bitmap）来表示；
Bitmap Heap Scan：再根据这个位图去访问表的 heap 页，只读取需要的行，避免全表扫描。

为什么要用 Bitmap Scan？

当单个条件筛选出的行比较多时，普通索引扫描会频繁跳页，导致随机 I/O 增加。
多个条件联合过滤时，可以对多个索引分别做 Bitmap Index Scan，合并位图后再访问表。
通过先用位图标记符合条件的行，再按物理顺序访问表页，减少随机访问，提高缓存命中率。

优点：

适合返回大量结果的索引查询；
通过减少随机访问，降低 I/O；
支持多个索引结果合并，提高复杂查询效率。

缺点：

需要额外的内存存储位图，位图过大会消耗较多资源；
对于返回行很少的查询，普通索引扫描往往更快。

backward_scan

即索引扫描支持双向遍历：可以从索引的左端（最小键）开始向右扫描，也可以从索引的右端（最大键）开始向左扫描。例如 ORDER BY id DESC 时利用该索引

关于索引膨胀

索引可能会随着插入和删除不断膨胀，而不会自然收缩，需要通过重建或 REINDEX 来处理。

当需要向节点中插入数据而发现节点已满时，PostgreSQL 会先尝试“修剪”冗余数据（例如：删除已过期或无效的元组），希望通过回收空间来避免进一步拆分。
在 PostgreSQL 的 B-tree 实现中，节点一旦因为插入新数据而被拆分，就不会再被合并回来。哪怕后续通过 vacuum 操作清理了旧数据，节点中元素数量减少，也不会自动合并。
标准的 B-tree 数据结构理论上是支持合并操作的（比如删除数据后可合并空节点），但 PostgreSQL 的实现为了简化逻辑或出于性能原因，没有实现这一特性

参考书目

postgres internals 14

一 结构

二 特性

三 多列索引