B+Tree 内部机制与扫描类型：Oracle vs PostgreSQL vs MySQL

一个fish

380人浏览 · 2026-07-06 09:23:48

一个fish · 2026-07-06 09:23:48 发布

为什么索引建好了，有的查询走索引快，有的查询反而比全表扫描还慢？答案不在索引的"外形"，而在它的"内功"：页分裂、填充因子、以及数据库选择哪种扫描方式。三库虽然都用 B+Tree，内部机制却大相径庭。

前言：索引不是"一本字典"，而是"一棵活着的树"

很多工程师把索引理解成静态的字典——建好之后固定不变，查就是了。但 B+Tree 索引是一棵"活着的树"：每当你插入、更新、删除数据，树的结构就在变化。页分裂时树会长高，大量删除时页会变稀疏，叶子节点的物理顺序会逐渐偏离逻辑顺序。

Oracle、PostgreSQL、MySQL InnoDB 虽然都用 B+Tree，但它们在页大小、分裂策略、空间回收、扫描算法上各自为政。这些差异直接决定了同一句 SQL 在三库中的性能表现可能差出几倍甚至几十倍。

一、B+Tree 的内部结构：统一框架下的三种实现

1.1 统一的结构模型

三库的 B+Tree 都遵循同样的基本结构：

                    根节点（Root Page）
                   /                    \
              内节点（Branch）          内节点（Branch）
              /      \                 /      \
         叶子（Leaf） 叶子           叶子     叶子
          ⇔ 双向链表 ⇔              ⇔ 双向链表 ⇔

根节点与内节点：存储键值 + 子页指针，不存实际数据；
叶子节点：存储完整键值 + 数据指针/实际数据，通过双向链表连接；
所有键值只在叶子节点出现一次（B+Tree 与 B-Tree 的核心区别）。

但"同一个结构模型"之下，三库的实现差异从第一个参数就开始分叉——页大小。

1.2 页大小对比

数据库	默认页大小	可调范围	限制
Oracle	8KB	2/4/8/16/32KB	建库时设定，不可为单表调整
PostgreSQL	8KB	编译时设定（1-32KB）	需重新编译，极少调整
MySQL InnoDB	16KB	4/8/16/32/64KB	可通过 `innodb_page_size` 调整

页大小直接影响树的"高度"和 I/O 效率。同样 500 万行数据，16KB 页的树约 3 层，8KB 页可能需要 4 层——每多一层就多一次 I/O。

1.3 索引组织表 vs 堆表索引的树结构

虽然上表列出了标准 B+Tree 结构，但 Oracle 索引组织表（IOT）和 MySQL 聚簇索引的 B+Tree 有一个本质区别：叶子节点存的是整行数据，不是指针。

这在 Oracle 中是可选的（ORGANIZATION INDEX），在 MySQL InnoDB 中是强制的（聚簇索引）。

在堆表模型中（Oracle 默认堆表、PG 堆表），B+Tree 叶子节点存的是 键值 + 行定位符（ROWID/TID）。叶子节点之间的双向链表使范围扫描能按索引顺序遍历，但每访问一个键值就要用 ROWID/TID 去堆表取一行数据。

二、页分裂：树的"生长痛"

当向一个已满的叶子页插入新键值时，B+Tree 必须分裂该页。这是索引维护中开销最大的操作。

2.1 Oracle 的 PCTFREE：为未来预留空间

Oracle 通过 PCTFREE 参数控制索引页中的空闲空间比例：

-- 创建索引时设置 PCTFREE
-- PCTFREE=10 表示每个索引页保留 10% 的空间用于后续 UPDATE
CREATE INDEX idx_orders_date ON orders(order_date) PCTFREE 10;

数据插入阶段：Oracle 将页填满到 100% - PCTFREE，预留 PCTFREE 空间；
UPDATE 导致键值变大时：优先使用预留空间，避免行迁移和页分裂；
默认 PCTFREE=10：对于纯 INSERT 场景（如日志表），可设为 0 减少空间浪费。

2.2 PG 的 fillfactor：同样是预留空间

PG 使用 fillfactor 实现类似效果，但一些行为不同：

-- 默认 fillfactor=90（堆表），索引 fillfactor=90
CREATE INDEX idx_orders_date ON orders(order_date) WITH (fillfactor = 70);

