土法炼钢兴趣小组的算法知识备份

【PG 内核】GiST 索引：一套接口搞定几何、全文、数组——通用搜索树怎么把"像什么"变成索引查找

2026-06-16 · database · kernel · #postgresql #pg-kernel #gist #index #consistent #penalty #picksplit #point-ops #tsvector-ops #full-text-search #geometric-index #generalized-search-tree

文章导航

分类入口
databasekernel
标签入口
#postgresql#pg-kernel#gist#index#consistent#penalty#picksplit#point-ops#tsvector-ops#full-text-search#geometric-index#generalized-search-tree

目录

GiST 索引：一套接口搞定几何、全文、数组——通用搜索树怎么把”像什么”变成索引查找

假设你要在一个包含 100 万个地理坐标的表中查找距离 (116.38, 39.90) 最近的 10 个点。B-Tree 帮不了你——它只能做一维排序，没法回答”二维空间中谁离我最近”。全文搜索也类似——找包含 “database” AND “index” 的文档，不是找某个确切值，而是找满足布尔谓词的集合。

PG 的答案是 GiST（Generalized Search Tree，通用搜索树）。它不定义具体的索引逻辑，而是定义一组抽象算子接口——Consistent、Union、Penalty、PickSplit——你只需按你的数据类型实现这几个函数，就能得到一个完整的平衡搜索树索引。point_ops 用这套接口做空间索引（R-Tree 风格），tsvector_ops 用同一套接口做全文搜索（签名树风格）。本文从这组接口出发，拆解搜索、插入、分裂的完整流程。

一、GiST 的设计动机与核心抽象

B-Tree 的核心能力是一维全序比较：给定任意两个键，总能判定它们之间的大小关系。这个前提很多数据类型不满足：

GiST 把这些类型统一为一种抽象：每个 key 是一种 predicate（谓词），页面中存储 key 的 bounding predicate（边界谓词），搜索时用 Consistent 判定查询谓词是否可能与页面内某个 key 的谓词成立。

flowchart LR
  A["B-Tree<br/>一维全序<br/>a &lt; b → 左分支<br/>a &ge; b → 右分支"] --> C["索引基础设施<br/>页面管理 / 并发控制 / WAL"]
  B["GiST<br/>N 维谓词<br/>Consistent(q, p) → true/false<br/>决定是否深入搜索"] --> C
```text

这意味着 GiST 不需要知道你的 key 长什么样——你实现了 Consistent、Union，以及 Penalty 或 PickSplit 之一，GiST 就能帮你构建和维护一棵平衡搜索树。

PG 内置的 GiST opclass 覆盖了多种类型：

| opclass | 数据类型 | 主要查询操作 |
|---------|---------|------------|
| `point_ops` | `point` | `<->`（距离 KNN）、`<@`（包含）、`&&`（重叠） |
| `tsvector_ops` | `tsvector` | `@@`（全文匹配） |
| `range_ops` | `anyrange` | `&&`（重叠）、`@>`（包含）、`<<`（严格左） |
| `inet_ops` | `inet` | `<<`（子网）、`>>`（超网）、`&&`（重叠） |
| `box_ops` | `box` | `&&`（重叠）、`@>`（包含） |
| `circle_ops` | `circle` | `&&`（重叠）、`<->`（距离） |
| `poly_ops` | `polygon` | `&&`（重叠）、`@>`（包含） |
| `array_ops` | `_int4` | `&&`（重叠）、`@>`（包含） |

---

## 二、GiST 的六个抽象算子接口

这六个接口定义在 `src/include/access/gist.h` 的 `GISTSTATE` 结构体中，每个 opclass 注册时提供函数指针。

```c
// src/include/access/gist_private.h
typedef struct GISTSTATE {
    FmgrInfo consistentFn[INDEX_MAX_KEYS];  // Consistent 回调
    FmgrInfo unionFn[INDEX_MAX_KEYS];       // Union 回调
    FmgrInfo compressFn[INDEX_MAX_KEYS];    // Compress 回调
    FmgrInfo decompressFn[INDEX_MAX_KEYS];  // Decompress 回调
    FmgrInfo penaltyFn[INDEX_MAX_KEYS];     // Penalty 回调
    FmgrInfo picksplitFn[INDEX_MAX_KEYS];   // PickSplit 回调
    FmgrInfo equalFn[INDEX_MAX_KEYS];       // Same 回调
} GISTSTATE;

