为什么数据库普遍选择 B+ Tree#

如果只从算法课本看，查找一个有序集合有很多选择：数组可以二分，哈希表可以做到平均 O(1)，红黑树、AVL 树可以做到 O(logN)。但数据库的核心问题不是“CPU 内存里怎么找”，而是“磁盘或 SSD 上的数据怎么少读几次”。

MySQL 的 InnoDB 存储引擎把表数据和索引组织成页。默认情况下，一个页通常是 16KB。一次查询如果每深入一层索引就需要读取一个页，那么树的高度越低，I/O 次数就越少。B+ Tree 的核心优势就在这里：

  1. 每个节点能存放很多 key，树的分叉数很大，高度很低。
  2. 所有真实记录都在叶子节点，非叶子节点只负责导航。
  3. 叶子节点之间按 key 顺序连接，非常适合范围查询和排序扫描。
  4. 节点大小天然适合数据库页，可以和磁盘读写单位对齐。

所以，B+ Tree 不是为了在理论复杂度上压倒所有结构，而是为了适配数据库最昂贵的资源：随机 I/O。

从二叉树到 B+ Tree#

普通二叉搜索树每个节点最多两个孩子。即使它保持平衡，一千万条数据的高度也大约是二十多层。放在内存里问题不大，放在数据库里就意味着一次查找可能触发很多次随机页读取。

B Tree 和 B+ Tree 解决的是“分叉太少”的问题。一个节点可以保存多个 key 和多个孩子指针。例如节点中有这些分隔 key：

[10 | 20 | 30]

它可以把搜索空间分成四段：

(-∞, 10)   [10, 20)   [20, 30)   [30, +∞)

这样，一个节点不是二选一，而是多路分发。只要一个页中能放下足够多的 key 和指针，树的高度就会非常低。

B+ Tree 相比 B Tree 又进一步做了一个重要取舍：非叶子节点不存放完整数据记录，只存放用于导航的 key 和子节点页号；所有完整记录都放在叶子节点。这样非叶子节点更小，能容纳更多 key，树也就更矮。

B+ Tree 的基本结构#

一棵典型 B+ Tree 可以分成三类节点：

  1. 根节点：树的入口。数据量很小时，根节点也可能同时是叶子节点。
  2. 内部节点：只保存索引 key 和子节点指针，用来决定下一步走向哪个页。
  3. 叶子节点：保存最终记录，或者保存指向最终记录的引用。

更贴近数据库页的示意是：

Root Page
  keys: 30, 60
  children: page_12, page_28, page_41

Internal Page page_12
  keys: 10, 20
  children: page_101, page_102, page_103

Leaf Page page_101
  records: 1, 2, 3, 4, 5, 6, 7, 8, 9
  next: page_102

叶子页之间有顺序链表。这个设计让范围查询很高效：先通过树定位到范围起点所在的叶子页，然后沿着叶子页的 next 指针顺序扫描即可。

阶、分叉数和树高#

很多资料会用“阶”来描述 B+ Tree。简单理解，一个 m 阶 B+ Tree 的内部节点最多可以有 m 个孩子，最多有 m - 1 个 key。实际数据库实现不会只用抽象的“阶”，而是由页大小、key 大小、页头、槽目录、记录头、指针大小等共同决定一个页能容纳多少条索引项。

假设一个内部页能容纳 1000 个分支，那么树高会非常低：

高度 1：根节点就是叶子页，可容纳若干条记录
高度 2：根节点指向约 1000 个叶子页
高度 3：约 1000 * 1000 个叶子页
高度 4：约 1000 * 1000 * 1000 个叶子页

即使实际分叉数没有这么夸张，B+ Tree 在大表上通常也只有 3 到 4 层。根页和上层内部页还很容易被缓存在 Buffer Pool 中，真正落到磁盘的随机读取次数通常更少。

查找算法#

B+ Tree 的查找过程可以概括为：从根节点开始，在当前节点内找到 key 应该落入的区间，然后进入对应子节点，直到叶子节点为止。

search(tree, key):
    page = tree.root

    while page is not leaf:
        i = upper_bound(page.keys, key)
        page = read_page(page.children[i])

    return find_record_in_leaf(page, key)

这里的 upper_bound 表示找到第一个大于目标 key 的位置。内部节点中的 key 是分隔符，不一定代表完整记录。真正的数据查找必须落到叶子节点。

在单个页内部，数据库并不是逐条线性扫描所有记录。InnoDB 页内有页目录，可以先在槽目录上二分，再在小范围内顺序比较，从而减少页内查找成本。

范围查询为什么快#

范围查询是 B+ Tree 相比哈希索引的核心优势之一。假设执行：

