B 树 —— 为什么 MySQL 选它不选红黑树一句话MySQL 数据在磁盘上磁盘 I/O 很慢。B 树是多叉树、树矮3 层存 2000 万条查一次最多读 3 次磁盘。红黑树是二叉树、树高20 层每次查要读 20 次磁盘——慢 10 倍。为什么不能只用内存里的数据结构数据库的数据存在磁盘上​磁盘 I/O 比内存慢 10 万倍​内存里读一次 几十纳秒 磁盘上读一次 几毫秒慢 10 万倍所以数据库索引的核心目标​尽量减少读磁盘的次数​。红黑树为什么不适合红黑树是二叉树每个节点只有 2 个子节点。 存 100 万条数据 红黑树高度 ≈ 20 层 查找一次最多读 20 次磁盘 ❌ B 树多叉树一个节点存几百个 key 存 100 万条数据高度 ≈ 3 层 查找一次最多读 3 次磁盘 ✅树越高磁盘 I/O 次数越多越慢。MySQL 选 B 树的根本原因就是它最矮。B 树长什么样┌───────────┐ │ 50 100 │ ← 内部节点只存 key不存数据 └─────┬─────┘ │ ┌─────────────────┼─────────────────┐ │ │ │ ┌─────┴──────┐ ┌─────┴──────┐ ┌─────┴──────┐ │ 10 25 40 │ │ 60 75 90 │ │ 110 130 │ ← 内部节点 └──────┬─────┘ └──────┬─────┘ └──────┬─────┘ │ │ │ ┌────┴────┐ ┌────┴────┐ ┌────┴────┐ │ 数据页 │ │ 数据页 │ │ 数据页 │ ← 叶子节点存完整行数据 │ id1 │ │ id51 │ │ id101 │ │ name.. │ │ name.. │ │ name.. │ └─────────┘ └─────────┘ └─────────┘ ←────── 叶子节点之间是双向链表 ──────→两个核心特征① 只有叶子节点存数据内部节点只存 key路标查找 age25 从根节点进 → 502550 → 走左边 → 第二层10,25,40 → 25 在 10~25 之间 → 走左边 → 叶子节点 → 找到 age25 的数据 一共读了 3 次磁盘 ✅② 叶子节点之间是双向链表适合范围查询SELECT * FROM user WHERE age BETWEEN 20 AND 80 先找到 20 → 顺着叶子节点的链表往后遍历 不需要每次都从根节点重新查 ✅为什么 B 树 3 层能存 2000 万条MySQL 默认一个节点页 16KB 假设 一行数据 ≈ 1KB 一个 keybigint 8B 指针6B≈ 14 字节 计算 一个叶子节点能存16KB ÷ 1KB 16 行 一个内部节点能存16KB ÷ 14B ≈ 1170 个 key 三层 B 树 第一层根 1 个节点 第二层内部 1170 个节点 第三层叶子 1170 × 1170 ≈ 137 万个节点 总数据量137 万 × 16 ≈ 2190 万条 ✅三层就能覆盖 2000 万条数据的查询每次查询最多 3 次磁盘 I/O。B 树 vs 红黑树 vs Hash 对比对比维度B 树红黑树Hash 索引树高3-4 层千万级20 层百万级—磁盘 I/O 次数3-4 次20 次1 次范围查询✅ 叶子链表遍历❌ 需要中序遍历❌ 不支持排序✅ 天然有序❌ 无序❌ 无序等值查询O(log n)O(log n)O(1) ✅B 树是综合性能最好的选择等值和范围查询都支持磁盘 I/O 少。 面试回答模板MySQL 用 B 树做索引核心原因是数据在磁盘上 I/O 是最大瓶颈。B 树是多叉树一个内部节点可以存几百个 key 树高很矮——3 层就能存 2000 万条数据查找最多 3 次 I/O。 红黑树虽然内存里很快但它是二叉树同样数据量树高 20 层 磁盘 I/O 次数多 10 倍不适合数据库。 另外 B 树的叶子节点是双向链表天然支持范围查询 这也是 Hash 索引做不到的。参考来源《MySQL 技术内幕InnoDB 存储引擎》第 5 章MySQL 官方文档B Tree Index