第2章 B-Tree 与页管理

第2章 · B-Tree 与页管理

章节摘要：第 1 章读完了文件的头，本章走进 4096 字节的内部。我们给出 SQLite 五种页面的完整清单，拆解 B-Tree 页从页头、单元格指针数组到内容区的物理布局；然后用一道可以手算的题回答"三层树能装多少行"；最后把 SQLite、InnoDB、PostgreSQL 三种行存储布局并排对照，看清"行存进树里"与"树挂在堆上"这两条路线的全部差异。本章是全册技术密度最高的一章，每个数字都可以在真实文件上验证。

学习目标

读完本章，你应当能够：

1. 说出五种 B-Tree 页类型（表内部页、表叶子页、索引内部页、索引叶子页、空闲页）各自的页类型码与职责。
2. 画出 4096 字节 B-Tree 页的内部布局：8 或 12 字节页头、单元格指针数组、从页尾向下生长的内容区、自由块链表。
3. 给定行宽与页大小，手工估算一棵三层 B+ 树能容纳的行数，并解释这个估算如何指导分区与归档决策。
4. 解释页分裂的触发条件与"先尝试页内整理"的优化路径，知道碎片率怎么变成查询性能。
5. 对照说出 SQLite 的"表即 B-Tree"、InnoDB 的聚簇索引、PostgreSQL 的堆表加索引三种行存路线在写入、点查、范围扫描上的表现差异。

核心概念速览

一句金句：在 SQLite 里，"一行数据存在哪"这个问题有且只有一个答案——某个 B-Tree 叶子页的某个单元格；理解了单元格怎么排布，性能问题就从玄学变成了算术。

子章节导航

2.1 页面类型与布局：用一张真实文件的字节图拆开 B-Tree 页：页头各字段的含义、单元格指针数组为什么从前往后长、内容区为什么从页尾向下长、自由块链表怎么串起页内碎片，以及溢出页链在什么情况下拖慢读取。

2.2 B树阶数与层数手算：给出行宽与页大小，完整演算叶子页容量、内部页扇出、三层树的行数上限；再用这个模型解释为什么"几千行的表不需要索引调优，千万行的表索引差一层就是灾难"，以及删除为什么不会让文件变小。

2.3 三库存储引擎对照：同一个员工表分别按 SQLite、InnoDB、PostgreSQL 的方式落盘，对照三种布局在点查、范围扫描、写入放大、二级索引回表上的差异，并给出行之有效的主键选型三步法。

子章节之间的逻辑关系

三节是"静态布局 → 数学模型 → 横向对照"的递进。2.1 给出页的物理事实，2.2 把事实升级成可推理的模型——有了扇出与层高，你能在建表阶段预判索引形态；2.3 再把模型放进三个引擎的坐标系，解释为什么同一张表在三个引擎里文件大小、点查速度、写入吞吐各不相同。先掌握自己的布局，再看别人的布局，对照才有意义：

2.1 页的物理布局 ──▶ 2.2 扇出与层高模型 ──▶ 2.3 三库路线对照
      事实                推理                 坐标系
                          │
                          ▼
              第4章：页在事务日志里的另一种形态
​

前置知识与后续延伸

前置：第 1 章的页概念与文件头字段；知道主键与 rowid 的关系（1.1 提到 INTEGER PRIMARY KEY 即 rowid 别名）。

后续延伸：本章的页视角在第 4 章获得时间维度——回滚日志与 WAL 记录的正是"页的旧版本"，理解了页布局才能理解日志为什么按帧组织。第 5 章的索引优化同理：选择性、覆盖索引这些概念全部落在"索引 B-Tree 的叶子页里有什么"这个事实上。读 2.3 时可以带着问题：为什么 PostgreSQL 没有聚簇索引仍然很快？