BRIN 与其他索引：什么时候不建 B-Tree 反而更好

如果你有一张 1TB 的传感器数据表，按时间列 ts 查询某一天的数据。建 B-Tree 索引需要扫描每一行、排序、写 WAL——索引本身可能 200GB，建索引跑一下午。但你会本能地意识到这件事的荒谬：ts 列的值天然有序，新数据 ts 越来越大，ts 与物理存储位置高度相关。有没有一种索引，只利用”page range 内的最大值和最小值”，而不逐行建立指针？

有。BRIN（Block Range INdex）做的事情就是这个。它不是 B-Tree 的替代品，而是在”数据物理有序、表太大、查询只关心范围”的场景下，把索引空间和时间开销从 \(O(n)\) 降到 \(O(n/\text{range\_size})\)。

本文从 BRIN 的内部结构（revmap + summary tuple）出发，说明它如何用极小的代价提供范围过滤能力。随后讨论另外两种”不建 B-Tree”的索引：Hash 索引的 WAL 安全边界，以及 Bloom 索引的多列任意组合过滤场景。最后给出索引选择的代价对比表和决策树。

一、BRIN 的哲学：范围摘要替代逐行索引

问题场景

CREATE TABLE sensor_data (
    ts      TIMESTAMPTZ,
    dev_id  INTEGER,
    temp    DOUBLE PRECISION
);

-- 每天 1000 万行，运行一年
-- 总行数：~36 亿
-- 表大小：~300GB

-- 常见查询：查某一天的温度
SELECT * FROM sensor_data
WHERE ts BETWEEN '2025-06-01' AND '2025-06-02';
```text

B-Tree 在这个场景下有两个问题：

1. **建索引代价**：B-Tree 需要读全表、排序、写 WAL，300GB 表上可能需要数小时。索引本身大约 50-80GB。
2. **索引维护代价**：每次 INSERT 都要更新 B-Tree，可能触发页面分裂和 WAL 写入。每天 1000 万行的写入速度下，索引维护可能成为瓶颈。

BRIN 的观察很简单：如果 `ts` 值与物理存储位置高度相关（新数据自然追加到表的后面），那么每个 page range（比如 128 个连续页面 = 1MB）只需要存两条信息——这个 range 内 `ts` 的最小值和最大值。

查询 `WHERE ts BETWEEN '2025-06-01' AND '2025-06-02'` 时，BRIN 扫描所有 range summary：如果 range 的 `[min_ts, max_ts]` 与查询区间 `[2025-06-01, 2025-06-02]` 无交集，直接跳过整个 range 的所有页面。有交集的 range，才去读实际页面并逐行检查（因为 summary 只是范围，不能精确过滤每一行）。

### 代价对比

| 维度 | B-Tree（300GB 表） | BRIN（pages_per_range=128） |
|------|-------------------|----------------------------|
| 索引大小 | ~50-80GB | ~50MB |
| 创建时间 | 数小时 | 数分钟 |
| 每次 INSERT 的索引维护 | 遍历 B-Tree + 可能分裂 | 更新当前 range 的 min/max |
| 查询精度 | 精确，回表读目标行 | 粗过滤，回表读整个 range 的所有行 |
| 适用条件 | 任何数据分布 | 数据物理有序（或近似有序） |

---

## 二、BRIN 的内部结构：revmap + summary tuples

### revmap：range 到 index page 的映射

BRIN 索引本身也使用页面存储，但它的"行"是 summary tuples。对于 heap 表中连续的 `pages_per_range` 个页面，BRIN 在索引中存一行 summary。

revmap（reverse map）是一个数组，存储"每个 heap page range 对应哪个 BRIN index page"。当 heap 页面被更新时，PG 需要找到对应的 BRIN summary tuple 并更新它。revmap 提供 $O(1)$ 的查找：

```c
// src/include/access/brin_revmap.h
typedef struct BrinRevmap {
    Relation    rm_irel;            // BRIN index relation
    BlockNumber rm_pagesPerRange;   // pages_per_range 参数
    BlockNumber rm_maxRevmapPages;  // revmap 占用的最大页数
    Buffer      rm_currBuf;         // 当前 revmap 页面的 buffer
} BrinRevmap;