SELECT * FROM orders
WHERE user_id BETWEEN 1000 AND 2000
ORDER BY user_id;

如果 user_id 上有 B+ Tree 索引，执行过程大致是：

  1. 从根节点开始定位 user_id >= 1000 的第一条记录。
  2. 到达叶子页后，从这个位置开始顺序读取。
  3. 沿着叶子页链表继续向后扫描。
  4. 当遇到 user_id > 2000 时停止。
range_scan(tree, left, right):
    leaf, pos = lower_bound_leaf(tree, left)

    while leaf is not null:
        while pos < leaf.record_count:
            record = leaf.records[pos]
            if record.key > right:
                return
            output(record)
            pos = pos + 1

        leaf = read_page(leaf.next)
        pos = 0

这类访问模式对磁盘和缓存都更友好，因为它把大量随机访问转化为顺序访问。尤其在 InnoDB 中，叶子页按 key 有序，范围扫描、前缀匹配、排序、分组都可以从这个特性中受益。

插入算法：定位、插入、分裂#

B+ Tree 插入一条记录时，首先像查找一样定位到目标叶子页。然后分两种情况：

  1. 叶子页还有空间：直接插入到有序位置。
  2. 叶子页空间不足：先分裂页，再把分隔 key 提升到父节点。
insert(tree, key, value):
    leaf = find_leaf(tree.root, key)

    if leaf has space:
        insert_into_leaf_in_order(leaf, key, value)
        write_page(leaf)
        return

    new_leaf = split_leaf(leaf)
    move_half_records(leaf, new_leaf)
    fix_leaf_links(leaf, new_leaf)

    separator = first_key(new_leaf)
    insert_into_parent(tree, leaf, separator, new_leaf)

叶子页分裂时，通常会把一部分记录移动到新页，并维护叶子页链表：

分裂前：
leaf_A -> leaf_C

分裂后：
leaf_A -> leaf_B -> leaf_C

然后父节点需要新增一个分隔 key，指向新页。如果父节点也满了，就继续向上分裂。最极端的情况是根节点也分裂，此时树高增加一层。

这也是为什么随机插入比顺序插入更容易造成页分裂。对于 InnoDB 聚簇索引来说，如果主键是递增的，新的记录大多追加到最右侧叶子页；如果主键是完全随机的，插入位置会分散到整棵树的各个叶子页，更容易触发页分裂、页碎片和缓存抖动。

删除算法：删除、借位、合并#

删除记录时，同样先定位到叶子页，再删除目标记录。删除之后，如果页内记录仍然足够多，操作就结束。如果页利用率过低，B+ Tree 需要尝试保持平衡，常见处理有两种：

  1. 向相邻兄弟节点借一部分记录。
  2. 和相邻兄弟节点合并，并删除父节点中的分隔 key。
delete(tree, key):
    leaf = find_leaf(tree.root, key)
    remove_record(leaf, key)

    if leaf is still sufficiently full:
        write_page(leaf)
        return

    sibling = choose_sibling(leaf)

    if sibling can lend record:
        redistribute(leaf, sibling)
        update_parent_separator()
    else:
        merge(leaf, sibling)
        remove_separator_from_parent()

如果父节点删除分隔 key 后也低于最低填充要求，合并可能继续向上传播。若根节点最后只剩一个孩子，树高还可以下降一层。

需要注意，数据库系统的实现会比教材算法更复杂。比如 InnoDB 不一定在每次删除后立刻做完全合并，还会考虑事务、锁、MVCC、页重组、后台 purge 等因素。教材 B+ Tree 讲的是结构约束，数据库 B+ Tree 还要处理并发和恢复。

MySQL InnoDB 中的聚簇索引#

InnoDB 表本身就是按照主键组织的一棵 B+ Tree，这棵树叫聚簇索引。聚簇索引的叶子节点保存完整行记录。

CREATE TABLE user_account (
  id BIGINT PRIMARY KEY,
  name VARCHAR(64),
  email VARCHAR(128),
  created_at DATETIME
) ENGINE=InnoDB;

这张表的数据会按 id 的顺序组织在聚簇索引的叶子页中。查询主键时：

SELECT * FROM user_account WHERE id = 10086;

执行路径大致是：

根页 -> 内部页 -> 叶子页 -> 完整行记录

因为叶子页已经包含完整行，所以主键查询通常非常高效。

如果表没有显式主键，InnoDB 会选择一个非空唯一索引作为聚簇索引；如果也没有合适的唯一索引，会生成隐藏的行 ID。实践中不建议依赖隐藏行 ID，最好为每张 InnoDB 表设计明确、稳定、尽量短的主键。

二级索引与回表#

