B-Tree 索引：页面分裂、rightlink 与去重

你在 PG 里跑了几个月的 orders 表，突然发现 INSERT 延迟跳了 5 倍。EXPLAIN ANALYZE 看不出问题——查询本身很快。pg_stat_user_tables 的 n_tup_ins 也没有异常。但 pg_stat_statements 抓到那条 INSERT 的 shared_blks_written 比平时翻了 3 倍。

问题在索引。B-Tree 页面分裂时，PG 要分配新页面、迁移元组、在父页面插入 downlink、写 WAL——这个操作持有页面的 LWLock，阻塞同一页面上的所有并发插入。分裂从叶子向上传播，最坏情况一直裂到根节点，树高加一。

本文从 PG 17 源码出发，拆解 B-Tree 的三个核心机制：页面布局（BTPageOpaque、high key、rightlink）、插入与分裂的完整源码路径、PG 12 引入的去重。读完你会理解为什么 fillfactor 和 deduplicate_items 不是可有可无的存储参数，以及什么时候该在 UUID 列上建 B-Tree、什么时候不该。

一、B-Tree 页面布局：BTPageOpaque、high key 与 rightlink

1.1 三层结构 + special space

B-Tree 页面复用了 PG 通用 Page 的 8KB 三层结构（PageHeaderData + ItemId 数组 + Tuple 区域），区别在 special space 里塞了 B-Tree 专用元数据：

┌─────────────────────────────────────────────┐
│              PageHeaderData (24B)            │ ← pd_lsn, pd_lower, pd_upper
├─────────────────────────────────────────────┤
│          ItemId 数组（每项 4B）               │ ← 指向每个 IndexTuple
├─────────────────────────────────────────────┤
│               空闲空间                        │
├─────────────────────────────────────────────┤
│  IndexTuple N │ ... │ IndexTuple 2 │ IndexTuple 1 │ ← 从底部向上增长
├─────────────────────────────────────────────┤
│            BTPageOpaqueData (16B)            │ ← special space
└─────────────────────────────────────────────┘

// src/include/access/nbtree.h
typedef struct BTPageOpaqueData {
    BlockNumber  btpo_prev;       // 左兄弟 block number（同层双向链表）
    BlockNumber  btpo_next;       // 右兄弟 block number
    uint32       btpo_level;      // 树中层级（0 = 叶子）
    uint16       btpo_flags;      // BTP_LEAF / BTP_ROOT / BTP_DELETED / BTP_META / BTP_HALF_DEAD
    BTCycleId    btpo_cycleid;    // 最近一次 VACUUM 的 cycle ID
} BTPageOpaqueData;
```text

`btpo_flags` 的标志位：

| 标志 | 含义 | 如何产生 |
|------|------|---------|
| `BTP_LEAF` | 叶子页面，btpo_level == 0 | 页面创建时，如果是叶子层 |
| `BTP_ROOT` | 根页面 | 根分裂时新分配的页面被设为此标志 |
| `BTP_DELETED` | 页面已标记删除，元组被迁移 | VACUUM 发现叶子页完全无活跃元组时标记 |
| `BTP_HALF_DEAD` | 页面半死——内部页面删除的中间状态 | 内部节点的 key 全被删空，但仍被父节点引用 |
| `BTP_META` | metapage——索引的第 0 号块 | 索引创建时 |

### 1.2 rightlink：同层页面的单链表

`btpo_prev` 和 `btpo_next` 构成双向链表，把所有同一层的页面串在一起。教科书 B-Tree 没有兄弟指针——跨节点遍历必须回到父节点重新向下。PG 的 rightlink 解决了两个工程问题：

**第一，并发扫描的窗口期安全。** 页面分裂是两阶段操作——先裂叶子页，再在父页插入 downlink。在父页更新之前，新产生的右页面对扫描器不可达。rightlink 让扫描器可以从旧页面"向右走"找到新页面，不会因为"父页还没更新 downlink"而丢数据。

分裂前: [Page A] → next → [Page B] 分裂: [Page A] → next → [NEW Page A’] → next → [Page B] 此时父页面还不知道 Page A’ 存在，但扫描器从 Page A 沿 rightlink 能找到它

**第二，范围扫描的 IO 模式。** 范围查询 `WHERE key BETWEEN 100 AND 200` 不再需要 $O(\log N)$ 次回父节点再向下——只需要两次二分查找（定位起始和终止位置），中间的页面全部沿 rightlink 顺序读取。在缓存预热的情况下，这是一个接近顺序 IO 的扫描。

### 1.3 high key：每个非最右页面的"上限"

每个非最右叶子页面的 offset 1 是 `P_HIKEY`，一个特殊的索引项，存储本页所有索引 key 的上界：

```c
// src/include/access/nbtree.h
#define P_HIKEY     ((OffsetNumber) 1)   // high key 总是在偏移位置 1
#define P_FIRSTKEY  ((OffsetNumber) 2)   // 第一个正常数据项在偏移位置 2

