mysql选择b+树而非红黑树，根本原因是红黑树树高过高、单节点数据密度低、不支持高效范围查询；b+树通过非叶节点仅存键、叶子节点链表连接、数据集中存储等设计，大幅减少磁盘i/o并优化范围查询。
MySQL 选择 B+ 树而非红黑树，根本原因是：红黑树在磁盘 I/O 场景下树高过高、单节点数据密度太低、不支持高效范围查询，而 B+ 树专为磁盘存储和数据库查询模式优化。
红黑树为什么不适合做磁盘索引？
红黑树本质仍是二叉树，每个节点只存一个键 + 一行数据指针（data），100 万数据下树高通常达 20 层左右 —— 意味着最坏要进行 20 次随机磁盘 I/O 才能定位一条记录。而磁盘寻道一次约 10ms，20 次就是 200ms，远超数据库可接受延迟。
- 红黑树的旋转/变色操作必须在磁盘上完成，每次调整都可能触发额外 I/O，写入放大严重
- 节点分散在磁盘不同位置，无法利用局部性原理预读；B+ 树则把整页（如 16KB）作为节点单位，一次 I/O 就能加载全部子键
- 内存中用红黑树很高效，但数据库索引绝大多数驻留在磁盘，设计目标完全不同
B+ 树如何针对性解决红黑树的缺陷？
B+ 树通过三项关键设计压低 I/O 次数并支撑业务常见操作：
-
非叶子节点仅存 key：不存data，同样大小的页（如 16KB）能容纳数百个键，树高直接降到 3–4 层 -
叶子节点用双向链表连接：BETWEEN、ORDER BY、LIKE 'abc%'等范围查询只需定位起始叶节点，后续遍历链表即可，无需反复回溯根节点 - 所有
data集中在叶子层：既保证查询路径长度一致（稳定O(log n)），又让范围扫描变成顺序 I/O，大幅提升吞吐
实际建表时你能观察到的差异
执行 SHOW INDEX FROM t1 后，InnoDB 的主键索引显示为 BTREE 类型，但它底层是 B+ 树 —— 这个命名是历史兼容。真正影响性能的是结构行为：
- 对
SELECT * FROM t1 WHERE id BETWEEN 1000 AND 2000，B+ 树只需 1 次根节点 I/O + 1 次叶节点 I/O 定位起点，然后顺序读取链表；红黑树需对每个值单独查找，至少 1000 次 I/O - 插入新行时，B+ 树分裂只发生在叶子层，且分裂后仍保持链表连续；红黑树旋转可能波及多层节点，I/O 更不可控
-
EXPLAIN中看到type: range且rows值较小，背后正是 B+ 树叶子链表带来的范围跳转能力
真正容易被忽略的是：B+ 树的优势不是“理论更快”，而是它把数据库最重的两个负担——随机磁盘 I/O 和范围扫描——同时做到了极致压缩。一旦脱离磁盘场景（比如内存数据库），红黑树反而可能更合适。但只要数据落盘，B+ 树就是目前工程上最平衡的选择。
