B+ 树索引：从磁盘到内存

几乎每个数据库入门者都问过同一个问题：**为什么索引是 B+ 树而不是红黑树？**答案藏在磁盘的物理特性里。

核心约束：一次 I/O 读一个页

磁盘随机读的延迟（约 10ms 级）比内存访问（纳秒级）慢 6~7 个数量级。数据库把数据组织成页，一次磁盘 I/O 只能读入一页。因此，索引的目标从「比较次数少」变成了「树的高度矮」——每多一层，就多一次磁盘 I/O。

高度为 3 的 B+ 树，存储 10 亿条记录：

  层0: 1 个根节点（页）
  层1: ~1000 个内部节点（页）
  层2: ~1000*1000 个叶子节点（页）
  → 任意点查询最多 3 次磁盘 I/O

为什么能做到这么矮？因为一个页可以容纳几百个键（假设键 8 字节 + 指针 8 字节，8KB 页能装约 500 个），B+ 树的扇出（fan-out）远超二叉树。

B+ 树 vs 其他结构

结构	树高（1e9 条）	范围查询	写放大	用途
二叉搜索树/红黑树	~30	差	无	内存结构
B 树	3~4	中	低	老系统（部分）
B+ 树	3~4	优	低	主流关系库
LSM-Tree	3~5	中	高	写密集系统

B+ 树的两个关键设计：

1. 数据只在叶子：内部节点只存键与指针，扇出更大
2. 叶子链表串联：范围查询从起点顺着链表扫，无需回溯

节点分裂：插入的代价

B+ 树插入时，节点满了就分裂成两个，并把中间键上提到父节点：

插入前 [10 20 30 40]（满，容量 4）
插入 25 → 节点溢出
分裂为 [10 20] 和 [30 40 25]... 
         ↓
父节点获得新键 30

分裂是 B+ 树唯一比较昂贵的操作，但分摊下来每个插入的代价仍是 O(log n)。

页缓存与预读

光有 B+ 树还不够，数据库用缓冲池让热节点留在内存：

• 根节点和上层内部节点几乎总是热的 → 实际 I/O 往往只有叶子层一次
• 顺序扫描时预读（Read Ahead）把相邻页批量载入 → 把随机 I/O 变顺序 I/O

💡 经验： 索引设计要「小而热」。宽索引（多列、长字符串）会降低扇出、抬高树高、撑大缓冲池占用——这是慢查询最常见的原因之一。

聚簇索引：数据就是叶子

MySQL InnoDB 的主键索引是聚簇索引：叶子节点直接存放整行数据。这意味着：

• 按主键查询：索引即数据，一次 I/O 拿到行
• 二级索引：叶子存放主键值，查询需要「回表」再走一次主键索引

聚簇索引叶子: [主键 | 完整行数据]
二级索引叶子: [索引列 | 主键值] → 回表

设计主键时优先选择单调递增的短主键：避免页分裂、缩小二级索引体积。

小结

B+ 树不是最聪明的数据结构，却是最懂磁盘的数据结构：用高扇出换树高，用叶子链表换范围查询，用缓冲池换热路径。理解了「页」这个单位，B+ 树的一切设计都顺理成章。