high key 的来源：页面分裂时，从右兄弟页面取最小的 key 拷贝到左页面的 offset 1。如果本页面就是最右页面（没有右兄弟），则没有 high key。

high key 参与两个决策：

1. 插入路由：_bt_doinsert() 判断新 key 插哪一页时，如果新 key \(\ge\) high key，沿 rightlink 向右移动，直到找到容纳它的页面。
2. 分裂点选择：_bt_findsplitloc() 用 high key 计算新的页面边界。

二、B-Tree 元页面：bt_metap()

每个 B-Tree 索引的 block 0 是 metapage，存储索引级别的元数据：

// src/include/access/nbtree.h
typedef struct BTMetaPageData {
    uint32       btm_magic;                 // BTREE_MAGIC (0x053162)
    uint32       btm_version;               // PG 17 为 4 (PG 12+ 支持去重后升版)
    BlockNumber  btm_root;                  // 根页面的 block number
    uint32       btm_level;                 // 根页面的 btpo_level
    BlockNumber  btm_fastroot;              // "快速根"——跳过顶部空页面
    uint32       btm_fastlevel;
    uint32       btm_last_cleanup_num_delpages;
    bool         btm_allequalimage;         // PG 17: 所有列支持等值比较优化
} BTMetaPageData;
```text

`fastroot` 是一个值得注意的设计：当根节点因为大量删除变空时，PG 不会立即释放它——它被标记为 `BTP_HALF_DEAD`，树的实际根下移一层。`fastroot` 指向这个"有效根"，避免每次扫描路过一个空页面。

---

## 三、插入路径：从 _bt_doinsert() 到页面分裂

### 3.1 入口调用链

B-Tree 插入的入口是 `btinsert()`（在 `nbtinsert.c` 中，由索引 AM 接口 `index_insert()` 调用）：

btinsert() // nbtinsert.c → _bt_doinsert() 1. _bt_search() // 从 root 找到目标叶子页 2. _bt_check_unique() // 唯一索引冲突检查 3. _bt_insertonpg() // 在页面上执行插入 → _bt_findinsertloc() // 二分查找插入位置 → 有空间：直接写入页面 → 空间不足：_bt_split() // 触发页面分裂

```c
// src/backend/access/nbtree/nbtinsert.c
bool _bt_doinsert(Relation rel, IndexTuple itup,
                  IndexUniqueCheck checkUnique, bool indexUnchanged,
                  Relation heapRel) {
    BTInsertStateData insertstate;
    Buffer buf;

    // 1. 从 root 下降到目标叶子页，pin 住
    _bt_search(rel, &insertstate, &buf);

    // 2. 唯一索引冲突检测
    if (checkUnique != UNIQUE_CHECK_NO)
        _bt_check_unique(rel, &insertstate, heapRel, checkUnique, ...);

    // 3. 在叶子页插入或分裂
    _bt_insertonpg(rel, itup, buf, InvalidBuffer, NULL, itup_key,
                   false, false, checkUnique != UNIQUE_CHECK_NO,
                   indexUnchanged, &insertstate);
}

3.2 _bt_search()：利用 rightlink 向下搜索

_bt_search() 从 root 页面开始，逐层下降直到叶子层。在每一层，二分查找第一个 key 大于等于目标 key 的项，获取该项指向的子页 block number，pin 住子页，释放当前页。

关键细节：在内部节点上二分查找时，P_HIKEY 位置被跳过——只有叶子节点才有 high key 在 offset 1。内部节点的第一个项不是 high key。