Consistent(giststate, entry, query, strategy, recheck)

作用：判断页面/索引项的谓词 entry->key 是否”一致于”查询谓词 query。

关键：recheck 是出参。如果 Consistent 不能精确判定，可以返回 true 但设 *recheck = true，告诉执行器”这只是候选，需要回表再检查”。这是 GiST 实现有损索引的基础——索引层做粗筛选，heap 层做精筛。全文搜索严重依赖这个机制。

契约：Consistent 可以有假阳性（false positive），但绝不能有假阴性（false negative）。“宁滥勿缺”让签名树等概率性索引得以工作——加载一个可能匹配但实际不匹配的页面检查，比漏掉真正的匹配更安全。

Union(giststate, entryvec, attrsz)

作用：把多个 key 合并成一个”超级 key”（bounding predicate）。这是 GiST 的向上归纳能力——叶节点的 key 是原始数据，内部节点的 key 是子节点 key 的 Union。

point_ops 的例子：Union([(1,2), (5,8), (3,4)]) → 一个包围所有三维点的最小矩形 BOX(1,2),(5,8)。

tsvector_ops 的例子：Union([{'a','b'}, {'b','c'}, {'d'}]) → {'a','b','c','d'}，所有词元的并集。

契约：Union 的结果必须覆盖所有输入 key——不能比输入 key 的集合更窄。

Penalty(giststate, origentry, newentry)

作用：把 newentry 插入到 origentry 所在的子树，会导致 origentry 的 bounding predicate 膨胀多少？

penalty 越小，说明 newentry 和该子树越”亲近”。Penalty 是 GiST 插入路径选择的核心——新 key 走下哪个子树能最小化 bounding predicate 的膨胀。

point_ops 的例子：Penalty = 加入新点后 MBR 的面积增量。新点在 MBR 内部 → penalty = 0；新点在 MBR 外面很远 → penalty 很大。

PickSplit(giststate, entryvec, left, right, delta)

作用：页面满了，把 entryvec 中约 \(2n+1\) 个条目分成左右两组。目标：让左右两组的 bounding predicate 尽量紧凑且重叠小。

B-Tree 的分裂原则是”左右尽量平衡”（_bt_findsplitloc() 找两边大小最接近的分裂点），GiST 的 PickSplit 不以大小为平衡目标——它以查询效率为目标。分裂质量直接影响后续查询性能：bounding predicate 太大 → Consistent 过滤效果差 → 扫描更多页面。

point_ops 的例子：空间聚类——把点分成两个组，使组内聚拢、组间远离。point_ops 用基于 MBR 面积最小的贪心算法。

tsvector_ops 的例子：基于签名位差异的分裂——让左右分区的签名尽量不重叠，减少后续搜索时的假阳性。

Compress(giststate, entry) / Decompress(giststate, entry)

作用：Compress 把原始类型值转为 GiST 内部存储形式，Decompress 是其逆操作。只在存储格式不同于原始类型时需要。

point_ops：Compress 把 point(1,2) 压缩为 BOX(1,2),(1,2)（退化为点的矩形），因为内部页面统一用 BOX 做 Union。

tsvector_ops：Compress 把 tsvector 转为 SignTSVector（定长 bitmap 签名），减少存储开销和 Union 计算量。

这六个接口中，Consistent 和 Union 是必须实现的，Penalty 和 PickSplit 至少实现一个（否则无法维护平衡树），Compress/Decompress 可选。

GiST 页面布局

GiST 页面与 B-Tree 共享 PageHeaderData 和 ItemIdData 数组，但页面尾部用 GISTPageOpaqueData 替代 BTPageOpaque：

