一文详解为什么MySQL选择使用B+树作为索引结构_Mysql

面试考点分析：

数据结构对比能力：考察是否理解 b 树、b+ 树、哈希、二叉搜索树等常见数据结构的特性与差异。
磁盘 io 与存储原理：考察对磁盘预读、局部性原理、页式存储管理的理解深度。
范围查询优化：考察是否了解 b+ 树叶子节点链表在范围查询中的核心优势。
工程权衡思维：考察对 mysql 作为关系型数据库在一致性和持久性方面的设计取舍的理解。
索引下推与覆盖索引：考察能否将 b+ 树特性与高阶 sql 优化手段结合分析。

一、标准回答

mysql 选择 b+ 树作为索引结构的根本原因在于：b+ 树能够在保持良好平衡性的前提下，最大限度减少磁盘 io 次数，同时完美支持高效的范围查询。

具体而言，b+ 树作为一种多路平衡搜索树，其非叶子节点仅存储键值而不存储数据，使得单个节点可以容纳更多的索引键。这意味着在相同的数据量下，b+ 树的高度远低于二叉搜索树或红黑树，从而将磁盘 io 次数压缩到最低。此外，b+ 树的所有数据都存储在叶子节点中，叶子节点之间通过双向指针连接，形成一个有序链表。这一设计在数据库领域尤为关键：它使得基于索引的范围查询（如 between、>、<、order by）无需反复回溯父节点，只需定位到起始节点后沿链表顺序扫描即可完成。

相比之下，哈希索引虽在等值查询上做到 o(1)，但无法处理范围查询；b 树虽也支持范围查询，但其数据分散在所有节点中，范围扫描时需要在不同层级的节点间跳跃，磁盘 io 远高于 b+ 树。因此，b+ 树在查询效率、范围扫描和空间利用率三个维度上达成了最优平衡，成为 mysql innodb 引擎的默认索引结构。

二、核心原理

2.1 磁盘 io 与局部性原理

计算机的存储体系呈现典型的金字塔结构：cpu 缓存 → 内存 → 磁盘。mysql 的数据最终持久化在磁盘上，而磁盘的一次 io（寻道 + 旋转 + 传输）通常是内存访问的数十万倍。因此，衡量数据库索引效率的核心指标不是算法的时间复杂度，而是磁盘 io 次数。

操作系统从磁盘读取数据时，遵循局部性原理：即使只需要 1 字节，也会将包含该字节的一个完整数据块（page，innodb 中默认为 16kb）读入内存。b+ 树的设计充分利用了这一特性：

高扇出（fan-out）：非叶子节点只存键值，不存数据，单节点可容纳更多键值。以 16kb 页、主键 8 字节为例，一个节点可存储约 1200 个键值。
低高度：扇出 1200 时，高度为 3 的 b+ 树可存储 1200³ ≈ 17 亿条记录。这意味着即使上亿数据，从根节点到叶子节点也只需 2~3 次磁盘 io。

2.2 b+ 树与 b 树的本质区别

mysql 官方文档指出，innodb 使用 b+ 树变体来组织数据。b 树与 b+ 树的核心差异如下：

对比维度	b 树	b+ 树
数据存储位置	所有节点都存储数据	仅叶子节点存储数据，非叶子节点只存键
叶子节点结构	独立节点，无链表连接	通过双向指针形成有序链表
范围查询效率	需要在中序遍历中反复跳跃	一次定位后顺序扫描链表即可
单节点键数量	较少（因为包含数据）	更多（仅存键值）
树高度	相对较高	相对较低

2.3 b+ 树内部结构详解

一棵 b+ 树由以下三部分构成：

根节点（root node）：树的入口，通常常驻内存。只在树分裂或合并时发生变化。

内部节点（internal node）：仅存储键值及其指向下一层节点的指针。结构为 [k1, p1, k2, p2, ..., kn, pn]，其中指针 pi 指向的子树中所有键值 ∈ [ki, k(i+1))。

叶子节点（leaf node）：存储完整的键值和行数据，并通过前后指针串联。每个叶子节点页中包含一个页目录，用于内部二分查找。

2.4 查询过程详解

等值查询（如 where id = 25）：从根节点开始，逐层进行二分查找，定位到目标键所在的下一层指针，最终到达叶子节点。以高度为 3 的树为例，需要 2~3 次磁盘 io。

范围查询（如 where id between 100 and 500）：首先通过等值查询定位到起始键 100 所在的叶子节点，然后沿叶子节点的 next 指针顺序向后扫描，直到遇到第一个大于 500 的键值。整个过程中，只有定位起始节点需要回溯根节点，后续扫描都在叶子链表上顺序完成——磁盘 io 次数 = 树高度 + 扫描涉及的叶子页数。这正是 b+ 树相对 b 树的核心优势所在。