// src/backend/access/nbtree/nbtsearch.c, _bt_search() 核心（简化）
for (;;) {
    page = BufferGetPage(buf);
    opaque = BTPageGetOpaque(page);

    if (P_ISLEAF(opaque))
        break;   // 到达叶子层

    // 内部节点二分查找，跳过 offset 1
    offnum = _bt_binsrch(rel, insertstate, buf, ...);
    itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
    blkno = BTreeInnerTupleGetDownLink(itup);
    buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ);
}
```bash

### 3.3 _bt_insertonpg()：插入或分裂的决策点

```c
// src/backend/access/nbtree/nbtinsert.c, _bt_insertonpg() 简化
if (PageGetFreeSpace(page) >= itemsz) {
    // 空间足够，直接插入
    _bt_findinsertloc(rel, insertstate, ...);
    PageIndexTupleOverwrite(page, insertstate->offnum, (Item) itup, itemsz);
} else {
    // 空间不足，触发分裂
    _bt_split(rel, insertstate, buf, ...);
}

PG 的 B-Tree 不做”页面重整”（尽管碎片化后总空闲空间够但不连续）——遇到不连续空闲空间时，PG 也走分裂路径，不尝试在页面内重排 item 来腾出连续空间。这是 fillfactor 有意义的原因之一：为 UPDATE-heavy 的索引留足页面内空间，让 HOT update 的新索引 tuple 版本能放进同一页，避免频繁分裂。

四、页面分裂：_bt_split() 的完整流程

_bt_split() 定义在 src/backend/access/nbtree/nbtsplitloc.c 中，是 B-Tree 实现中最复杂的单个操作。它分五步：

sequenceDiagram
    participant Caller as 调用者
    participant Split as _bt_split()
    participant SplitLoc as _bt_findsplitloc()
    participant Parent as _bt_insert_parent()

    Caller->>Split: 页面已满，请求分裂
    Split->>SplitLoc: 1. 选择分裂点
    SplitLoc-->>Split: 返回最佳分裂位置
    Split->>Split: 2. _bt_split_alloc() 分配新页面
    Split->>Split: 3. 迁移元组到新页面
    Split->>Split: 更新双向链表 (btpo_next/prev)
    Split->>Parent: 4. 在父页面插入 downlink
    Note over Parent: 父页满时递归触发分裂
    Parent-->>Split: 完成
    Split->>Split: 5. WAL logging
    Split-->>Caller: 返回左页或右页的 buffer
```bash

### 4.1 第一步：选择分裂点（_bt_findsplitloc）

`_bt_findsplitloc()` 是 `nbtsplitloc.c` 约 800 行的核心——整个 C 文件只做"在哪里切这一刀"。它不是一个简单的"找中间位置"，而是对每个候选分裂点计算一个惩罚分，选惩罚最小的。

为什么不是 50/50？因为 PG B-Tree 页面中 item 大小差异巨大。如果一个 item 占了页面 70% 的空间，按 item 个数对半分会导致新页装不下这个大 item。分裂点选择必须满足：

1. **硬约束**：两个新页面都能装下各自的那一半元组。
2. **软优化**：左右填充量尽可能均衡。
3. **key 边界优化**：如果存在大量相同 key 的数据，把相同 key 的元组分到同一侧——有助于后缀截断。

```c
// src/backend/access/nbtree/nbtsplitloc.c, _bt_findsplitloc() 策略（简化）

// 策略一：默认单后缀策略
// 把每个 item 的 penalty 设为 1，找左右 penalty 总和最接近的位置
for (offnum = firstright; offnum <= lastleft; offnum++) {
    delta = Abs(leftfree - rightfree);
    if (delta < best_delta) {
        best_delta = delta;
        bestoff = offnum;
    }
}

// 策略二：多后缀策略（大量相同 key 时触发）
// 找到 newitemoff 附近第一个不同 key 的边界作为分裂点
if (_bt_afternewitemoff(rel, page, newitemoff, ...)) {
    // 在 key 边界处分裂——相同 key 留在一侧
    return _bt_bestsplitloc(rel, page, ...);
}

4.2 后缀截断（Suffix Truncation）

分裂后，插入父页面的 downlink key 不需要存完整的索引值——它可以被截断到”刚好能区分左右子树的最短前缀”。

举例：如果索引列是 text，左页面的最大值是 "PostgreSQL"，右页面的最小值是 "Postmaster"，父页面的 downlink key 只需要 "Postm"——这个前缀已经足够引导搜索到正确的子页面。截断在 _bt_truncate() 中实现：