// src/include/access/gist.h
typedef struct GISTPageOpaqueData {
    PageGistNSN    nsn;              // GiST NSN（并发搜索用）
    BlockNumber    rightlink;        // 右兄弟指针
    uint16         flags;            // F_LEAF / F_DELETED / F_FOLLOW_RIGHT / F_TUPLES_DELETED
    uint16         gist_page_id;     // 魔数 0xFF81
} GISTPageOpaqueData;
```text

`rightlink` 是关键并发控制机制：当一个页面分裂时，原页面的 `rightlink` 指向新页面，并发搜索可以顺着 `rightlink` 找到被迁移的元组，不需要持锁等待分裂完成。

---

## 三、搜索：深度优先 + Consistent 过滤

### 入口：gistgettuple()

搜索入口是 `src/backend/access/gist/gistget.c` 中的 `gistgettuple()`。它为每次扫描（返回一条结果）调用 `gistnext()`，后者通过栈驱动深度优先遍历。

```c
// src/backend/access/gist/gistget.c
// gistgettuple() → gistnext() → gistScanPage() 核心路径
gistgettuple(scan, dir)
  → gistnext(scan)
    → gistScanPage(scan, ...)          // 扫描当前页面
      → gistindex_keytest(pageitems, query, strategy, recheck)
        → for each item in page:
            FunctionCall2Coll(consistent, key, query, ...)
            if (consistent == true):
              if (leaf page): 返回 tuple 的 TID
              else:           把子页面的 block 压入搜索栈

搜索流程

flowchart TD
  A["从根页开始，压入搜索栈"] --> B{"搜索栈为空？"}
  B -->|是| G["返回 false（无更多匹配）"]
  B -->|否| C["弹出栈顶页面"]
  C --> D["对页面中每个 IndexTuple<br/>调用 Decompress → Consistent"]
  D --> E{是叶页面？}
  E -->|是| F1["Consistent=true → 返回 TID<br/>检查 heap 可见性后返回给上层"]
  E -->|否, 内部页面| F2["Consistent=true → 子页压栈<br/>Consistent=false → 跳过（剪枝）"]
  F1 --> B
  F2 --> B
```text

关键点：Consistent 在叶子层和内部层都会被调用。在内部层，它决定是否深入子树；在叶子层，它决定是否返回该 TID。如果 Consistent 过于"宽松"（假阳性太多），会把大量无用页面加载进内存。

### KNN 距离查询的优先队列

对于 `ORDER BY pos <-> point '(0,0)' LIMIT 5` 这样的 KNN 查询，GiST 不使用简单的 DFS 栈，而是使用**优先队列**：

```c
// src/backend/access/gist/gistget.c, gistnext() 中 KNN 分支
if (scan->numberOfOrderBys > 0) {
    // KNN 模式：对每个内部页面条目计算距离
    // 优先搜索距离查询点最近的页面
    // 使用 PairingHeap 作为优先队列，保证最早返回的结果就是最近的
}

这是增量式 KNN：不需要扫描全部数据再排序，而是一边搜索一边按距离产出结果。如果 LIMIT 5 的结果已经在优先探索的分支中找到了，GiST 可以直接返回，不需要访问远处的分支。

// gistScanPage() 中简化逻辑
// 读完当前页面后，检查是否需要跟随 rightlink
if (GistFollowRight(page)) {
    BlockNumber rightlink = GistPageGetOpaque(page)->rightlink;
    if (rightlink != InvalidBlockNumber) {
        // 页面被并发分裂了——把右兄弟也压栈继续搜索
        stack = gistPushItrRightLink(stack, rightlink, so);
    }
}
```text

---

## 四、插入与页面分裂：Penalty → PickSplit 二阶段

### 插入路径

GiST 的插入入口是 `src/backend/access/gist/gist.c` 中的 `gistdoinsert()`：
  1. 从根页面开始向下搜索
  2. 对内部页面的每个子页面、调用 Penalty(child_union_key, new_key)
  3. 选择 Penalty 最小的子页面继续向下
  4. 到达叶页面后尝试放入
  5. 如果叶页面满 → 触发 gistSplit()

Penalty 选择逻辑在 `gistchoose()`（`src/backend/access/gist/gistutil.c`）中：

```c
// gistchoose() 简化逻辑
OffsetNumber gistchoose(Relation r, Page p, IndexTuple it, ...) {
    best_penalty = INFINITY;
    for each item in page {
        penalty = FunctionCall2(penalty_fn, item_union_key, it);
        if (penalty < best_penalty) {
            best_penalty = penalty;
            best_item = current_item;
        }
    }
    return best_item;
}

