B-Tree 和 B+Tree 的区别是什么？以及 MySQL 和 PostgreSQL 相关的区别。
这是数据库索引领域的经典必考题，而且这是一个 “对比型 + 落地型” 的问题。
分三层来讲：
- B-Tree vs B+Tree 本质区别
- MySQL（InnoDB）怎么用
- PostgreSQL 怎么用
- 为什么两个数据库做了不同选择（工程原因）
以下尽量用工程视角而不是教科书视角说明。
B+Tree 是为了数据库而生的 B-Tree 变种
- 非叶子节点 + 叶子节点
- 👉 都存 key + value
- 查到中间节点就可能结束
- 叶子节点 不一定链表
[10|20]
/ | \
[1..9] [10..19] [20..30]
- 非叶子节点：只存 key + child pointer
- 叶子节点：存 key + value
- 所有 value 都在叶子节点
- 叶子节点形成有序链表
[10|20]
/ | \
/ | \
[1..9] <-> [10..19] <-> [20..30]
| 对比项 | B-Tree | B+Tree |
|---|---|---|
| 数据存储位置 | 所有节点 | 只在叶子节点 |
| 中间节点是否存数据 | 是 | 否 |
| 查询是否可能提前结束 | 是 | 否 |
| 范围查询 | 差 | 非常好 |
| 顺序遍历 | 不友好 | 极其高效 |
| 节点扇出（fanout） | 较小 | 更大 |
| IO 次数 | 偏多 | 更少 |
数据库 90% 的查询是：
- 范围查询
- 排序
- 分页
- 扫描
- >=, <=, BETWEEN, ORDER BY
👉 B+Tree 天生为这些而生
InnoDB = 全面 B+Tree
- 主键索引
- 叶子节点 = 整行数据
- 表数据就是索引
PRIMARY KEY B+Tree
叶子节点 = 行数据
- 叶子节点存：二级索引 key + 主键
- 查二级索引 -> 再回主键索引（回表）
secondary index
叶子节点 = (idx_key, primary_key)
- 固定 16KB page
- 高 fanout
- 极少树高（一般 2～4 层）
- 顺序扫描极快
- 范围查询多
- 聚簇索引减少一次 IO
- 适合磁盘顺序读
- 页级缓存友好
PostgreSQL 的设计思想和 InnoDB 完全不同。
- PostgreSQL 的 btree 是 B+Tree 变体
- 索引中不存行数据
- 叶子节点存：
key + TID（tuple id）
👉 TID 指向 Heap Table
Index (B+Tree)
↓
Heap Table (真正的数据)
特点
- 表是堆结构（无序）
- 索引只做“指针导航”
- 更新时不移动索引结构
核心原因：MVCC
- 每次 UPDATE = 新行
- 老行保留（直到 VACUUM）
- 如果是聚簇索引：
- 行频繁移动
- 索引维护成本巨大
👉 所以 PostgreSQL 选择 索引 & 数据分离
CLUSTER table_name USING index_name;
- 只在当前时刻按索引顺序重排
- 后续 UPDATE 会破坏顺序
PostgreSQL 更偏向：
- 多索引类型
- 不执着于 B+Tree 一把梭
| 对比项 | MySQL InnoDB | PostgreSQL |
|---|---|---|
| 索引类型 | B+Tree 为核心 | B-Tree 为主，多类型 |
| 聚簇索引 | 必须有 | ❌ |
| 数据存储 | 在主键索引叶子 | Heap |
| 二级索引 | 存主键 | 存 TID |
| UPDATE 代价 | 改索引 | 写新行 |
| MVCC | undo log | tuple version |
| 顺序扫描 | 非常快 | 依赖 VACUUM |
| OLTP | 强 | 强 |
| 扩展能力 | 中 | 非常强 |
B+Tree 把数据集中在叶子节点，并通过链表连接叶子节点，使范围查询和顺序扫描效率极高，因此成为数据库索引的事实标准。
InnoDB 使用聚簇 B+Tree，将数据和主键索引绑定以减少 IO；PostgreSQL 使用堆表 + B-Tree 索引，更好地支持 MVCC 和复杂更新场景。