revmap 存储为 BRIN 索引的 meta page 之后的一组连续页面。第 \(N\) 个 heap page range（从 heap block 0 开始计数）的 revmap entry 存储在 revmap_page = N / entries_per_page 页面的偏移位置。每个 revmap entry 是目标 BRIN index page 的 block number，或特殊值 BRIN_EMPTY（表示该 range 尚未有 summary）。

// src/backend/access/brin/brin_revmap.c
// revmap 查询
BlockNumber
brinRevmapGetBlockNumber(BrinRevmap *revmap, BlockNumber heapBlk)
{
    // 计算此 heap block 所属的 range number
    BlockNumber rangeNo = heapBlk / revmap->rm_pagesPerRange;
    // 从 revmap 中找到此 range 对应的 BRIN index page
    // ...
}
```bash

### Summary Tuple：range 内所有行的统计摘要

每个 BRIN summary tuple 存储一个 page range 内所有行的统计摘要。对于 `ts` 列（`TIMESTAMPTZ` 类型），summary 就是 range 内的最小值和最大值。

PG 为每种支持 BRIN 的数据类型定义了 summary 的格式和操作。核心接口是一个操作符族（opclass），定义在 `pg_amproc` 中：

- **`BRIN_PROCNUM_SUMMARIZE`**（过程 1）：对给定的 tuple 更新统计信息（向 summary 中"加入"一个新值）。
- **`BRIN_PROCNUM_CONSISTENT`**（过程 3）：判断查询条件与 summary 是否一致（即有交集）。
- **`BRIN_PROCNUM_UNION`**（过程 4）：合并两个 summary（页面合并时使用）。

```c
// src/include/access/brin_internal.h
typedef struct BrinOpcInfo {
    uint16      oi_nstored;         // 此 opclass 存储的 summary 列数
    uint16      oi_regular_nulls;   // 是否允许常规 NULL
    Oid         oi_opaque;          // opaque data type
    // ...
} BrinOpcInfo;

typedef struct BrinValues {
    bool        bv_allnulls;    // 此列所有值都是 NULL？
    bool        bv_hasnulls;    // 此列有 NULL？
    bool        bv_attributes;  // 是否有 attribute（TOAST 外存）
    Datum       bv_values[];    // 实际 summary 值
} BrinValues;

typedef struct BrinTuple {
    uint32      bt_placeholder; // 占位符标志（待删除）
    BlockNumber bt_blkno;       // heap block 范围起始
    uint16      bt_info;        // 标志位：是否有 null、占位符等
    char        bt_columns[FLEXIBLE_ARRAY_MEMBER]; // 各列的 BrinValues
} BrinTuple;

以 timestamp_minmax_ops 为例，summary 的物理布局为 [min_ts, max_ts] 两个 8-byte 值，共 16 bytes。128 个页面（1MB）的数据，被压缩成 16 bytes 的摘要。

BRIN 插入与维护

当向 heap 表插入一行时，PG 检查此行所在的 page range 是否已有 BRIN summary：

// src/backend/access/brin/brin.c, brininsert()
bool
brininsert(Relation idxRel, Datum *values, bool *nulls,
           ItemPointer heaptid, Relation heapRel, ...)
{
    BrinDesc   *bdesc;
    BrinRevmap *revmap;

    bdesc = BrinDescInit(idxRel);
    revmap = brinRevmapInitialize(idxRel, pagesPerRange);

    // 从 revmap 中找到此 heap page range 对应的 summary tuple
    // 如果已有 summary，更新 min/max
    // 如果还没有，创建新的 summary tuple
    brinaddtuple(idxRel, bdesc, heapRel, values, nulls, heaptid);
    ...
}
```text

关键行为：如果 INSERT 的新值在已有 summary 的范围之内（例如已有 `[2025-06-01, 2025-06-30]`，新插入 `2025-06-15`），summary 不需要变化——不需要写 BRIN 索引。只有当新值超出 summary 范围时，才需要更新 BRIN index page。这意味着 BRIN 索引的写入开销极低。

### 查询：CONSISTENT 过程

查询时，BRIN 扫描所有 summary tuples，对每个 summary 调用 `CONSISTENT` 过程：

```c
// src/backend/access/brin/brin.c, bringetbitmap()
// 简化伪代码
for (each BRIN index page) {
    for (each summary tuple in page) {
        // 调用 opclass 的 CONSISTENT 函数
        consistent = DatumGetBool(
            FunctionCall3Coll(consistFn, collation,
                PointerGetDatum(summary),
                PointerGetDatum(scanKey),       // WHERE 条件
                PointerGetDatum(nullFlags))
        );
        if (consistent) {
            // 将此 range 的所有 heap 页面标记到 bitmap 中
            for (blk = start_blk; blk <= end_blk; blk++)
                tbm_add_page(tbm, blk);
        }
    }
}