如果有多个子页面的 penalty 相等（如 point_ops 中新点同时落在多个 MBR 内部，penalty 都是 0），则选择 Union(child_entries + new_entry) 后面积最小的那个。

sequenceDiagram
    participant HEAP as Heap Insert
    participant GIST as gistdoinsert()
    participant WALK as 树下降
    participant PAGE as gistplacetopage()
    participant SPLIT as gistSplit()

    HEAP->>GIST: 插入 IndexTuple
    GIST->>WALK: 从根页开始
    loop 下降
        WALK->>WALK: Penalty(new_entry, child.union)
        WALK->>WALK: 选 penalty 最小的 child
    end
    WALK->>PAGE: 尝试放入叶页
    alt 页面有空间
        PAGE-->>GIST: 放入，完成
    else 页面已满
        PAGE->>SPLIT: 调用 PickSplit
        SPLIT->>SPLIT: 种子选择 + 条目分配
        SPLIT->>SPLIT: 左右组分别计算 Union key
        SPLIT->>PAGE: 返回分裂结果
        PAGE->>PAGE: 更新父页，插入新 downlink
        alt 父页也满
            PAGE->>SPLIT: 递归向上分裂
        end
    end
```bash

### PickSplit 算法

通用 PickSplit 实现在 `src/backend/access/gist/gistsplit.c` 中：

```c
// genericPickSplit() 简化
void genericPickSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v, ...) {
    // 1. 种子选择：互相之间 penalty 最大的两个条目作为左右组种子
    find_seeds(entryvec, &seed_left, &seed_right, penalty_fn);

    // 2. 贪心分配：每个剩余条目分别计算加入左/右组后的 penalty
    for each remaining entry {
        penalty_left  = Penalty(Union(左组), entry);
        penalty_right = Penalty(Union(右组), entry);
        分配到 penalty 较小的一组;
        更新该组的 Union key;
    }

    // 3. 计算左右组的 Union key 写入父页面
    v->spl_ldatum = Union(左组所有条目);
    v->spl_rdatum = Union(右组所有条目);
}

不同 opclass 有不同的分裂策略：

分裂完成后，父页面插入两个新条目（分别指向左右新页面）。如果父页面也满了，分裂向上递归，直到根页面——如果根页面也需要分裂，GiST 会创建一个新的根页面。

五、point_ops：几何索引的 GiST 实现

point_ops（源码在 src/backend/access/gist/gistproc.c）是最直观的 GiST 实现，核心思想是用最小外包矩形（MBR）作为 bounding predicate。

Compress：point → BOX

// src/backend/access/gist/gistproc.c
// gbt_point_compress() 简化
Datum gbt_point_compress(PG_FUNCTION_ARGS) {
    GISTENTRY *entry = ...;
    if (entry->leafkey) {
        Point *p = DatumGetPointP(entry->key);
        BOX *box = palloc(sizeof(BOX));
        box->high = box->low = *p;   // 退化为点的矩形
        PG_RETURN_POINTER(box);
    }
    // 内部页面已经是 BOX，不需要转换
    PG_RETURN_POINTER(entry->key);
}
```bash

### Consistent：五类空间策略

| 策略号 | 操作符 | 含义 | Consistent 判定逻辑 |
|--------|--------|------|--------------------|
| 1 | `<<` | 严格在左 | entry 右边界 < query 左边界 |
| 3 | `&&` | 重叠 | entry MBR 和 query 有交集 |
| 17 | `<->` | KNN 距离 | 计算 MBR 到查询点的最小距离 |
| 24 | `<@` | 被包含 | query 包含 entry |
| --- | `@>` | 包含 | entry 包含 query |

```c
// gbt_point_consistent() 简化——策略 3（重叠 &&）
case RTOverlapStrategyNumber:
    result = overlap2d(entry_box, query_box);
    // 两个矩形有交集 → true
    break;

