深入理解PostgreSQL B-Tree索引：完整指南（上）

背景

在大型表上进行查询优化是数据库日常运维的核心挑战之一，尤其是在过滤操作逐渐变慢时，索引的合理使用变得至关重要。然而，要想真正高效地利用索引，理解其内部工作机制是必不可少的。PostgreSQL 提供了多种索引类型，其中 B-Tree（平衡树）索引是最常用、最基础的一种。本系列文章将深入剖析 PostgreSQL 中 B-Tree 索引的内部原理，并探讨如何更高效地使用这类索引。本文是系列的第一部分，重点介绍 B-Tree 索引的逻辑架构、PostgreSQL 的数据存储方式，以及索引的初步实现概念。

核心内容

PostgreSQL 提供了多种索引类型，每种采用不同的算法，适用于不同场景：

• B-tree
• Hash
• GiST
• SP-GiST
• GIN
• BRIN

每种索引都有其特定用途，应根据实际需求选择最合适的类型。

B-Tree 索引的逻辑架构

B-Tree 是“平衡树”（Balanced Tree）的缩写，意味着从根节点到每个叶子节点的距离在所有层级上保持一致。与普通二叉树不同，B-Tree 的根节点和内部节点可以有超过两个子节点，这有效减少了树的深度，从而提升搜索效率。B-Tree 的主要特点包括：

• 节点灵活性：节点可以有多个子节点，通常最小为两个，最大由树的阶数（M）决定。
• 高度管理：自动调整以保持高度为 logM N，优化搜索操作。
• 排序顺序：数据保持有序，最小值在左侧，最大值在右侧。
• 均匀性与效率：所有叶子节点位于同一层，确保效率与一致性；叶子节点之上没有空子树。

B-Tree 针对平衡性和检索效率进行了优化，非常适合需要频繁插入和检索的系统，如数据库索引和文件系统。

PostgreSQL 中的 B-Tree 索引基于 Lehman 和 Yao 在 1981 年提出的算法。当对表进行简单搜索且没有索引时，PostgreSQL 默认使用顺序扫描，即遍历表中的每条数据并比较，若条件匹配则返回。下图对比了使用索引与不使用索引的复杂度差异（原文附图未提供，但描述中指出：使用索引时，对于大量数据的读取，信息检索速度更快）。

回顾：PostgreSQL 如何存储数据

当我们创建表时，通常认为数据会按序存储在磁盘上，但实际上数据可能分布在不同的页面（Page）以及页面内的不同位置。

例如，创建表 t(a INTEGER, b INTEGER, c VARCHAR) 后，物理存储结构如下图所示（原文附图未提供，但描述为：数据以页面为单位存储，每个页面包含头部、元组、指针等）。

可以通过以下 SQL 查询表的元数据信息：

SELECT class.oid AS "OID", relname AS "Relation Name",
       schema.nspname AS "Schema", usr.rolname AS "Object Owner",
       coalesce(tblsp.spcname, 'pg_default') AS "Tablespace",
       relpages AS "Amount Pages", reltuples AS "Amount Tuples",
       reltoastrelid AS "TOAST table",
       CASE
           WHEN relpersistence = 'p' THEN 'Permanent'
           WHEN relpersistence = 't' THEN 'Temporary'
           ELSE 'Unlogged'
       END AS "Type",
       pg_relation_filepath(class.oid) AS "File Path",
       pg_size_pretty(pg_relation_size(class.oid)) AS "Relation Size"
FROM pg_class class
INNER JOIN pg_namespace schema ON schema.oid = class.relnamespace
INNER JOIN pg_authid usr ON usr.oid = class.relowner
LEFT JOIN pg_tablespace tblsp ON tblsp.oid = class.reltablespace
WHERE relname = 't';

查询结果中涉及的关键概念：

• OID（对象标识符）：PostgreSQL 基于系统序列生成的唯一标识，每个新对象（列、函数、触发器、虚拟表等）都会获得一个 OID，用于无歧义地引用该对象。
• 默认表空间：通常为 pg_default。
• Schema：默认是 public。
• 表所有者：创建该表的用户，负责管理访问权限。
• 页面与元组数量：relpages 和 reltuples 分别表示该表占用的页面数和行数（元组数）。
• TOAST 表：辅助表，用于拆分过长的行，使其能适应页面大小限制。
• 表类型：当前创建的是普通持久表（Permanent）。
• 文件路径：映射到操作系统级别的路径，位于 PostgreSQL 实例的 pg_home 目录下。例如，文件名为 16389，该二进制文件存储了表的内容（插入、更新、删除操作均会影响该文件）。文件名与表的 OID 一致，形成一一对应关系。

在未插入数据时，表大小为 0 字节。PostgreSQL 中小于 1GB 的表存储在一个文件中，超过 1GB 则会被拆分为多个 1GB 大小的文件，以便高效管理大数据集。

页面结构详解

每个页面（Page）的结构从顶部和底部同时增长。当插入数据时，元组（T1、T2、T3）从页面底部左侧开始写入，并向上增长，直到与页面起始处附近的指针值（I1、I2、I3）相遇。指针是对页面中较低位置特定元组的引用。这种结构经过充分优化，能高效存储信息，并帮助 PostgreSQL 优化器有效处理偏移量和指针。

页面包含以下部分：

• 页面头部：元数据层，存储页面可用空间总量。
• 事务指针：每个元组和行都包含事务信息。
• 特殊区域：对于普通表不使用，但对于索引结构是必需的，因为页面不仅是表的基础存储单元，也是索引的基础存储单元。

ctid 介绍

在 PostgreSQL 中，ctid 是表中每一行（元组）的唯一标识符，表示该元组在表存储文件中的物理位置。ctid 由一对数字组成：块号（block number）和块内的偏移量（offset）。通过 ctid 可以直接访问表中的任意行。结合 OID，我们便获得了定位信息的坐标：一侧是数据文件，另一侧是数据文件中的页面，最后是页面中存储具体信息的元组。

这一原理是 B-Tree 索引的基础：B-Tree 索引的叶子节点指向特定文件中的 ctid。

PostgreSQL 中 B-Tree 索引的逻辑表示

B-Tree 索引在 PostgreSQL 中是一个独立的数据文件，位于表数据文件附近（可以创建独立的表空间专门存储索引）。创建索引时，数据库会将索引的详细信息记录在元数据中，包括索引文件的位置和路径。

创建标准 B-Tree 索引的命令如下：

CREATE INDEX index_name ON table_name (column_name);

该命令在表 table_name 的列 column_name 上创建名为 index_name 的索引。

关键要点

• PostgreSQL 提供了六种索引类型（B-tree、Hash