CONSISTENT 返回 true 表示”这个 range 可能包含符合条件的行”——它是粗粒度的，可能有假阳性（false positive），但不会有假阴性。然后 executor 会用这个 bitmap 去扫描 heap 页面，并在回表后做精确的 WHERE 条件过滤。这是 BRIN 和 B-Tree 的核心区别：B-Tree 精确定位到每一行，BRIN 把一个 range 的所有页面都交给 executor 做二次过滤。

三、运维场景：BRIN 的坑与排查

坑 1：数据物理无序时 BRIN 退化为全表扫描

BRIN 依赖数据物理有序。如果你在一个随机的列（例如 UUID 主键）上建 BRIN 索引，每个 page range 内的 min 和 max 覆盖了几乎整个值域——每个 range 的 summary 与任何查询条件都有交集。BRIN 索引不提供任何过滤，每次查询扫描全表。

-- 错误用法：随机 UUID 主键
CREATE INDEX idx_uuid_brin ON user_table USING brin (uuid_col);

-- 此索引毫无作用——每个 range 的 [min_uuid, max_uuid]
-- 几乎总是覆盖整个 UUID 空间
-- 正确用法：B-Tree on UUID
CREATE INDEX idx_uuid_btree ON user_table USING btree (uuid_col);
```text

排查方法：

```sql
-- 用 pageinspect 观察 BRIN summary 的内容
CREATE EXTENSION pageinspect;

-- 查看 BRIN 索引的汇总统计
SELECT * FROM brin_page_items(
    get_raw_page('idx_brin_test', 0), 'idx_brin_test'::regclass
);

-- 如果每个 range 的 min/max 几乎覆盖整个值域，说明 BRIN 无效

坑 2：pages_per_range 选太大

pages_per_range 决定每个 summary 覆盖多少个 heap 页面。默认值 128（1MB）。如果设太大（例如 1024 = 8MB），每个 query 匹配到的 range 会回表扫描 8MB 的数据，即使实际只有几行符合条件的。

调优规则：pages_per_range 应使得每个查询的目标数据均匀落在少量 range 内。如果查询通常跨越 1 小时（~400MB 数据），pages_per_range = 32（256KB/range）会比默认值 128（1MB/range）更有效——更精细的 summary 减少回表扫描的浪费。

-- 调整 pages_per_range
CREATE INDEX idx_brin_fine ON sensor_data
USING brin (ts) WITH (pages_per_range = 32);
```bash

### 坑 3：BRIN 索引不适用于 UPDATE-heavy 场景

BRIN summary 是"累积"的——一旦 `max_ts` 更新到 `2025-06-30`，即使 `2025-06-01` 到 `2025-06-29` 的所有行都被 DELETE 了，`max_ts` 仍然是 `2025-06-30`。summary 不会收窄。这导致旧 range 的 summary 仍然与大量查询条件匹配，造成不必要的回表扫描。

修复方式：周期性运行 `brin_summarize_new_values()`（更新已有 range 的 summary）或 `VACUUM`（但 VACUUM 不会收窄 summary）。严重的 summary 膨胀需要通过 `REINDEX` 重建。

```sql
-- 重新汇总某个 range
SELECT brin_summarize_new_values('idx_brin_test'::regclass);

-- 如果 summary 严重膨胀，重建索引
REINDEX INDEX idx_brin_test;

坑 4：BRIN 扫描的 IO 模式

BRIN 扫描产生的 bitmap 是连续的 page range——这对 seqscan 友好的磁盘是高效的（大块连续读），但会绕过 shared_buffers 的随机缓存策略。在 EXPLAIN 中看到 Bitmap Heap Scan on ... (BRIN) 时，注意 Buffers: shared read=... 的数量——如果每个 range 都从磁盘读而非缓存命中，IO 可能成为瓶颈。