// 策略 17（KNN 距离 <->）
case RTDistanceStrategyNumber:
    // 查询点在 MBR 内部 → 距离 = 0
    // 否则 → 查询点到 MBR 最近边的距离
    distance = box_dist(query_point, entry_box);
    break;

Penalty：MBR 面积增量

// point_ops 的 Penalty：新点加入后 MBR 的面积膨胀
Datum gbt_point_penalty(PG_FUNCTION_ARGS) {
    BOX *origbox = DatumGetBoxP(origentry->key);
    BOX *newkey  = DatumGetBoxP(newentry->key);

    // 合并后的 MBR
    BOX unionbox;
    unionbox.high.x = Max(origbox->high.x, newkey->high.x);
    unionbox.low.x  = Min(origbox->low.x, newkey->low.x);
    // ... 同理处理 y 坐标

    penalty = size_box(&unionbox) - size_box(origbox);
    PG_RETURN_FLOAT4(penalty);
}
```text

新点落在 MBR 内部 → penalty = 0（不膨胀 bounding predicate）。这正是理想情况——新增数据不增加"松散度"。

### 搜索示例

```sql
-- 建 GiST 空间索引
CREATE INDEX idx_points_gist ON locations USING gist (pos);

-- 包围矩形搜索
SELECT * FROM locations
WHERE pos <@ box '((0,0),(100,100))';

-- KNN 搜索：离目标最近的 10 个点
SELECT * FROM locations
ORDER BY pos <-> point '(50, 50)'
LIMIT 10;

-- 方向搜索
SELECT * FROM locations
WHERE pos >> point '(10, 0)';

KNN 查询 ORDER BY pos <-> point LIMIT 10 的过程：

根页（内部节点）:
  ┌───────────────────────────────────────────────────┐
  │ Entry 1: MBR((-50,-50),(50,50))  │ 距 (0,0)=0    │ ← 优先搜索
  │ Entry 2: MBR((100,100),(200,200))│ 距 (0,0)=141  │ ← 后搜
  │ Entry 3: MBR((-200,-200),(-100,-100))│ 距=141    │
  └───────────────────────────────────────────────────┘

优先搜索 Entry1 → 叶页 → 找到实际点，LIMIT 10 满了就停止，无需访问 Entry2/3

六、tsvector_ops：全文搜索的 GiST 实现

tsvector_ops（源码在 src/backend/utils/adt/tsgistidx.c）展示了 GiST 如何处理有损索引和布尔查询。

签名树原理

签名（signature）是一个固定长度的 bit 串（默认 124 字节，即 992 位）。每个词通过哈希被映射到签名的某些位。一个页面的签名是其所有子页面签名的按位或。

tsvector: 'database:1 index:2 query:3'
  ↓ Compress
SignTSVector: bitmap[hash('database')]=1, bitmap[hash('index')]=1, bitmap[hash('query')]=1

核心运算：

Union:    parent_sig = child1_sig | child2_sig | ...
Consistent: query_sig & page_sig == query_sig ?

Compress / Decompress

// src/backend/utils/adt/tsgistidx.c
Datum gtsvector_compress(PG_FUNCTION_ARGS) {
    GISTENTRY *entry = ...;
    if (entry->leafkey) {
        TSVector val = DatumGetTSVector(entry->key);
        SignTSVector *sign = makeSignTSVector(val);  // 转签名
        PG_RETURN_SIGNTSVECTOR(sign);
    }
    // 内部页面已经是 SignTSVector
    PG_RETURN_POINTER(entry->key);
}
```bash

### Consistent：签名匹配 + recheck

```c
// gtsvector_consistent() 核心逻辑
Datum gtsvector_consistent(PG_FUNCTION_ARGS) {
    SignTSVector *entry_sign = ...;
    QUERYTYPE *query = ...;   // tsquery: 'database & index'

    // 签名匹配检查
    if (entry 签名包含 query 中所有必须词元的 bit) {
        *recheck = true;       // 签名匹配 ≠ 精确匹配！
        PG_RETURN_BOOL(true);
    } else {
        PG_RETURN_BOOL(false); // 签名不匹配 → 安全排除
    }
}

