Luke a Pro

Luke Sun

Developer & Marketer

🇺🇦
EN|简|繁
© 2015–2026 Luke Sun.
All rights reserved.

第一章：B-Tree 与 B+Tree — 索引的数学骨架

Published: Thu Feb 05 2026 | Modified: Fri Feb 06 2026 , 2 minutes reading.

1. 定义

B-Tree（平衡多路查找树）是一种自平衡的树数据结构，它维护有序数据并允许以对数时间进行搜索、顺序访问、插入和删除。它由 Rudolf Bayer 和 Edward M. McCreight 于 1972 年定义。

B+Tree 是 B-Tree 的变体，其特点是：

  1. 非叶子节点不存储数据：仅存储键（Key）作为索引。
  2. 叶子节点链表化：所有数据均存储在叶子节点，且叶子节点之间相互链接（常见为单向或双向）。

2. 技术深度：为什么是 B+Tree 而不是二叉树？

数据库索引之所以不使用红黑树或 AVL 树，核心原因在于减少磁盘 I/O 次数。

A. 扇出 (Fan-out) 与树的高度

在磁盘中，数据是以 Page (页) 为单位读取的（InnoDB 默认为 16KB）。

  • 二叉树：每个节点只有 2 个子节点，树的高度 $H$ 约为 $\log_2 N$。对于 1000 万行数据，高度约 24 层，意味着最坏情况需要 24 次磁盘 I/O。
  • B+Tree：通过增大扇出（例如每个节点存储 100 个键），树的高度 $H$ 大幅降低。同样 1000 万行数据，高度仅需 3-4 层。

B. B+Tree 的磁盘预读优势

由于 B+Tree 的非叶子节点不存数据，一个 Page 可以容纳更多的键（Key），从而进一步提高扇出。同时，叶子节点的链表结构使得**范围查询（Range Scan）**无需回溯父节点，直接在叶子层水平移动即可。

3. 可视化：Page 分裂 (Page Split) 过程

当一个 Page 已满（达到填充因子限额）且有新数据插入时，数据库会触发一次“不可见”的底层操作：Page Split。

sequenceDiagram
    participant App as 插入请求
    participant Buffer as Buffer Pool (内存)
    participant PageA as Page 101 (已满)
    participant PageB as Page 102 (新申请)

    App->>Buffer: 插入键 50
    Buffer->>PageA: 尝试写入
    Note over PageA: 数据溢出 (Overflow)
    
    Buffer->>PageB: 申请新空页
    PageA->>PageB: 迁移一部分记录 (如键 30-49)
    Note over PageA,PageB: 重新平衡节点
    
    Buffer-->>Buffer: 更新父节点索引指针
    Note over Buffer: 磁盘 I/O 放大开始

4. 真实案例：Instagram 的 ID 生成策略 (2011)

背景：2011 年，Instagram 工程团队在设计其媒体 ID 生成系统时，需要一种能够跨分片（Shard）唯一且高性能的方案。

技术选型：他们最初考虑了 UUID (Universally Unique Identifier)。 拒绝理由：

  1. 索引大小：UUID 是 128 位的，而 bigint 只有 64 位。对于拥有数十亿条记录的表，索引会变得极其臃肿，难以全部装入内存。
  2. B+Tree 性能噩梦：UUID 是完全随机的。在 B+Tree 索引中，这会导致数据被随机插入到不同的 Page 中。由于 Page 频繁分裂（Page Split），磁盘物理存储变得极其不连续，且每个 Page 的填充率（Fill Factor）极低。这引发了大量的随机磁盘 I/O，严重拖慢了写入速度并挤壓了 Buffer Pool 空間。

最终方案：Instagram 参考了 Twitter 的 Snowflake 算法，设计了一种包含 时间戳前缀 的 64 位逻辑 ID。

  • 优势：由于 ID 是趋势递增的，新记录大多追加到 B+Tree 的右侧叶子节点。这避免了中间节点的频繁随机分裂，通常能维持较高的 Page 填充率（取决于具体的分裂策略），并显著提升了缓存命中率与写入局部性 (Write Locality)。

教訓：在高性能数据库设计中，索引列的顺序性往往比唯一性更具挑战。高质量的架构师会通过牺牲一定的随机性来换取 B+Tree 的物理连续性。

5. 深度优化与纵深防御

A. 根本修复：选择合适的聚簇索引 (Clustered Index)

  • 优先使用自增 ID 或趋势递增的键作为聚簇索引。
  • 对于非递增键，考虑降低 FILLFACTOR（填充因子，Postgres 术语）或 innodb_fill_factor（MySQL，依版本/场景生效），为随机插入预留空间，减少分裂。

B. 纵深防御：索引覆盖 (Covering Index)

  • 通过将常用查询字段放入二级索引，避免“回表查询”，降低额外 I/O 成本，但 B+Tree 查找仍为 $\log N$ 级别。

C. 碎片清理

  • 定期执行 OPTIMIZE TABLE (MySQL) 或 REINDEX (Postgres) 以回收物理碎片，重新平衡树结构。

6. 参考资料