除了聚簇索引，其他索引都叫二级索引。二级索引也是 B+ Tree，但它的叶子节点不保存完整行，而是保存二级索引 key 和对应的主键值。

CREATE INDEX idx_email ON user_account(email);

执行：

SELECT * FROM user_account WHERE email = 'a@example.com';

流程通常是：

  1. 在 idx_email 这棵 B+ Tree 中查找 email = 'a@example.com'。
  2. 在二级索引叶子节点拿到对应的主键 id。
  3. 再回到聚簇索引中，用 id 查完整行。

这第三步就是常说的“回表”。

二级索引 idx_email
email -> id

聚簇索引 PRIMARY
id -> full row

如果查询的列都在二级索引中，就不需要回表，这叫覆盖索引。例如：

SELECT id, email
FROM user_account
WHERE email = 'a@example.com';

因为二级索引叶子节点本来就包含 email 和主键 id，这条查询可以直接在二级索引中完成。

联合索引与最左前缀#

B+ Tree 的 key 可以由多个列组成，这就是联合索引：

CREATE INDEX idx_user_status_time
ON orders(user_id, status, created_at);

这棵 B+ Tree 的排序规则不是分别对三个列排序，而是按组合 key 排序：

(user_id, status, created_at)

比较时先比 user_id，相同再比 status，再相同才比 created_at。因此它适合这些条件：

WHERE user_id = 1

WHERE user_id = 1 AND status = 'PAID'

WHERE user_id = 1 AND status = 'PAID'
  AND created_at BETWEEN '2026-01-01' AND '2026-01-31'

但不适合只按后面的列直接定位：

WHERE status = 'PAID'

原因是同一个 status 的值在整棵树里不是连续的一段，而是散落在不同 user_id 下。所谓最左前缀原则，本质上就是 B+ Tree 的组合 key 排序规则决定的。

为什么范围条件后面的列常常用不上#

考虑这个索引：

CREATE INDEX idx_a_b_c ON t(a, b, c);

如果查询是：

WHERE a = 1 AND b > 10 AND c = 5

B+ Tree 可以先定位 a = 1 的区间，再在其中定位 b > 10 的起点。但一旦 b 是范围条件，后面的 c 就无法继续作为同一级别的精确定位条件。

原因是索引顺序是：

(a, b, c)

在 a = 1 AND b > 10 的范围里，c = 5 并不是一个整体连续区间。优化器可能仍然会用索引条件下推等方式减少回表，但不能像 a = 1 AND b = 10 AND c = 5 那样直接定位到非常窄的范围。

这也是设计联合索引时经常把等值条件列放前、范围条件列放后的原因之一。

页分裂、页合并和主键设计#

B+ Tree 的维护成本主要体现在写入路径上。查询只需要沿树向下和顺序扫描，插入、删除、更新则可能引发页分裂、页合并、父节点调整以及日志写入。

在 InnoDB 中，主键设计会直接影响聚簇索引的形态：

  1. 主键越短，二级索引越小。因为二级索引叶子节点保存的是主键值。
  2. 主键越稳定，行移动和索引维护成本越低。
  3. 主键越接近递增，聚簇索引插入越容易追加到右侧，页分裂相对少。
  4. 完全随机的主键会让插入分散到不同叶子页，增加随机 I/O 和页碎片风险。

这并不是说所有表都必须使用自增 ID。业务唯一键、雪花 ID、UUID、ULID 都有各自的取舍。关键是要理解：主键不是只影响一列约束，它决定了整张 InnoDB 表的物理组织方式。

如果使用 UUID，建议评估 UUIDv7、ULID 或类似具备时间有序性的方案，而不是完全随机的 UUIDv4。这样可以在全局唯一和索引局部性之间取得更好的平衡。

B+ Tree 与哈希索引的区别#

哈希索引适合等值查询：

WHERE id = 123

但它天然不适合范围查询：

WHERE id BETWEEN 100 AND 200

因为哈希函数会打散原始顺序。相邻的 key 经过哈希后不再相邻，所以无法顺序扫描。

能力B+ Tree哈希索引
等值查询支持支持，通常很快
范围查询支持不适合
排序可利用索引顺序不支持
前缀匹配联合索引可支持不适合
数据库通用性高场景较窄

MySQL InnoDB 的常规索引主要使用 B+ Tree，原因就是数据库查询并不只有等值查询，还包含范围、排序、分组、分页和前缀匹配。

B+ Tree 与 LSM Tree 的取舍#

现代存储系统里还有一种常见结构：LSM Tree。它常见于 RocksDB、LevelDB、一些 NoSQL 系统以及 MySQL 的 MyRocks 引擎。

B+ Tree 更偏向原地更新：

