为什么 MySQL 选择使用 B+ 树作为索引结构？
- 标签：后端、MySQL、数据库
🏛 业务架构师
MySQL 选 B+ 树是为磁盘 IO 定价的结果，我按淘汰逻辑讲：
- 哈希表：等值查询 O(1) 但不支持范围查询和排序，而业务查询大量是"某个时间段的订单""某价格区间的商品"，直接出局；
- 二叉/红黑树：树太高。千万数据 20 多层，每层都可能一次磁盘 IO，等于每次查询 20 次随机 IO，无法接受；
- B 树：每个节点存数据，单页能放的关键字变少，树更高；且范围查询要中序回溯；
- B+ 树胜出：非叶子节点只存键（16KB 一页能放上千个键，扇出极大，千万数据仅 3 层），一次 IO 换到的"有效导航信息"最多；叶子节点用双向链表串联，范围查询和分页变成顺序读取——这正好匹配"按时间查订单、按类目翻商品"这类主流业务查询模式。
业务视角的引申：B+ 树的所有特性（页为单位 IO、高扇出低树高、叶子链表）都在服务一个目标——让单机数据库在可接受的硬件成本下扛住千万级数据和毫秒级响应，推迟了业务上分布式化的时间点。理解这一点就会明白：优化索引本质是在配合 B+ 树的工作方式（最左前缀、顺序插入、减少回表），顺着结构设计就是快，逆着就是慢。这也是我评估"这表要不要分库分表"时的判断起点：先把 B+ 树的潜力榨干。
🏗 系统架构师
我从四个候选结构对比推到 B+ 树，这是典型的选型论证：
- 哈希表：等值 O(1)，但不支持范围查询和排序，而业务里
where a > x and b < y、order by 是刚需，直接出局； - 二叉/红黑树：树高 log2(n)，一千万数据约 23 层，每层一次磁盘 IO 不可接受；数据结构太"瘦"，一个节点一个 key；
- B 树：多路平衡，节点存数据，单页放的 key 少于 B+ 树；且范围查询要中序回溯遍历；
- B+ 树：非叶子节点只存键不存数据，16KB 的页能放约 1200 个指针（bigint 主键），3 层树可承载约 2000 万行，一次查询最多 3 次页 IO；叶子节点双向链表相连，范围查询、分页沿链表顺序扫即可。
核心结论：B+ 树是为磁盘/SSD 这种按页读写的介质设计的结构——把"树高（IO 次数）"压到最低，把范围扫描变成链表顺序读。所有选型本质都是围绕存储介质的访问特性做优化，这个思想在 LSM-Tree（写优化）与 B+ 树（读优化）的分野里同样成立。
💻 全栈开发专家
因为 B+ 树在磁盘 IO 次数、范围查询两个维度都最优，而数据库的瓶颈恰恰是磁盘 IO：
- 矮胖 = IO 少：非叶子节点不存数据只存索引键，16KB 页能塞约 1170 个指针，3 层就能覆盖两千万行，一次查询 2~3 次 IO。对比 B 树（每个节点都存数据，单页指针少，树更高）、红黑树/二叉树（千万数据 20+ 层，每层一次 IO 不可接受）、Hash（等值 O(1) 但不支持范围和排序）。
- 叶子成链表 = 范围查询顺：
WHERE id BETWEEN 1 AND 10000在 B+ 树上定位起点后沿叶子链表顺序扫即可，一次顺序 IO；B 树要中序回溯反复横跳。 - 对磁盘预读友好：节点按页对齐，顺序 IO 吞吐远高于随机 IO。
我的总结话术：数据库选索引结构本质是"为磁盘和数据量设计"，内存结构（红黑树、跳表）优秀的点（单点修改快、实现简单）在磁盘场景不值钱。同理 Redis 是纯内存，就用跳表不用 B+ 树——面试官听到这个对比通常会很满意。