假阳性不可怕，假阴性才是问题。签名哈希冲突导致假阳性（不同词哈希到相同 bit）→ Consistent 返回 true 但实际不匹配 → recheck 在 heap 层纠正。假阴性不可能（bit 在这就说明有某个词被哈希到这位）→ Consistent 返回 false 一定是安全的。

sequenceDiagram
    participant Q as tsquery<br/>'database & index'
    participant G as GiST Index
    participant H as Heap

    Q->>G: 搜索
    G->>G: DFS 遍历内部页面
    loop 每个内部页面的 entry
        G->>G: Consistent(entry_sign, query)
        G->>G: signature AND 位运算
        alt 签名匹配
            G->>G: push 子页面（可能有假阳性）
        else 签名不匹配
            G->>G: skip（安全剪枝）
        end
    end
    G->>H: 叶页签名匹配 → 返回 TID (recheck=true)
    H->>H: 用真实 tsvector 重新检查
    H->>Q: 精确结果（假阳性已过滤）
```bash

### PickSplit：签名重叠最小化

```c
// tsvector_ops 的 PickSplit 启发式（简化）
// 1. 计算所有条目的 Union 签名
// 2. 尝试将条目分配到左右分区
// 3. 对候选方案计算左右签名位重叠度
// 4. 选重叠最小的方案
// 目标：让未来搜索时 Consistent 可以更早排除一个分支

七、运维：GiST vs GIN 的选择与常见坑

GiST vs GIN 对比

维度 GiST GIN
基本结构 平衡树（节点存储”区域”概括） 倒排索引（词 → 文档列表）
写性能 较高（树下降 + 签名更新，代价稳定） 较低（更新 posting tree/list，pending list 需要后台合并）
读性能 中等（签名匹配 + recheck 开销） 高（直接定位到含词的文档，无假阳性）
存储开销 较小（签名固定长度） 较大（posting list 随文档数增长）
KNN 支持 原生支持（距离排序） 不支持
数据分布敏感度 对分布敏感（分裂质量影响查询） 对键基数敏感（高基数列开销大）
更新友好性 好（索引内 update = delete + insert） 差（频繁更新导致 pending list 膨胀）

选择规则

选 GiST 的场景：

选 GIN 的场景：

索引膨胀与 VACUUM

GiST 索引也会膨胀——UPDATE 和 DELETE 产生的死 tuple 在页面中累积。但与 B-Tree 不同：

排查：

-- 查看 GiST 索引大小
SELECT pg_size_pretty(pg_relation_size('idx_gist_geom')) AS index_size;

-- 查看膨胀（需要 pgstattuple 扩展）
CREATE EXTENSION pgstattuple;
SELECT * FROM pgstatindex('idx_gist_geom');
-- 关注 dead_tuple_percent，>20% 值得关注

-- 检查 autovacuum 是否跟得上
SELECT relname, n_dead_tup, n_live_tup,
       last_autovacuum, last_autoanalyze
FROM pg_stat_user_tables WHERE relname = 'your_table';
```bash

### fillfactor

GiST 支持 `fillfactor`。降低 fillfactor 可以减少页面分裂的频率，但会增加索引初始大小：

```sql
CREATE INDEX idx_gist_points ON points USING gist (geom) WITH (fillfactor = 70);

KNN 查询的性能陷阱

GiST 的距离排序查询在以下情况可能很慢：

  1. Bounding predicate 过于松散：数据分布极度不均匀时，PickSplit 可能产生一个大的 MBR 覆盖大部分数据。结果：KNN 搜索需要扫描大量”看似很近”的页面。

  2. LIMIT 太小但数据量大：如果优先搜索的分支中没有足够的结果，需要回溯大量分支。

验证方法：

sql EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM points ORDER BY geom <-> '(0,0)'::point LIMIT 10; -- 如果 "Buffers: shared hit=..." 数字很大，说明扫描了大量页面text