// src/backend/access/nbtree/nbtsplitloc.c
IndexTuple _bt_truncate(Relation rel, IndexTuple lastleft,
                         IndexTuple firstright, BTScanInsert itup_key) {
    // 计算需要多少字节才能区分 lastleft 和 firstright
    int natts = _bt_keep_natts_fast(rel, lastleft, firstright);
    // 生成截断后的 index tuple，只保留前 natts 个属性列
}
```text

后缀截断的效果：**内部节点变窄，树高更矮**。对于 text 列，内部节点的 key 通常只需要几个字符，不需要完整字符串。

### 4.3 第二步：分配新页面

```c
// src/backend/access/nbtree/nbtinsert.c
rbuf = _bt_getbuf(rel, P_NEW, BT_WRITE);  // 从 FSM 获取空闲页面

如果 FSM 中有之前被 BTP_DELETED 标记后回收的页面，优先复用。否则在索引文件末尾追加新 block。

4.4 第三步：迁移元组

分裂点之后的元组从原页面（左页）拷贝到新页面（右页），原页面的 high key 更新为新的上界（右页面的最小 key）。左右页面的 btpo_next/btpo_prev 重新链接：

迁移前: [Page A] ←→ [Page B]
迁移后: [Page A] ←→ [NEW Page A'] ←→ [Page B]

4.5 第四步：插入父指针（_bt_insert_parent）

_bt_insert_parent() 向父页面插入一个新的 downlink，指向新右页面。如果父页面也满了，递归调用 _bt_split()——分裂从叶子向上传播。根节点分裂时，分配新根页面，放两个 downlink 指向旧根和新兄弟，树高加一，同时更新 metapage 的 btm_root 和 btm_level。

// nbtinsert.c, _bt_insert_parent() 中根分裂的处理（简化）
if (is_root_split) {
    rootbuf = _bt_getbuf(rel, P_NEW, BT_WRITE);
    // 在新根页面写入两个 item，分别指向左子页和右子页
    _bt_update_meta(rel, BufferGetBlockNumber(rootbuf), level + 1, ...);
}
```bash

### 4.6 分裂的性能开销

一次叶子页面分裂涉及：
- 一次 Buffer Manager 分配（可能触发 victim 选择）
- 约半页 IndexTuple 的内存拷贝
- 一次父页面写入（可能触发递归分裂）
- 双向链表的两次指针更新
- WAL record 的构建和写入

全部在持着原页面和父页面 LWLock 的情况下完成。如果 `fillfactor` 设太高（初始填充 100%），分裂频率会随着插入量线性增长。

---

## 五、PG 12+ 去重（deduplicate_items）

### 5.1 问题：非唯一索引的空间浪费

在非唯一索引中，同一个 key 可能对应成千上万行。经典 B-Tree 为每个 `(key, TID)` 对存储独立的 `IndexTuple`。当 10000 行的 `status = 'active'` 时，索引中存储了 10000 份 `'active'` 的字符串拷贝。

PG 12 引入的去重机制改变了这一点：**相同 key 的多个 TID 被打包到一个 posting list 中，key 数据只存一份**。

去重前: [(“active”, tid1)] [(“active”, tid2)] [(“active”, tid3)] [(“active”, tid4)] 去重后: [(“active”, {tid1, tid2, tid3, tid4})]

### 5.2 触发条件

去重由 `nbtdedup.c` 中的 `_bt_dedup_one_page()` 实现，在以下条件同时满足时触发：

1. 页面是叶子页面（只有叶子页面有重复 key 的数据）
2. 页面空间不足以直接插入新项——插入失败后、分裂之前，先尝试去重
3. 索引为**非唯一**索引（`deduplicate_items` 在唯一索引上默认为 off——key 本来就不重复）
4. `deduplicate_items` 存储参数为 `on`（PG 13+ 默认 on）

```c
// src/backend/access/nbtree/nbtdedup.c, _bt_dedup_one_page()（简化）
void _bt_dedup_one_page(Relation rel, Buffer buf, BTInsertState insertstate,
                        bool checkingunique) {
    Page page = BufferGetPage(buf);
    BTPageOpaque opaque = BTPageOpaque(page);

    if (!P_ISLEAF(opaque))
        return;

    OffsetNumber offnum = P_FIRSTKEY;
    OffsetNumber maxoff = PageGetMaxOffsetNumber(page);

    while (offnum <= maxoff) {
        IndexTuple itup = (IndexTuple) PageGetItem(page, ...);
        OffsetNumber nextoff = offnum + 1;

        // 找到所有 key 相同的连续 tuple
        while (nextoff <= maxoff &&
               _bt_compare(rel, insertstate, itup, nextup) == 0) {
            nextoff++;
        }

        // 如果有 2 个以上相同 key，合并为 posting list
        if (nextoff - offnum > 1)
            _bt_swap_posting(rel, buf, offnum, nextoff - offnum);

        offnum = nextoff;
    }
}

5.3 posting list 的物理格式

去重后的 tuple 的 header 中设置了 INDEX_ALT_TID_MASK 标志：

// src/include/access/itup.h
#define INDEX_ALT_TID_MASK  0x2000  // 这是一个 posting list，不是普通 tuple
```text

物理布局：

[IndexTuple Header | INDEX_ALT_TID_MASK] [key data] [TID 1 (6B)] [TID 2 (6B)] … [TID N (6B)]

每个 TID 是 6 字节的 `ItemPointerData`（block number 4B + offset 2B）。去重后，原来 $N$ 个各自独立的 tuple（每个约 `8 + key_size + 6` 字节），变成 1 个 `(8 + key_size + N × 6)` 字节的 tuple。当 $N$ 足够大时，空间节省接近：

$$\text{节省比例} \approx \frac{N - 1}{N} \cdot \frac{\text{key\_size}}{\text{key\_size} + 14}$$

### 5.4 去重的副作用

**对 index-only scan 的影响**：posting list 中的 TID 不对应单独的 VM bit。当一个 page 被去重后，index-only scan 对去重过的 key 需要回表检查可见性，即使对应的 heap page 在 VM 中标记为 all-visible。VM bit 的粒度为 heap page，而 posting list 中的 TID 可能来自多个 heap page。

**对 `=` 扫描的影响**：去重后，扫描器遇到 posting list 时需要展开后逐个返回 TID。`_bt_readpage()` 对此做了优化——展开 posting list 是纯内存操作，开销通常小于节省的 IO。

### 5.5 什么时候该关闭去重

1. **UUID 或几乎唯一的索引**：每个 key 几乎不重复，去重每次扫描都找不到可合并的 tuple，浪费 CPU。
2. **索引列从不被 UPDATE 修改**：HOT update 不需要更新索引——去重在这里没有数据可以合并。

```sql
-- 关闭单个索引的去重
ALTER INDEX idx_orders_customer SET (deduplicate_items = off);

六、WAL 记录类型与崩溃恢复

B-Tree 的所有结构变更通过 WAL 记录，定义在 src/include/access/nbtxlog.h：

分裂的 WAL 是最复杂的——需要记录对三个页面的修改（左页、右页、父页）。XLOG_BTREE_SPLIT_L 和 XLOG_BTREE_SPLIT_R 成对记录，redo 时先恢复左页再恢复右页；父页面的 downlink 插入单独记录为 XLOG_BTREE_INSERT_UPPER。

// src/include/access/nbtxlog.h
typedef struct xl_btree_split {
    uint32       level;              // 分裂层级（0=叶子）
    BlockNumber  leftsib;            // 左兄弟
    BlockNumber  rightsib;           // 右兄弟
    BlockNumber  rnext;              // 新页面之后的下一页
    uint32       npage;              // 分到新页面的元组数
    // 后面跟着：新页面的所有 IndexTuple 数据
} xl_btree_split;
```text

WAL replay 是幂等的——redo 函数在修改页面之前检查 `BufferGetLSNApplied()`，如果页面 LSN 已经大于等于 record LSN，跳过该操作。

---

## 七、运维：常见坑与排查

### 7.1 索引膨胀：分裂后的填充率下降

每次页面分裂，两个新页面的平均填充率约为 50%-70%（具体取决于分裂点选择算法找到的最优位置）。对 append-only 的单调递增主键（如 `SERIAL`），新 key 总是追加到最右页面，只有最右页面在参与分裂，其他页面保持分裂后的填充率不变。但对于随机分布的 key（如 UUID），分裂均匀分布在整个索引中，所有页面都处于 50%-70% 填充状态——索引体积比最优值膨胀 30%-50%。

排查：

```sql
-- 查看索引大小与预期值的偏差
SELECT
    indexrelname,
    pg_size_pretty(pg_relation_size(indexrelid)) AS actual_size,
    idx_scan, idx_tup_read, idx_tup_fetch
FROM pg_stat_user_indexes
WHERE indexrelname = 'idx_orders_customer';

-- 查看各页面的填充率分布
SELECT
    blkno, type, live_items,
    ROUND((8152 - free_size)::numeric / 8152 * 100, 1) AS fill_pct
FROM bt_page_stats('idx_orders_customer', blkno)
FROM generate_series(0, 50) AS blkno;

修复：REINDEX INDEX CONCURRENTLY idx_orders_customer; 重建索引，将填充率恢复到接近 100%（按 fillfactor 的值）。CONCURRENTLY 不会阻塞写入，但需要两次全表扫描。

7.2 UUID 主键的 B-Tree 灾难

UUID v4（完全随机）有两个特征对 B-Tree 极不友好：

1. 随机分布：每个 INSERT 跳到一个随机的叶子页面，所有被碰到的页面都被弄脏、都写 WAL。shared_buffers 缓存的索引页面不断被驱逐和重新读入。
2. 无重复：去重对 UUID 无效——每个 key 唯一。deduplicate_items 每次插入都扫描页面寻找可合并的 tuple，每次都一无所获。

对比实验：

-- UUID 主键的写入性能
CREATE TABLE t_uuid_v4 (id UUID DEFAULT gen_random_uuid() PRIMARY KEY, data TEXT);
INSERT INTO t_uuid_v4 (data) SELECT 'x' FROM generate_series(1, 100000);
-- 观察 pg_stat_user_tables.idx_tup_fetch vs idx_scan

-- SERIAL 主键的写入性能
CREATE TABLE t_serial (id SERIAL PRIMARY KEY, data TEXT);
INSERT INTO t_serial (data) SELECT 'x' FROM generate_series(1, 100000);
```text

SERIAL 主键的 INSERT 是 append-only——每次都在最右叶子页面写入，缓存命中率极高。UUID v4 的 INSERT 是随机写入——每 100 次插入可能踩到 50 个不同的叶子页面，缓存被频繁驱逐。

**缓解方案**：
- 使用 `uuid_generate_v1mc()`（基于时间戳 + MAC 地址，趋势递增，部分有序）
- 或者使用 `uuid_generate_v7()`（PG 17 内置时间排序 UUID）
- 如果必须用 UUID v4，考虑降低 `fillfactor` 到 80，给后续插入留足空间

### 7.3 fillfactor 的权衡与配置陷阱

`fillfactor` 控制索引页面在初始构建时的填充比例。后续插入可以使用剩余空间：

| fillfactor | 优点 | 缺点 | 适用场景 |
|-----------|------|------|---------|
| 90-100（默认）| 页面利用率高，索引小，读快 | INSERT 分裂频繁 | append-only（`SERIAL`、时间序列） |
| 70-80 | 有空余容纳新 key，分裂少 | 索引体积增大 10%-20% | UPDATE-heavy、随机插入 |
| 50 | 极低的初始填充，分裂极少 | 索引体积约翻倍，scan 慢 | 极端随机写入 + 极少查询 |

常见配置错误：在 append-only 的 `SERIAL` 主键上设 `fillfactor = 70`——新 key 只在最右页面插入，不会用到预留空间。降低了页面利用率却没有减少分裂。

排查：

```sql
-- 查看索引的页数和每个页面的填充率
SELECT
    (SELECT count(*) FROM bt_page_stats('idx_orders_pkey')) AS total_pages,
    (SELECT pg_relation_size('idx_orders_pkey')) AS index_size;

-- 如果一个索引有 1000 页，与表大小的比率异常高，
-- 可能是 fillfactor 设太低或分裂过度导致膨胀

7.4 唯一索引插入的死锁风险

唯一索引上的并发 INSERT 有一个经典死锁场景：

-- Session 1
INSERT INTO t (id) VALUES (1);    -- 在唯一索引中插入 key=1，获取页面的排他 LWLock

-- Session 2
INSERT INTO t (id) VALUES (1);    -- 同样尝试插入 key=1
                                  -- _bt_check_unique() 发现冲突
                                  -- 等待 Session 1 的事务结束
                                  -- 但在等待过程中持有页面的共享 LWLock

-- Session 1 执行其他操作需要获取同一页面的排他 LWLock
-- → 死锁：Session 1 等锁，Session 2 持锁并等 Session 1 的事务
```text

PG 的 `_bt_check_unique()` 通过"推测性插入"（speculative insertion）来避免这个死锁。如果发现可能的冲突（另一个事务正在插入相同的 key），PG 使用 `XactLockTableWait()` 在事务级别等待，而不持有页面级别的锁。如果最终发现对方回滚了，PG 的插入继续；如果对方提交了，上报唯一约束冲突错误。

排查唯一索引死锁：

```sql
SELECT
    pg_blocking_pids(pid) AS blocking_pids,
    wait_event_type, wait_event,
    query
FROM pg_stat_activity
WHERE wait_event_type = 'Lock' AND query LIKE '%INSERT%';

7.5 去重与 index-only scan 的隐性代价

去重后的 posting list tuple 不设置 VM 位——即使对应的 heap page 在 VM 中标记为 all-visible，index-only scan 对 posting list 中的 TID 也需要回表检查可见性。在以下场景可能观察到性能回归：

-- 建一个高重复率索引 + index-only scan 查询
CREATE TABLE t (val INT, extra TEXT);
INSERT INTO t SELECT 1, 'x' FROM generate_series(1, 100000);
CREATE INDEX idx_t_val ON t (val);

-- index-only scan
EXPLAIN (ANALYZE, BUFFERS) SELECT val FROM t WHERE val = 1;
-- 观察 Heap Fetches: 可能有大量的回表操作
```text

如果 `Heap Fetches` 很高（远超 `rows`），说明 index-only scan 没有达到预期的优化效果——部分原因是去重后的 posting list 需要回表验证。关闭去重后重新测试：

```sql
ALTER INDEX idx_t_val SET (deduplicate_items = off);
-- 重新执行 EXPLAIN ANALYZE，对比 Heap Fetches

但这之间存在权衡：关闭去重减少回表，但索引体积会增大，可能超过 shared_buffers 缓存容量。

八、实验：用 pageinspect 观察 B-Tree 页面

8.1 环境准备

CREATE EXTENSION pageinspect;

CREATE TABLE test_btree (val INTEGER);
INSERT INTO test_btree SELECT (random() * 10000)::INTEGER
FROM generate_series(1, 500);
CREATE INDEX idx_test ON test_btree (val);
```bash

### 8.2 查看索引元数据

```sql
SELECT * FROM bt_metap('idx_test');
-- 输出:
--  magic  | version | root | level | fastroot | fastlevel | allequalimage
-- --------+---------+------+-------+----------+-----------+---------------
--  340322 |       4 |    3 |     1 |        3 |         1 | t

root=3 表示根页面是 block 3（block 0 是 metapage，block 1-2 是叶子页面），level=1 表示根页面在层级 1（叶子层 level=0），树高为 2。

8.3 查看页面统计

SELECT * FROM bt_page_stats('idx_test', 1);
-- type=l（叶子页面），live_items 约 200，free_size 约 5000
-- btpo_level=0，btpo_next 指向下一页

SELECT * FROM bt_page_stats('idx_test', 3);
-- type=i（内部页面），live_items=2，btpo_level=1
```bash

### 8.4 逐项查看页面内容

```sql
-- 叶子页面
SELECT itemoffset, ctid, itemlen, dead, data
FROM bt_page_items('idx_test', 1)
LIMIT 5;

-- itemoffset=1: high key (P_HIKEY)，data 是十六进制表示的键值
-- itemoffset=2: 第一个用户数据项，ctid=(heap_block, heap_offset)

-- 内部页面（根页面）
SELECT itemoffset, ctid, itemlen, data
FROM bt_page_items('idx_test', 3);
-- 内部节点的 ctid 不指向 heap tuple，而是子页面的 block number
```bash

### 8.5 观察页面分裂

```sql
-- 插入足够多的行迫使分裂
INSERT INTO test_btree SELECT generate_series(501, 1000);
-- 再次查看 metapage
SELECT * FROM bt_metap('idx_test');
-- 观察 root 和 level 是否变化（树高可能增加）

-- 遍历所有页面，观察 rightlink 链
SELECT blkno, type, btpo_next, live_items
FROM generate_series(0, 10) AS blkno
JOIN LATERAL bt_page_stats('idx_test', blkno) ON true
ORDER BY blkno;

8.6 观察去重效果

CREATE TABLE test_dedup (val INTEGER);
INSERT INTO test_dedup SELECT 42 FROM generate_series(1, 500);
CREATE INDEX idx_dedup ON test_dedup (val);

-- 观察去重后的 posting list
SELECT itemoffset, ctid, htid, tids
FROM bt_page_items('idx_dedup', 1);

-- htid 包含第一个 TID，tids 包含剩余的 TID 数组
-- 如果所有 500 行都去重成功，itemoffset=2 会是一个 posting list
```text

对比关闭去重时的大小：

```sql
SELECT pg_relation_size('idx_dedup') AS size_with_dedup;
DROP INDEX idx_dedup;
CREATE INDEX idx_dedup ON test_dedup (val) WITH (deduplicate_items = off);
SELECT pg_relation_size('idx_dedup') AS size_without_dedup;

在 500 行全为相同 key 的场景下，去重开启时的索引体积约为关闭时的 5%-10%。

九、关键要点

1. B-Tree 页面通过 BTPageOpaque 管理同层链接和节点类型——rightlink 让范围扫描和并发操作不需要回父节点；high key 提供本地搜索上界，是分裂和插入路由的决策依据。
2. **_bt_split() 的分裂点选择不是简单的 50/50**——nbtsplitloc.c 针对 item 大小不均、相同 key 分组、新项位置三种场景选择不同策略，目标是左右页面都能装下自己的元组且填充率尽量均衡。
3. 后缀截断让内部节点变窄——插入父页面的 downlink key 被截断到”刚好能区分左右子树的最短前缀”，让每个内部页面容纳更多 key，降低树高。
4. PG 12+ 的去重将相同 key 的 TID 合并为 posting list——在高重复率列上索引体积可以减少 90% 以上，但对 UUID 和几乎唯一的索引无效，对 index-only scan 有回表代价。
5. fillfactor 是控制分裂频率的主要杠杆——对 append-only 的单调递增主键，默认 100 即可；对随机分布的 key（UUID），降低到 70-80 可以减少分裂频率，代价是更大的索引体积和更慢的扫描。
6. bt_page_items() 和 bt_metap() 是观察 B-Tree 内部结构的核心工具——可以直接查看每个页面的 high key、rightlink 链、去重后的 posting list、分裂后的页面填充率。

下一章：GiST 索引 —— PG 的可扩展索引框架：抽象算子接口（Consistent / Union / Penalty / PickSplit）、几何类型和全文搜索的 GiST 实现。

上一章：JIT 编译

参考资料

源码（PG 17）

• src/backend/access/nbtree/nbtinsert.c：_bt_doinsert(), _bt_insertonpg(), _bt_split(), _bt_insert_parent()
• src/backend/access/nbtree/nbtsplitloc.c：_bt_findsplitloc(), _bt_bestsplitloc(), _bt_truncate()
• src/backend/access/nbtree/nbtdedup.c：_bt_dedup_one_page(), _bt_swap_posting()
• src/backend/access/nbtree/nbtsearch.c：_bt_search(), _bt_binsrch(), _bt_readpage()
• src/backend/access/nbtree/nbtxlog.c：btree_xlog_insert(), btree_xlog_split()
• src/backend/access/nbtree/nbtpage.c：_bt_getbuf(), _bt_split_alloc()
• src/backend/access/nbtree/nbtutils.c：_bt_compare(), _bt_truncate()
• src/include/access/nbtree.h：BTPageOpaqueData, BTMetaPageData, P_HIKEY, P_FIRSTKEY
• src/include/access/nbtxlog.h：xl_btree_split, WAL record 类型定义
• src/include/access/itup.h：IndexTupleData, INDEX_ALT_TID_MASK

官方文档

• PostgreSQL Documentation, Chapter 67: B-Tree Indexes — B-Tree 内部机制的官方描述，包括页面格式、分裂算法和去重
• PostgreSQL Documentation, Section 67.4: B-Tree Deduplication — 去重的设计文档和性能考量
• PostgreSQL Documentation, Section 11.2: Index Types — fillfactor 和 deduplicate_items 存储参数

论文与设计讨论

• Lehman, P. L. & Yao, S. B. Efficient Locking for Concurrent Operations on B-Trees. ACM TODS, 1981. — B-link tree 原始论文，PG 的 rightlink + high key 设计理论基础
• Peter Geoghegan, “B-Tree Deduplication for PostgreSQL 12”, pgsql-hackers (2019) — 去重功能的原始设计提案和实现迭代
• pgsql-hackers discussion: “Suffix truncation for B-Tree inner pages” — 后缀截断的设计动机和性能数据
• Graefe, G. A Survey of B-Tree Locking Techniques. ACM TODS, 2010. — B-Tree 并发控制方案的全面综述