Skip to content
2027校招后端+Agent八股

PostgreSQL 核心存储与索引机制

堆表无序存储、CTID 物理寻址、HOT 堆内元组技术、B-tree 索引底层、覆盖索引与深分页优化。

Updated View as Markdown
For humans

PostgreSQL 核心存储与索引机制

校招考察频度：★ 高频（核心必背·高频生死线） 一句话速记：数据按堆无序放，物理指针靠 CTID；索引统一指向堆，HOT 堆内防膨胀；防回表靠 INCLUDE 与 VM，大翻页用 Keyset 游标。

在校招面试中，数据库底层机制是考察候选人计算机系统功底的核心试金石。不同于常见误区，PostgreSQL 采用的是堆表（Heap Table）+ 物理指针寻址的架构，理解这一底层设计是理解其 MVCC、HOT 与性能优化的基石。

一、为什么索引底层默认要用平衡树（B-Tree）？

面试官经典拷问：“为什么数据库索引底层不用 Hash、二叉搜索树、平衡二叉树（AVL）或红黑树？”

数据结构缺点与无法作为通用主索引的原因
Hash 索引仅支持等值查询 O(1)，完全不支持范围查询（<、>、BETWEEN）、模糊查询（LIKE）与排序（ORDER BY）。无法满足绝大多数业务场景。
二叉搜索树 / AVL / 红黑树树的每个节点最多只有 2 个子节点，当数据量达到千万级时，树的高度（Height）极高。数据库数据持久化在磁盘上，访问树的每一个节点都对应一次随机磁盘 I/O（毫秒级）。树太深会导致查询 I/O 次数过多，系统吞吐急剧下降。
B 树（B-Tree） / B+ 树绝对优势：① 多叉平衡树，扇出（Fan-out）极大、树高极低。单个数据页（PG 默认为 8KB）能容纳数百个键值指针，通常 34 层即可支撑千万甚至上亿级数据，定位一条数据最多只需 34 次磁盘 I/O；② 节点内数据有序，叶子节点互相串联，范围扫描与排序性能极佳。

B-Tree 索引：大扇出、低树高、叶子节点直接保存数据物理指针 CTID

核心推导：树高与容量估算

  • PostgreSQL 默认数据页（Page）大小为 8KB。
  • 假设索引键为 BIGINT（8 字节），加上指针与头部开销约 16 字节。一个非叶子页可容纳约 8192 / 16 ≈ 500 个分支路由（扇出系数）。
  • 3 层平衡树：根节点（500 分支）× 二级节点（500 分支）× 叶子节点（容纳约 300 条索引项），可支撑： 500 × 500 × 300 ≈ 7500 万行记录
  • 结论：在数千万级数据体量下，通过 B-Tree 索引定位记录只需要 3 次页读取（且根节点与二级节点通常常驻内存 shared_buffers，实际只需 1 次磁盘 I/O）。

二、堆表（Heap Table）与 CTID 物理寻址

这是 PostgreSQL 与很多聚簇索引数据库最根本的架构区别：

1. 堆表组织形式

  • 无序存储：数据行（元组 Tuple）是按照插入的时间顺序追加写入到数据堆表（Heap Table）的各个 8KB 数据页中的，不按主键的顺序物理排列。
  • CTID（Item Pointer）：每个元组在物理存储上的唯一坐标，格式为 (BlockNumber, OffsetNumber)：
    • BlockNumber：数据块号（第几页）；
    • OffsetNumber：页内行指针数组（ItemId）的下标（第几个槽位）。
  • 通过 SELECT ctid, * FROM users; 可以直接查出每行记录当前的物理存储位置。

2. 索引地位完全平等

  • 在 PostgreSQL 中，主键索引和二级索引没有任何物理存储上的特权。
  • 无论是主键的 B-tree 索引，还是在普通列上创建的二级索引，它们的叶子节点存放的都是： 索引列键值 (Key) ──> 目标行在堆表中的物理地址 (CTID)
  • 回表访问：通过索引定位到 CTID 后，直接根据 BlockNumber 读入对应的数据页，再根据 OffsetNumber 取出完整行数据。