2.5 页分裂与平衡

当向叶子节点插入数据导致页满时，innodb 会触发页分裂：将原页中约 50% 的数据移动到新页，并更新父节点的键值指针。这一机制保证了 b+ 树始终保持平衡，不会出现退化成链表的情况。

三、应用场景

3.1 日常开发场景

主键索引与自增 id：在实际开发中，强烈建议使用自增 id 作为主键。因为 innodb 的数据按主键顺序存储在 b+ 树的叶子节点中（聚簇索引），使用自增 id 保证了数据插入总是在叶子链表的末尾追加，避免了频繁的页分裂，从而显著提升写入性能。如果用 uuid 作为主键，随机插入会导致大量的页分裂和数据移动，写入性能会急剧下降。

联合索引与最左前缀：b+ 树的键值比较是从左到右依次进行的。因此创建联合索引 (a, b, c) 时，数据先按 a 排序，a 相同时按 b 排序，以此类推。这意味着查询条件中必须包含 a 才能利用该索引——这就是最左前缀原则的底层原因。例如 where a = 1 and b > 10 可以充分利用索引，而 where b = 10 则无法使用该联合索引。

覆盖索引优化：当查询的所有列都出现在索引中时，mysql 只需扫描索引的叶子节点即可返回结果，无需回表查询完整的行数据。这减少了磁盘 io，提升了查询效率。

3.2 企业真实场景

千万级用户查询优化：某电商平台的用户表包含 3000 万条记录，经常执行按手机号登录和按注册时间范围查询。技术方案：在 phone 字段上建立唯一索引（b+ 树），等值查询只需 3 次磁盘 io；在 create_time 字段上建立普通索引，范围查询利用叶子链表顺序扫描，查询耗时从 5 秒降至 50 毫秒。

订单系统分页优化：订单表数据量达到亿级时，offset 深度分页（如 limit 1000000, 20）会导致 mysql 扫描大量无关数据。优化方案：利用 b+ 树有序特性，先通过 where id > last_max_id 定位起点，再取 limit 20。这种基于游标的分页方式将扫描范围精确控制在叶子节点链表的一个小段区间内。

日志系统时间范围检索：运维平台的日志表每天新增数千万条数据，需要按时间区间检索。在时间戳字段上建立 b+ 树索引后，范围查询只扫描对应的叶子节点段，结合分区表策略，可实现秒级返回结果。

四、使用方式

下面通过 java 代码示例演示如何使用 jdbc 操作 mysql，并展示执行计划来验证 b+ 树索引的实际效果。

4.1 环境准备

-- 创建用户表
create table user (
    id bigint auto_increment primary key,
    username varchar(50) not null,
    phone varchar(20) not null,
    create_time datetime not null default current_timestamp,
    index idx_phone (phone),
    index idx_create_time (create_time)
) engine=innodb default charset=utf8mb4;
-- 插入 100 万条测试数据（省略批量插入脚本）

4.2 java 示例代码