八、关键要点

  1. GiST 是索引框架，不是一种索引用法——它将页面管理、并发控制、WAL 恢复与搜索/分裂的语义分离。Consistent、Union、Penalty、PickSplit 六个接口定义了 opclass 需要实现的所有行为。

  2. 搜索是深度优先 + Consistent 过滤——gistgettuple() 从根页出发，对每个内部条目的 bounding predicate 调 Consistent。命中 → 深入子树；未命中 → 剪枝跳过。KNN 用优先队列替代栈，保证最近的结果最先产出。

  3. 插入用 Penalty 选路径，分裂用 PickSplit 决定分区——Penalty 最小化 bounding predicate 膨胀，PickSplit 以查询效率为目标（不是平衡大小）。Point_ops 最小化 MBR 面积，tsvector_ops 最小化签名重叠。

  4. Consistent 的 recheck 是有损索引的基础——签名树等概率性索引通过 recheck 处理假阳性。契约：允许 false positive，禁止 false negative。

  5. point_ops：MBR 做 bounding predicate，Penalty 是面积增量，PickSplit 是贪心空间聚类。KNN 利用 MBR 距离做搜索优先级排序。

  6. tsvector_ops：签名（定长 bitmap）做有损压缩——Union 是位或，Consistent 是位与。假阳性通过 recheck 消除，假阴性不可能。

  7. GiST 偏写，GIN 偏读——GiST 的树结构使更新代价更稳定，GIN 的倒排索引读性能更高但写代价大。需要 KNN 距离排序时只能选 GiST。

上一章：B-Tree 索引 下一章：GIN 索引

参考资料

源码（PG 17）

官方文档

论文

实验工具

同主题继续阅读

把当前热点继续串成多页阅读，而不是停在单篇消费。

2026-06-16 · database / kernel

【PG 内核】B-Tree 索引：页面分裂、rightlink 与去重

拆解 PostgreSQL B-Tree 索引的内核实现：BTPageOpaque 页面布局（high key / rightlink 的工程意义）、_bt_doinsert() 插入路径与 _bt_split() 页面分裂的完整流程（分裂点选择不是简单的 50/50）、PG 12+ 去重（deduplicate_items）的触发条件与 posting list 压缩策略、B-Tree WAL 记录类型与恢复，以及用 bt_page_items() 和 bt_metap() 观察索引内部结构的实验方法。

2026-06-16 · database / kernel

【PG 内核】GIN 索引：倒排索引的内部机制与 Fast Update

拆解 PostgreSQL GIN 索引的内部结构：entry tree、posting list、posting tree 三者各在什么条件下使用；Fast Update 的 pending list 设计与 gin_clean_pending_list 合并时机；gingetbitmap() 的 bitmap AND/OR 多关键词搜索合并流程；全文搜索 tsvector 与数组 _int4 的 GIN 实现；以及 GIN 与 GiST 在写性能、读性能、存储开销上的三角权衡和具体场景下的选择建议。

2026-06-16 · database / kernel

【PG 内核】进程模型与共享内存：Postmaster 如何管理 100 个 Backend

拆解 PostgreSQL 多进程架构的核心：Postmaster 的启动与信号处理、Backend 进程的 fork()→InitPostgres→主循环生命周期、CreateSharedMemoryAndSemaphores() 的共享内存初始化流程、PGPROC/ProcArray/PGXACT 等关键共享内存结构的内存布局，以及 Background Worker 的注册与调度。理解了这个地基，才能理解 PG 为什么用进程而不是线程，以及 max_connections 为什么不能随便调大。

2026-06-16 · database / kernel

【PG 内核】页面布局与元组格式：PG 如何把一行数据塞进 8KB

拆解 PostgreSQL 的物理存储层：Page 的 8KB 布局（PageHeaderData、ItemId 数组、special space）、HeapTupleHeaderData 的字段语义（xmin/xmax/ctid/t_infomask/t_infomask2）、TOAST 外存机制的压缩阈值与四种策略（PLAIN/EXTENDED/EXTERNAL/MAIN），以及用 pageinspect 扩展直接观察页面字节。理解页面格式是理解 VACUUM、Index Scan、MVCC 可见性判断的共同前提。

By .