查询执行路径：
[SQL: WHERE username = 'alice']
       │
       ▼ (遍历 B-Tree)
[索引页 Leaf Tuple: Key='alice', CTID=(Block 42, Offset 3)]
       │
       ▼ (一次寻址)
[堆表数据页 Block 42 -> 槽位 Offset 3 -> 提取整行数据并检查 MVCC 可见性]

三、HOT（Heap-Only Tuples）堆内元组技术（高分分水岭）

1. 堆表架构的原生痛点：写放大与索引膨胀

在传统的堆表更新中，每次 UPDATE 一行数据：

  1. 原位置装不下或因为 MVCC，必须在堆表中插入一条新的元组（拥有全新的 CTID）；
  2. 因为 CTID 改变了，表上所有的索引（主键索引、联合索引、外键索引等）都必须插入一条新的索引项指向新的 CTID；
  3. 这会导致巨大的磁盘写 I/O，以及严重的索引膨胀（Index Bloat）。

2. HOT 机制的触发条件与原理

PostgreSQL 8.3 引入了 HOT（堆内元组） 优化。当满足以下两个条件时自动触发：

  1. 未更新索引列：本次 UPDATE 操作没有修改任何建立在表上的索引列；
  2. 同页有空闲空间：原元组所在的同一个 8KB 数据页内，有足够的空闲空间容纳新生成的元组。

HOT 机制：索引指针保持不变，页内元组通过 t_ctid 形成链表

  • 执行效果：
    • 索引页根本无需任何修改，依然指向最初的根元组 (1, 1)；
    • 堆页内原元组的指针 t_ctid 被修改为指向新元组 (1, 2)；
    • 查询沿着索引定位到 (1, 1) 后，在堆页内部顺着 HOT 链表直接找到最新的 (1, 2)；
    • 收益：大幅消除写放大，彻底避免了频繁更新非索引列时的索引膨胀！
  • 生产调优建议：对更新极频繁的表，可在建表时调小 fillfactor（如 fillfactor = 80），为每个页预留 20% 空闲空间，专门用于容纳 HOT 更新。

四、覆盖索引（Covering Index）与 Index-Only Scan

1. INCLUDE 子句（覆盖索引利器）

PostgreSQL 11 引入了对 B-tree 索引的 INCLUDE 支持：

CREATE INDEX idx_orders_user_covering 
ON orders (user_id) 
INCLUDE (amount, status);
  • 核心原理：
    • user_id 是索引键（Key Column），参与 B-tree 树形分支的排序与二分查找；
    • amount, status 是附加列（Non-key Column），仅保存在叶子节点中，不参与树的排序，不增加内部节点的扇出压力；
    • 当执行 SELECT amount, status FROM orders WHERE user_id = 100; 时，所有需要的数据都在索引叶子页中。

2. Index-Only Scan 成立的关键：可见性映射（VM）

在很多系统里覆盖索引直接返回数据即可，但在 PostgreSQL 中，索引元组内部不包含事务可见性信息（没有 xmin/xmax）！ 那它是怎么做到零回表的？

  • 依赖 Visibility Map（可见性映射，简称 VM） 文件：
    • VM 用位图记录每个数据页是否对所有当前事务“全可见（All-Visible）”；
    • 如果 VM 标记该数据页为全可见，说明该页中所有元组都早已提交且没有死元组，执行器直接信任索引并返回数据（真正实现零回表）；
    • 如果 VM 显示该页可能存在未提交或已删除元组，执行器仍必须访问堆页验证可见性（产生 Heap Fetches）。
  • 面试要点：若发现 EXPLAIN 中 Index-Only Scan 伴随大量 Heap Fetches，通常是因为该表缺乏及时 VACUUM，导致 VM 位图未被更新。

五、最左前缀原则与经典索引失效场景

对联合索引 INDEX idx_order (tenant_id, user_id, create_time)：

  1. 最左前缀原理：索引树首先按 tenant_id 排序；在 tenant_id 相同的前提下再按 user_id 排序；以此类推。
  2. 匹配规律：
    • 必须包含最左列：WHERE tenant_id = 1（命中）、WHERE tenant_id = 1 AND user_id = 2（全命中）；
    • 跳过最左列：WHERE user_id = 2（完全无法使用该索引）；
    • 范围中断效应：WHERE tenant_id = 1 AND user_id > 10 AND create_time = '2026-01-01'，只有 tenant_id 和 user_id 走索引检索，create_time 无法用于树的二分定位。