import java.sql.*;
import javax.sql.datasource;
import com.zaxxer.hikari.hikariconfig;
import com.zaxxer.hikari.hikaridatasource;
public class bplustreeindexdemo {
private static datasource datasource;
static {
hikariconfig config = new hikariconfig();
config.setjdbcurl("jdbc:mysql://localhost:3306/test_db?usessl=false&servertimezone=utc");
config.setusername("root");
config.setpassword("your_password");
config.setmaximumpoolsize(10);
datasource = new hikaridatasource(config);
}
public static void main(string[] args) throws sqlexception {
// 1. 利用 b+ 树主键索引进行等值查询 —— 时间复杂度 o(log n)，磁盘 io 次数 = 树高度
querybyid(500000l);
// 2. 利用 b+ 树索引进行范围查询 —— 利用叶子链表顺序扫描
rangequerybycreatetime("2024-01-01 00:00:00", "2024-01-31 23:59:59");

// 3. 利用联合索引 + 覆盖索引避免回表
coveringindexquery();
}
/**
等值查询 —— 通过主键定位，走 b+ 树从根到叶子的路径。
执行流程：
a) 从根节点开始，通过二分查找定位到下一层内部节点；
b) 在内部节点中继续二分查找，找到目标叶子节点所在页；
c) 将叶子节点页加载到内存，通过页目录二分查找定位具体行。
*/
private static void querybyid(long id) throws sqlexception {
string sql = "select id, username, phone, create_time from user where id = ?";
try (connection conn = datasource.getconnection();
preparedstatement pstmt = conn.preparestatement(sql)) {
pstmt.setlong(1, id);
// 打印执行计划 —— 可以看到 type=const、key=primary
printexplain(conn, sql.replace("?", string.valueof(id)));
long start = system.currenttimemillis();
try (resultset rs = pstmt.executequery()) {
if (rs.next()) {
system.out.printf("查询结果: id=%d, username=%s, phone=%s%n",
rs.getlong("id"), rs.getstring("username"),
rs.getstring("phone"));
}
}
system.out.printf("等值查询耗时: %d ms%n", system.currenttimemillis() - start);
}
}
/**
范围查询 —— b+ 树的核心优势场景。
执行流程：
a) 通过 b+ 树定位到起始时间对应的叶子节点（一次树搜索）；
b) 沿叶子节点 next 指针顺序向后扫描，直到遇到第一个超出结束时间的记录；
c) 整个扫描过程中不需要再回溯父节点，磁盘 io = 树高度 + 扫描叶子页数。
*/
private static void rangequerybycreatetime(string starttime, string endtime)
throws sqlexception {
string sql = "select id, username, create_time from user " +
"where create_time between ? and ? order by create_time";
try (connection conn = datasource.getconnection();
preparedstatement pstmt = conn.preparestatement(sql)) {
pstmt.setstring(1, starttime);
pstmt.setstring(2, endtime);
printexplain(conn, sql.replace("?", "'" + starttime + "'")
.replace("?", "'" + endtime + "'"));
long start = system.currenttimemillis();
int count = 0;
try (resultset rs = pstmt.executequery()) {
while (rs.next()) {
count++;
}
}
system.out.printf("范围查询结果数: %d, 查询耗时: %d ms%n",
count, system.currenttimemillis() - start);
}
}
/**
覆盖索引查询 —— 查询列全部包含在索引中，无需回表。
注意事项：
extra 列显示 using index 表示完全覆盖索引；
索引列要尽量窄，以提升单页存储的键值数量，降低树高度。
*/
private static void coveringindexquery() throws sqlexception {
string sql = "select phone from user where phone = '13800138000'";
try (connection conn = datasource.getconnection();
statement stmt = conn.createstatement()) {
printexplain(conn, sql);
try (resultset rs = stmt.executequery(sql)) {
if (rs.next()) {
system.out.println("覆盖索引查询命中: " + rs.getstring("phone"));
}
}
}
}
/**
打印执行计划，用于验证索引使用情况。
*/
private static void printexplain(connection conn, string sql)
throws sqlexception {
string explainsql = "explain " + sql;
try (statement stmt = conn.createstatement();
resultset rs = stmt.executequery(explainsql)) {
system.out.println("\n===== 执行计划 =====");
while (rs.next()) {
system.out.printf("id=%d, select_type=%s, table=%s, type=%s, " +
"possible_keys=%s, key=%s, key_len=%s, " +
"rows=%d, extra=%s%n",
rs.getint("id"), rs.getstring("select_type"),
rs.getstring("table"), rs.getstring("type"),
rs.getstring("possible_keys"), rs.getstring("key"),
rs.getstring("key_len"), rs.getlong("rows"),
rs.getstring("extra"));
}
}
}
}

4.3 执行流程与注意事项

关于 range 类型的扫描：执行计划中 type=range 表示通过 b+ 树的叶子节点链表进行范围扫描。rows 列为预估扫描行数，该值越接近实际返回行数说明索引选择性越高。

注意避免索引失效场景：对索引列使用函数（如 where date(create_time) = '2024-01-01'）会导致 b+ 树索引失效，因为 mysql 无法直接利用键值进行二分查找；like 'keyword%' 可以使用索引（前缀匹配），但 like '%keyword' 无法使用，因为 b+ 树按前缀有序，中间匹配无法利用键值比较。

关于回表开销：普通索引的叶子节点存储的是主键值，而非完整行数据。当查询列超出索引覆盖范围时，mysql 需要拿着主键回到聚簇索引中查找完整行数据，这就是回表。每次回表都是一次额外的 b+ 树搜索，因此高频查询应尽量使用覆盖索引。

关于自适应哈希索引：innodb 会监控 b+ 树索引的访问模式，对热点数据页自动构建哈希索引（自适应哈希索引），进一步提升等值查询性能。这一特性对用户透明，无需手动干预。

五、扩展延伸

5.1 技术对比：b+ 树 vs lsm 树

对比维度	b+ 树（mysql innodb）	lsm 树（rocksdb / hbase）
写入方式	原地更新，可能触发页分裂	追加写，写入性能极高
读取方式	直接读取，读性能稳定	需合并多层 sstable，读放大严重
空间放大	存在页内碎片（b+ 树填充因子）	存在旧版本数据，需定期 compaction
适用场景	读写均衡的 oltp 场景	写多读少的大数据场景
代表产品	mysql、postgresql	rocksdb、leveldb、hbase