四、Hash 索引：WAL 安全边界与适用场景

历史包袱：PG 9.x 的 Hash 索引不支持 WAL

PG 的 Hash 索引有一个历史包袱：在 PG 9.x 及之前，Hash 索引不写 WAL。这意味着如果数据库 crash，Hash 索引的内容无法通过 WAL 恢复——必须用 REINDEX 重建。PG 10 之后，Hash 索引写了完整的 WAL 支持，但”Hash 索引不可靠”的印象留存至今。

在 PG 10+ 中，Hash 索引的 WAL 日志由 src/backend/access/hash/hash.c 和 hash_xlog.c 实现：

// src/backend/access/hash/hash.c
// Hash 索引插入入口
bool
hashinsert(Relation rel, Datum *values, bool *nulls,
           ItemPointer ht_ctid, Relation heapRel, ...)
{
    // 查找目标 bucket
    // 如果目标页面没有空间，触发 bucket split
    // 写 WAL record（PG 10+ 起支持）
    _hash_doinsert(rel, buf, ...);
}
```text

PG 10 的 Hash 索引 WAL 支持覆盖了以下操作：insert、split page、squeeze page（bucket 清理）、meta page 更新。PG 11 增加了对 `CREATE INDEX CONCURRENTLY` 的 WAL 支持。

### 什么时候用 Hash 索引

Hash 索引的物理结构是基于线性哈希的 bucket 数组，每个 bucket 包含一个 overflow 链（类似 B-Tree 的页面链）。查找流程为：`hash(key) → bucket number → 扫描该 bucket 的 overflow 链`。

Hash 索引的优势场景是**纯等值查询（=），且键值分布均匀**：

```sql
-- 适合 Hash 索引
SELECT * FROM sessions WHERE session_id = 'abc123';

-- 不适合 Hash 索引
SELECT * FROM sessions WHERE session_id BETWEEN 'abc' AND 'def';  -- 不支持范围
SELECT * FROM sessions ORDER BY session_id;                        -- 不支持排序

Hash 索引的物理大小通常比 B-Tree 小 20-40%（因为不需要 high key 和 rightlink），插入性能在键值均匀分布时略优于 B-Tree（不需要复杂的页面分裂点选择逻辑）。但在以下场景下 Hash 索引的性能不如 B-Tree：

1. 键值分布不均匀：某些 bucket 显著比其他的大，形成长 overflow 链。
2. 有范围查询：Hash 索引不能支持范围扫描——= 以外的操作需要全索引扫描。
3. 需要排序：Hash 索引不保证任何顺序。

当前底线：Hash 索引在 PG 10+ 中已经 WAL-safe，对于纯等值查询且键值均匀的场景，与 B-Tree 的差距主要在功能性（无 range scan、无排序）而非可靠性。但 B-Tree 仍然是默认选择——除非键值很宽（如长 UUID 字符串）且表很大，Hash 索引的空间优势才可能明显。

五、Bloom 索引：多列任意组合过滤

问题场景

CREATE TABLE users (
    id       INTEGER PRIMARY KEY,
    email    TEXT,
    phone    TEXT,
    nickname TEXT
);

-- 查询模式：任意字段的等值过滤，组合任意
SELECT * FROM users WHERE email = 'a@b.com';
SELECT * FROM users WHERE phone = '123456';
SELECT * FROM users WHERE email = 'a@b.com' AND phone = '123456';
```text

B-Tree 对于这个模式的解决方案是建三个单列索引，或一个复合索引。但复合索引有前缀匹配限制：`(email, phone)` 上的索引不能只用于 `WHERE phone = '123456'`（除非使用 Bitmap Index Scan 合并多个单列索引的 bitmap）。建三个单列索引意味着：每次 INSERT 要更新三个 B-Tree、总共 3 倍索引空间。

Bloom 索引（`bloom` 扩展）用布隆过滤器来处理这个问题：对每一行，将**所有被索引的列**的值一起哈希到一个布隆过滤器中。查询时，Bloom 索引对每个过滤条件做布隆过滤器检查——如果有任意条件不通过（即布隆过滤器说"不存在"），则排除此页面。

```sql
CREATE EXTENSION bloom;

CREATE INDEX idx_users_bloom ON users
USING bloom (email, phone, nickname)
WITH (length = 80, col1 = 2, col2 = 2, col3 = 2);