找到目标页 -> 修改页 -> 写日志 -> 刷脏页

LSM Tree 更偏向追加写：

写入内存表 -> 顺序写 WAL -> 后台合并多层文件
维度B+ TreeLSM Tree
点查稳定，路径短可能查多层，需要 Bloom Filter 辅助
范围扫描很自然可以支持，但要合并多层有序数据
写入随机写和页分裂成本较高追加写友好，写吞吐高
空间放大通常较低后台 compaction 可能带来空间放大
读放大通常较低可能较高

InnoDB 选择 B+ Tree，是因为它需要在 OLTP 场景下平衡点查、范围查询、事务、锁、恢复、二级索引和 SQL 优化器的通用需求。

一个完整查询例子#

假设有订单表：

CREATE TABLE orders (
  id BIGINT PRIMARY KEY,
  user_id BIGINT NOT NULL,
  status VARCHAR(20) NOT NULL,
  amount DECIMAL(10, 2) NOT NULL,
  created_at DATETIME NOT NULL,
  INDEX idx_user_status_time(user_id, status, created_at)
) ENGINE=InnoDB;

查询某个用户最近已支付订单：

SELECT id, amount, created_at
FROM orders
WHERE user_id = 1001
  AND status = 'PAID'
  AND created_at >= '2026-04-01'
ORDER BY created_at DESC
LIMIT 20;

如果优化器选择 idx_user_status_time，执行逻辑大致是：

  1. 在联合索引中定位 (1001, 'PAID', '2026-04-01') 附近的位置。
  2. 沿索引叶子页扫描满足条件的记录。
  3. 从二级索引叶子节点拿到主键 id。
  4. 如果 amount 不在索引中，需要回表到聚簇索引取完整行。
  5. 如果扫描方向和 ORDER BY created_at DESC 匹配，可以减少额外排序。

如果希望减少回表，可以考虑把查询需要的列加入索引：

CREATE INDEX idx_user_status_time_amount
ON orders(user_id, status, created_at, amount);

这会让查询更可能变成覆盖索引。但索引不是越多越好。每增加一个索引，写入时就多维护一棵 B+ Tree，磁盘空间也会增加。设计索引本质上是在读性能、写成本和空间成本之间做权衡。

B+ Tree 的核心不变量#

无论实现细节如何变化，B+ Tree 有几个关键不变量：

  1. 所有叶子节点在同一层，因此从根到任意叶子的路径长度相同。
  2. 节点内 key 有序。
  3. 内部节点的 key 用来划分子树范围。
  4. 叶子节点保存完整数据或数据引用。
  5. 叶子节点之间按 key 顺序连接。
  6. 插入和删除后，树会通过分裂、借位、合并等动作维持平衡。

这些不变量保证了 B+ Tree 的查询复杂度稳定，也保证了范围扫描可以沿叶子链表高效进行。

实践中的索引设计建议#

理解 B+ Tree 之后，很多 MySQL 索引经验就不再只是口诀：

  1. 高选择性的列更适合放在索引前面，但要结合查询模式，而不是机械套用。
  2. 联合索引遵循组合 key 的排序规则，最左前缀来自这个物理事实。
  3. 范围条件会改变后续列的可利用方式，设计索引时要注意等值列和范围列顺序。
  4. 二级索引叶子节点包含主键，主键过大会放大所有二级索引。
  5. 覆盖索引能减少回表，但会增加索引体积和写入维护成本。
  6. 随机主键可能带来更多页分裂和缓存不稳定，递增或近似递增主键通常更友好。
  7. LIKE 'abc%' 可以利用 B+ Tree 的有序性，LIKE '%abc' 通常无法有效利用普通 B+ Tree 索引。
  8. 不要为每个查询都盲目加索引，应通过 EXPLAIN、慢查询日志和真实数据分布验证。

总结#

B+ Tree 是数据库索引的经典结构，因为它不是单纯追求理论上的查找速度，而是围绕数据库真实瓶颈设计：页、缓存、磁盘 I/O、范围扫描和有序访问。

在 MySQL InnoDB 中，聚簇索引决定了表数据的物理组织方式，二级索引通过保存主键来间接定位完整行。一次 SQL 查询是否高效，往往取决于它能否顺着 B+ Tree 的有序结构少读页、少回表、少排序、少扫描。

把 B+ Tree 理解清楚后，很多看似零散的 MySQL 规则都会串起来：为什么有最左前缀，为什么范围条件后面的列可能用不上，为什么主键不宜太大，为什么覆盖索引能减少回表，为什么随机主键会影响写入。索引设计的本质，就是让查询条件尽可能贴合 B+ Tree 的排序方式，同时控制写入和空间成本。