mysql 作为 oltp 数据库，读操作占比通常更高，且需要支持事务的即时一致性读取。b+ 树的原地更新机制天然适配这一需求，而 lsm 树的追加写机制在处理即时一致性读取时需要多层合并，延迟不可控。

5.2 b+ 树的优缺点总结

优点：

磁盘 io 次数少：高扇出保证极低的树高度。
范围查询高效：叶子节点链表使得范围扫描仅需一次定位 + 顺序扫描。
查询性能稳定：任何数据的查询路径长度相同（均为树高度）。
全表扫描友好：只需扫描叶子链表，无需遍历整棵树。

缺点与注意事项：

写入性能受限：插入或更新可能导致页分裂和数据移动，随机插入时尤为明显。
空间利用率非 100%：页分裂后每个页保持约 50% 填充率以保证后续插入的性能。
并发控制复杂：页分裂时需要加锁保护，mysql 通过索引锁（index lock）和间隙锁（gap lock）来实现一致性。
不适合极高频写入：每秒数十万次随机写入的场景下，页分裂开销会成为瓶颈，此时 lsm 树是更好的选择。

5.3 实际开发注意事项

主键设计：强烈建议使用自增 bigint 作为主键，避免使用 uuid 或业务主键，以保持 b+ 树叶子链表的有序插入。
索引宽度控制：索引列越窄，单个节点容纳的键值越多，树越低，io 越少。避免在长 varchar 字段上建立索引。
联合索引列顺序：将区分度最高的列放在联合索引最左侧，合理利用最左前缀原则。
定期分析表结构：使用 analyze table 更新索引统计信息，帮助优化器做出正确的索引选择。
监控慢查询：通过慢查询日志发现未正确使用索引的 sql，关注 type 为 all（全表扫描）的查询。

六、面试追问

追问 1：为什么 mysql 不用红黑树或 avl 树作为索引？

回答思路：从数据量和磁盘 io 两个维度切入。红黑树和 avl 树是二叉树，每个节点只有两个子节点。当数据量达到千万级别时，树高度会达到 20+ 层，意味着一次查询需要 20+ 次磁盘 io——这在生产环境中是不可接受的。b+ 树的多路设计（每个节点可以有数百个子节点）将树高度压缩到 3~4 层，从根本上控制了磁盘 io 次数。

标准回答：红黑树和 avl 树是内存数据结构，设计目标是最小化比较次数。而数据库索引是磁盘数据结构，设计目标是最小化磁盘 io 次数。b+ 树将查询路径长度从二叉树的 20+ 次磁盘 io 降低到 3 次左右，这是数量级的差异。此外，b+ 树的叶子节点链表天然支持高效范围查询，而红黑树的中序遍历需要在树中反复回溯。

追问 2：b+ 树的高度对查询性能有多大影响？如何查看某张表的索引高度？

回答思路：首先明确高度与数据量的数学关系，再给出查询高度的实际操作。

标准回答：b+ 树高度每增加一层，等值查询就会增加一次磁盘 io。在现代硬件条件下，单次随机磁盘 io 约需 5~10 毫秒。因此高度为 2 和高度为 4 的查询延迟差异大约为 10~20 毫秒。对于高并发场景，这一差异会被显著放大。查看索引高度的方法：查询 innodb 的索引页面信息，可以从 information_schema.innodb_sys_indexes 和相关数据字典表中获取。更直接的方法是通过分析 b+ 树根页面在 buffer pool 中的层级信息来推断。也可以使用 mysql.innodb_index_stats 表来辅助估算，结合表的行数和索引页大小进行推算。

追问 3：如果业务中必须使用 uuid 作为主键，如何优化写入性能？

回答思路：承认问题（随机插入导致页分裂），提出多层次的优化策略。

标准回答：可以从四个层面进行优化：第一，将 uuid 中的时间戳部分前置（使用 uuid v7 或自定义格式），把随机性转化为近似有序，让写入落在 b+ 树相近的叶子节点上；第二，适当降低 b+ 树的填充因子（通过调整页填充率参数），为每次插入预留更多的空闲空间，减少页分裂的频率；第三，在业务层面对写入做批量排序和合并，降低随机性；第四，如果写入压力极大，可以考虑引入消息队列缓冲，将同步写入改为准实时批量写入。不过需要强调，这些优化只能缓解问题，无法从根本上消除随机插入带来的性能损耗。如果可以重新设计架构，更推荐使用自增整数主键 + uuid 业务唯一标识的混合方案。

总结

到此这篇关于为什么mysql选择使用b+树作为索引结构的文章就介绍到这了,更多相关mysql用b+树作索引结构内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！

一文详解为什么MySQL选择使用B+树作为索引结构

2026年09月08日 • Mysql •我要评论