PG 的 fillfactor 控制索引页在两种场景下的填充率：初始创建索引时，以及向 B+Tree 最右侧追加新键值时（新页的初始填充）。但对于非最右侧的页面——也就是页分裂产生的新页——fillfactor 不起作用，这些页面在后续插入中会逐渐填满；
与 Oracle 的关键区别：Oracle 的 PCTFREE 是一个硬上限——任何时候页都不会超过 100%-PCTFREE 的填充率。而 PG 的 fillfactor 只在上述两种场景生效，日常插入不受其约束。这意味着 PG 索引的页利用率更高，但也更容易触发页分裂。

2.3 MySQL InnoDB 的页分裂：最"激进"

InnoDB 的页分裂策略与 Oracle 和 PG 有本质差异：

默认不预留空间：InnoDB 的 MERGE_THRESHOLD（默认 50%）控制的是何时合并半空页，而不是插入时的预留空间；
分裂策略：InnoDB 在页分裂时，通常将 50% 的数据留在原页，50% 移到新页。这意味着分裂后两个页各有 50% 的空闲空间；
但后续插入会迅速填满这些空间。

自增主键的优势在这种机制下体现得最明显：

自增主键的新值总是比所有已有值大，始终追加到最右叶子页；
最右页填满后分裂，原页保持半满，新页接收后续插入——但在追加场景下这是最优的；
如果主键是 UUID 等随机值，新键值可能落在 B+Tree 的任意位置，引发大量页分裂，索引碎片化严重。

自增主键和 UUID 主键在页分裂行为上的差异非常直观：自增主键的分裂几乎只发生在 B+Tree 最右侧，而 UUID 主键的分裂分散在整棵树中，且频繁引发内节点分裂。

InnoDB 的页分裂还有一个隐藏开销：因为二级索引存的是主键值而不是物理地址，聚簇索引中行的物理位置变动不影响二级索引。这是一个优势——但也意味着聚簇索引本身的页分裂代价全部由聚簇索引独自承担。

三、索引扫描类型：同样的 SQL，不同的走法

3.1 唯一扫描（Unique Scan）

WHERE id = 100，主键或唯一索引。

数据库	扫描流程	回表需求
Oracle 堆表	根→内→叶子→取 ROWID→堆表取行	是（1次I/O）
Oracle IOT	根→内→叶子→直接返回数据	否
PG	根→内→叶子→取 TID→堆表+可见性检查	是
MySQL	根→内→叶子→直接返回数据	否

三库在唯一扫描上的性能差异主要来自回表代价和缓存命中率。对于热点数据，如果数据页在内存中，回表只是一次内存访问，差异不大。

3.2 索引范围扫描（Index Range Scan）

WHERE order_date BETWEEN '2026-06-01' AND '2026-06-30'

这是最能体现三库差异的扫描类型：

Oracle：

在索引中找到起始键值 → 沿叶子双向链表顺序遍历 → 每行通过 ROWID 去堆表取数据；
IOT 场景下，叶子节点直接存数据且物理有序，范围扫描效率最高；
TABLE ACCESS BY INDEX ROWID 可能导致大量随机 I/O，此时 Oracle 优化器可能选择全表扫描。

PostgreSQL：

在索引中找到起始键值 → 沿叶子链表遍历取 TID → 逐行访问堆表；
如果堆表数据物理有序（如定期 CLUSTER 后），顺序 I/O 效率高；
如果堆表数据物理无序，每次通过 TID 访问堆表都是随机 I/O；
PG 使用 Bitmap Index Scan 来自动优化：先收集所有 TID，按物理页号排序后再批量访问。

MySQL InnoDB：

范围扫描在二级索引上代价最大；
先扫描二级索引拿到主键值列表，再逐条回表查询聚簇索引；
优化器通过 MRR（Multi-Range Read） 将主键值排序后再批量回表；
如果 SELECT 的列全在二级索引中（覆盖索引），跳过回表步骤。

3.3 索引跳跃扫描（Index Skip Scan）

这是 Oracle 独有的能力，PG 和 MySQL 均不支持（截至 2026 年）。

-- 假设索引：(customer_id, order_date)
-- 查询：跳过 customer_id，只查 order_date
SELECT * FROM orders WHERE order_date = '2026-06-15';

-- Oracle：索引跳跃扫描
-- 遍历 customer_id 的每个唯一值，在每个值下查找 order_date='2026-06-15'
-- 计划显示：INDEX (SKIP SCAN)

-- PG/MySQL：此索引无法用于该查询，除非创建 (order_date) 单列索引
-- 计划显示：Seq Scan / 全表扫描

跳跃扫描的前提是前导列的不同值较少。如果 customer_id 有 100 万个唯一值，Oracle 也不会选择跳跃扫描。这不是万能优化，但在前导列基数较低时非常有效。