每个签名（signature）是一个 length × 16 bits 的位图（上例为 80 × 16 = 1280 bits = 160 bytes），每个列用 colN 个 bits 标记（上例每列 2 bits）。

Bloom 索引的代价与收益

Bloom 索引的关键价值：当查询模式是”多列的任意子集做等值过滤”时，一个 Bloom 索引替代多个单列 B-Tree，节省索引空间和写入开销。代价是存在假阳性——布隆过滤器说”这个页面可能有这行”但实际上没有。所以执行器仍然需要回表做精确的 WHERE 过滤。

Bloom 索引的参数选择

• length：signature 长度（× 16 bits）。越大假阳性越低，但索引越大。
• colN：第 N 列用多少 bits。越多假阳性越低，但 signature 空间更快被占满。

参数选择依赖于列数和预期的查询组合数。总签名空间（bits）= length × 16。如果所有列的总 bit 数（\(\sum col_i\)）为 \(K\)，每行有 \(M\) 个被索引列，则每个页面可以容纳约 \(S / K\) 个签名（\(S\) 为 signature 总 bits）。当页面填满后，假阳性率由布隆过滤器的位密度决定。

一般情况下，两列或三列组合的 Bloom 索引使用默认参数（length = 80, col1 = 2, col2 = 2）即可。如果列数较多（5+ 列），需要增大 length 或减少每列的 bits 来控制假阳性率。

Bloom 索引的限制

1. 不支持范围查询：布隆过滤器只能回答”可能存在”或”一定不存在”，不能判断范围。
2. 不支持 UNIQUE 约束：布隆过滤器的假阳性语义与唯一性检查不兼容。
3. 不支持排序：Bloom 索引没有值内容，无法按索引顺序返回结果。
4. 不能用于 JOIN：除非是等值 JOIN 且所有列都在 Bloom 索引中被覆盖。

六、索引选择决策树

查询模式是什么？
├─ 等值查询（=, IN）
│  ├─ 单列 → B-Tree（默认）、Hash（仅 PG 10+、纯等值、均匀分布）
│  └─ 多列、任意组合 → Bloom（空间和写入开销优势）、多个单列 B-Tree（精确但维护开销大）
│
├─ 范围查询（>, <, BETWEEN）
│  ├─ 数据物理有序 → BRIN（大表、低存储开销）
│  └─ 数据物理无序 → B-Tree
│
├─ 排序（ORDER BY, DISTINCT, GROUP BY）→ B-Tree
│
├─ 全文搜索 → GIN（读多写少）、GiST（读写平衡）— 见第 15、16 章
│
├─ 几何/空间/相似度 → GiST — 见第 15 章
│  └─ 或 SP-GiST（支持空间分区的特殊类型）
│
└─ UNIQUE 约束 → B-Tree（唯一）

代价速查表

七、实验：BRIN vs B-Tree 在时序数据上的对比

环境与数据

测试环境：PG 17，4C/8G，NVMe SSD，shared_buffers = 2GB，work_mem = 64MB。

-- 创建测试表（模拟传感器数据）
CREATE TABLE sensor_test (
    ts      TIMESTAMPTZ NOT NULL,
    dev_id  INTEGER,
    val     DOUBLE PRECISION
);

-- 生成模拟数据：时间有序的 5000 万行
INSERT INTO sensor_test
SELECT
    '2025-01-01'::timestamptz
        + interval '1 second' * generate_series,
    (random() * 1000)::int,
    random() * 100
FROM generate_series(1, 50000000);

-- 表大小
SELECT pg_size_pretty(pg_relation_size('sensor_test'));
-- 约 3.5GB
```bash

### 建索引对比

```sql
\timing on

-- B-Tree：耗时和索引大小
CREATE INDEX idx_sensor_btree ON sensor_test USING btree (ts);
-- Time: ~180000 ms（3 分钟）
SELECT pg_size_pretty(pg_relation_size('idx_sensor_btree'));
-- 约 1.1GB

-- 先删除 B-Tree
DROP INDEX idx_sensor_btree;

-- BRIN：耗时和索引大小
CREATE INDEX idx_sensor_brin ON sensor_test USING brin (ts)
WITH (pages_per_range = 128);
-- Time: ~8000 ms（8 秒）
SELECT pg_size_pretty(pg_relation_size('idx_sensor_brin'));
-- 约 200KB