经典索引失效场景手册（面试必背）

  1. 索引列被函数包裹或算术运算：
    • 错误：WHERE DATE(created_at) = '2026-01-01' 或 WHERE age + 1 = 20；
    • 解决：改写为范围查询 WHERE created_at >= '2026-01-01' AND created_at < '2026-01-02'，或直接建立表达式索引： 
      CREATE INDEX idx_user_lower_email ON users (lower(email));
  2. 隐式类型转换：
    • 如 phone 字段为 VARCHAR，查询写成 WHERE phone = 13800000000（数字类型），优化器会进行类型强制转换，导致索引失效。
  3. 左前缀模糊查询：
    • LIKE '%abc' 或 LIKE '%abc%' 无法使用 B-tree 索引。
    • 解决：如果必须全文模糊检索，使用 PostgreSQL 原生支持的 GIN 倒排索引 + pg_trgm 扩展： 
      CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE INDEX idx_user_name_trgm ON users USING gin (username gin_trgm_ops);
  4. 部分索引（Partial Index）利用不当：
    • PG 支持强大的部分索引，只索引活跃数据： 
      CREATE INDEX idx_active_orders ON orders (user_id) WHERE status = 'PENDING';
    • 只有查询条件显式带上 WHERE status = 'PENDING' 时，优化器才会走该索引。
  5. 优化器代价评估（选择度过低）：
    • 当查询条件命中的行数超过全表约 20%~30% 时，优化器评估随机 I/O（random_page_cost）的成本高于连续顺序扫描（seq_page_cost），会主动放弃索引而走 Seq Scan。

六、千万级深分页（Deep Pagination）性能陷阱与优化

面试高频压轴题：“在数千万数据量下，SELECT * FROM orders ORDER BY id LIMIT 10 OFFSET 1000000; 为什么会导致慢 SQL 甚至拖垮数据库？如何优化？”

1. 为什么深分页会极慢？

  • 执行代价：即使 id 上有索引，执行引擎也必须在索引中顺序扫描前 1,000,010 个元组，逐一通过 CTID 读取堆表数据并判断 MVCC 可见性；
  • 然后将前 1,000,000 条数据在内存中无情抛弃，仅仅返回最后 10 条；
  • 这导致前 100 万次磁盘 I/O 和 CPU 解码完全是无用功。

2. 工业界优化三大招

方案一：Keyset 游标分页（Seek Method · 性能极致 · 首选）

利用主键或有序字段的唯一性，每次翻页带上上一页最后一条记录的标识：

-- 查下一页：传入上一页最后一条记录的 id
SELECT * FROM orders 
WHERE id > 985623 
ORDER BY id ASC 
LIMIT 10;
  • 原理：B-tree 树形查找 O(log N) 直接定位到 id = 985623 对应的叶子节点位置，直接向后拉取 10 条数据即可。
  • 耗时：恒定在 1ms 以内，与翻页深度彻底脱钩。
  • 缺点：仅支持“上一页/下一页”滚动加载，无法随机跳到“第 500 页”。

方案二：子查询延迟关联（CTE 结合覆盖索引）

若必须支持跳转页码，先在只包含索引列的子查询中完成分页（利用 Index-Only Scan 免读堆表），最后通过 JOIN 回表读取整行：

WITH paged_ids AS (
    SELECT id FROM orders 
    ORDER BY created_at 
    LIMIT 10 OFFSET 1000000
)
SELECT o.* 
FROM orders o 
JOIN paged_ids p ON o.id = p.id;
  • 原理：子查询只扫描索引，无需读取宽表数据；最终仅针对目标 10 条记录读取堆表。

方案三：业务限制与搜索引擎分流

  • 限制最大翻页深度（如前 100 页）；超大规模深度查询交由数仓或 Elasticsearch 处理。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close