3.4 索引快速全扫描（Index Fast Full Scan）

数据库	是否支持	实现方式
Oracle	✅	多块读取索引的所有叶子页，不保证顺序
PG	❌	无等效操作
MySQL	❌	无等效操作

Oracle 的 INDEX FAST FULL SCAN 读取索引段的所有数据块（使用多块 I/O），但不像 INDEX FULL SCAN 那样按索引顺序读取。适用于 SELECT COUNT(*) 等不需要排序的聚合查询。

PG 和 MySQL 没有直接等效的操作。在 PG 中，类似场景会使用 Index-Only Scan（顺序读取）或全表扫描。

3.5 仅索引扫描（Index-Only Scan）

PG 的 Index-Only Scan：

PG 可以从索引直接返回数据而完全不访问堆表——前提是：

查询所需的列全部在索引中；
索引覆盖的堆表页面在 visibility map 中标记为"全可见"。

如果某个页面有未对所有事务可见的行版本，PG 仍需访问堆表检查可见性。

MySQL 的覆盖索引：

MySQL 的覆盖索引概念类似——如果查询列在二级索引中，直接从二级索引返回。因为二级索引叶子存了主键值，所以 SELECT id, indexed_col FROM t WHERE indexed_col = ? 天然覆盖。

Oracle：

Oracle 堆表没有真正的 Index-Only Scan——即使查询列全在索引中，由于索引叶子存的是 ROWID，要取出实际数据仍需回表。IOT 的二级索引可以在某些场景下实现"不回表"的效果（叶子存逻辑 ROWID + 主键值）。

四、页面空间回收：删除后的"坑"

索引中删除了大量数据后，空间能否被回收利用？三库差异显著。

4.1 Oracle：空间可重用但页不归还

Oracle 索引中删除行后，该行占用的空间标记为可用，后续插入可重用。但整个索引段不会收缩——即使删除了 90% 的数据，索引段的大小不变。需要手动 ALTER INDEX ... REBUILD 或 SHRINK SPACE。

-- Oracle 重建索引以回收空间
ALTER INDEX idx_orders_date REBUILD ONLINE;

4.2 PG：VACUUM 回收空间

PG 的索引空间回收依赖 VACUUM 操作。DELETE 后，索引中留下死元组指针。VACUUM 会清理这些指针并回收空间。但频繁 VACUUM 本身有 I/O 开销。

-- PG 重建索引以回收空间
REINDEX INDEX idx_orders_date;

4.3 MySQL InnoDB：MERGE_THRESHOLD

InnoDB 使用 MERGE_THRESHOLD 参数（默认 50%）控制页的合并行为。当一个索引页的填充率低于 50% 时，InnoDB 会尝试与相邻页合并。

-- 查看当前 MERGE_THRESHOLD（MySQL 8.0 可通过 innodb_merge_threshold_set_all_debug 在 debug 版本中查看）
-- 为单个索引设置 MERGE_THRESHOLD
ALTER TABLE orders ADD INDEX idx_status (status) COMMENT 'MERGE_THRESHOLD=40';

注意：MERGE_THRESHOLD 是索引级别参数，只能在创建索引时通过 COMMENT 子句设置，无法通过 SET GLOBAL 修改全局默认值，也无法对已有索引在线修改。

五、总结

三库的 B+Tree 实现虽然遵循同一理论模型，但工程细节的分歧在生产环境中会被放大：

机制	Oracle	PostgreSQL	MySQL InnoDB
页大小	8KB（可选）	8KB（编译时定）	16KB（可选）
预留空间	PCTFREE（默认10）	fillfactor（默认90）	MERGE_THRESHOLD（合并阈值）
跳跃扫描	✅	❌	❌
快速全扫描	✅	❌	❌
仅索引扫描	受限（非IOT）	✅ Index-Only Scan	✅ 覆盖索引
空间回收	REBUILD	VACUUM / REINDEX	自动合并（MERGE_THRESHOLD）

实战建议

Oracle DBA：关注 PCTFREE 设置、定期监控索引碎片化、善用跳跃扫描和快速全扫描；
PG DBA：关注 fillfactor 对 UPDATE 密集型表的影响、定期 CLUSTER 或 pg_repack、利用 Index-Only Scan；
MySQL DBA：主键设计是索引性能的基石——自增 BIGINT 是 99% 场景的最优解、善用覆盖索引避免回表、对 UUID 主键保持警惕。