查询性能对比

```sql SET enable_seqscan = off;

– 查询 1 小时数据（~3600 行） EXPLAIN (ANALYZE, BUFFERS) SELECT count(*) FROM sensor_test WHERE ts BETWEEN ‘2025-06-01 12:00:00’ AND ‘2025-06-01 13:00:00’;

– B-Tree： – Index Only Scan using idx_sensor_btree (actual time=0.050..2.123) – Heap Fetches: 0 – Buffers: shared hit=14

– BRIN： – Bitmap Heap Scan on sensor_test (actual time=0.300..4.567) – Bitmap Index Scan on idx_sensor_brin (actual time=0.200..0.200) – Buffers: shared hit=300 – BRIN 扫描了更多页面（整个 range 的所有页面），但仍远小于全表扫描 ```text

关键观察：BRIN 查询比 B-Tree 慢一些（回表了几百个页面而不是精确 14 个页面），但这是用8 秒 vs 3 分钟的建索引时间和200KB vs 1.1GB 的索引空间换来的。对于时序数据的日常查询，这个权衡通常是值得的。

八、关键要点

1. BRIN 用 page range summary 替代逐行索引——每个 range 只存 min/max 等统计值，索引大小仅为 B-Tree 的 1/100 到 1/1000。代价是查询精度依赖数据物理有序性。
2. BRIN 查询有假阳性，没有假阴性——consist 过程返回 true 的 range 可能不包含目标行，但返回 false 的 range 一定不包含。executor 需要回表做精确过滤。
3. BRIN 不适合数据随机分布的列或 UPDATE-heavy 的表——summary 不会收窄，旧 range 会保持宽泛的 min/max 导致不必要的回表扫描。
4. Hash 索引在 PG 10+ 中已 WAL-safe——对于纯等值查询且键值均匀的场景，Hash 索引能节省 20-40% 的空间。但不支持范围查询和排序。
5. Bloom 索引的价值在于多列任意组合的等值过滤——一个 Bloom 索引替代多个单列 B-Tree，但存在假阳性，且不支持范围查询、UNIQUE 约束、排序。
6. B-Tree 仍然是默认选择——除非空间和写入开销成为瓶颈，且 BRIN/Hash/Bloom 的前提条件（数据有序、纯等值、多列组合过滤）明确成立。

上一章：GIN 索引 下一章：流复制

参考资料

源码（PG 17）

• src/backend/access/brin/brin.c：brininsert(), bringetbitmap() — BRIN 插入与查询主函数
• src/backend/access/brin/brin_revmap.c：brinRevmapInitialize(), brinRevmapGetBlockNumber() — revmap 操作
• src/backend/access/brin/brin_tuple.c：BRIN summary tuple 的创建、修改、序列化
• src/backend/access/brin/brin_minmax.c：timestamptz_minmax_ops 等 opclass 的 summary 函数
• src/backend/access/brin/brin_inclusion.c：range 类型的 BRIN inclusion opclass
• src/include/access/brin.h：BRIN 相关结构体声明
• src/include/access/brin_internal.h：BrinOpcInfo, BrinValues, BrinTuple 定义
• src/include/access/brin_revmap.h：BrinRevmap 结构体
• src/backend/access/hash/hash.c：hashinsert(), hashgettuple() — Hash 索引实现
• src/backend/access/hash/hashpage.c：Hash 页面管理（bucket split, overflow）
• src/backend/access/hash/hash_xlog.c：Hash 索引的 WAL 重放（PG 10+）
• contrib/bloom/bloom.c：Bloom 索引的插入和查询实现
• contrib/bloom/blutils.c：Bloom 索引的 signature 管理

官方文档

• PostgreSQL Documentation, Chapter 67: BRIN Indexes（BRIN 原理和 opclass 接口）
• PostgreSQL Documentation, Chapter 64: Hash Indexes（Hash 索引内部结构）
• PostgreSQL Documentation, Section 11.2: Index Types（各类索引的概览与使用建议）
• PostgreSQL Documentation, Appendix F: Additional Supplied Modules — bloom（Bloom 索引扩展文档）
• PostgreSQL Documentation, Section 9.26: pageinspect — brin_page_items() 函数