🧱 1. 先一句话：B+Tree 是为磁盘 I/O 优化出来的树
不是为了算法优雅，也不是为了数据结构好看。
数据库最贵的不是算力，是：
磁盘随机 I/O
随机读一个页（16KB）要 0.1~1ms
在 CPU 看来这是地狱般的慢。
所以索引设计目标只有一个：
减少磁盘随机 I/O 次数，让查询尽量少读页。
能做到：
- 高扇出（每个节点分叉数多）
- 高度非常低（一般 2~3 层）
- 每次查找只需要 2–3 次 I/O
这就是 B+Tree。
🧊 2. 为什么不是“二叉树”？
你用一个例子就能秒懂。
假设 1000 万条数据。
用二叉树（例如 AVL、红黑树）：
树高度大约：
log2(1000万) ≈ 23 层
一次查询要走 23 层。
每层一个节点。
每个节点都可能不在内存 → 就要读一个页。
所以：
一条查询 = 最多 23 次磁盘随机 I/O
性能直接暴毙。
🌲 3. B+Tree 为什么高度低？（关键：高扇出）
数据库不是一条条数据放在节点，而是“一个节点（一个页）放很多 key”。
一个页 16KB
一个 key（主键 + 指针）几十字节
算一下：
一个页可以放大约 200～1000 个 key
也就是：
一个节点可以有 200～1000 个子节点。
扇出巨大。
因此树高度极低：
| 数据量 | B+Tree 高度 |
|---|---|
| 10 万 | 高度 2 |
| 1000 万 | 高度 3 |
| 1 亿 | 高度 3~4 |
也就是说，你查任何一条记录：
👉 最多读 3 个磁盘页就搞定
（根节点 + 一层中间节点 + 叶子节点）
现代 InnoDB 根节点几乎总是在 Buffer Pool
所以：
→ 查询通常只做 1 次磁盘 I/O
这就是为什么 B+Tree 强无敌。
🧨 4. 为什么不是 Hash？
Hash 看似 O(1)，为什么不用？
因为：
❌ Hash 不支持范围查询
比如：
WHERE age BETWEEN 20 AND 30
Hash 根本不知道 key 的相对大小。
B+Tree 天生支持范围查询，靠页之间的链表就能顺序扫描。
❌ Hash 不能支持排序（ORDER BY）
你要按 name 排序，Hash 没有顺序结构。
❌ Hash 冲突严重，存储更复杂
❌ Hash 不支持前缀匹配（like 'abc%'）
所以 Hash 只能用于：
- 内存 KV 存储
- Redis
- 哈希表
数据库存储引擎 100% 不适合。
🧩 5. 为什么 B+Tree 的“每个节点 = 一个磁盘页”很关键？
这是绝妙的设计点。
InnoDB 规定：
每一个节点 = 正好一页（16KB）
因为磁盘读取的最小单位是页，不是字节。
一次磁盘 I/O = 把 16KB 整页搬进来
那干脆把节点设计成大小刚好一页：
✔ 一次 I/O 就能把整个节点的数据读进来
✔ 这个页里有几百个 key（超级省 I/O）
✔ 这就是高扇出
✔ 扇出大 → 树高低 → 访问层数少 → 查询快
这就是数据库工程师的智慧：
“我知道磁盘读写慢，所以我把树节点做成和磁盘页一样大。”
这不是算法，是工程。
🧵 6. 为什么 B+Tree 的叶子节点用链表串起来？
因为数据库大量使用范围扫描（range scan）：
WHERE id BETWEEN 10 AND 20000
如果叶子节点是链表：
Page1 → Page2 → Page3 → ...
那么找起点后，就是连续顺着链表走：
- 连续页 → 顺序 I/O
- 顺序 I/O 比随机 I/O 快几十倍
所以范围查询飞快。
🥇 7. 为什么是 B+Tree，而不是 B-Tree？
B+Tree 的特点：
✔ 所有数据都在叶子节点（更适合磁盘）
内节点只存 key，不存数据 → 放更多 key → 高扇出 → 树更低
✔ 范围扫描直接从叶子链表扫，非常快
✔ 叶子节点存储结构适配页（16KB），能放更多行
B-Tree 查找过程中就会遇到“数据放在内节点里”
→ 查询变复杂
→ 范围扫描困难
所以 B+Tree 是更适合数据库的版本。
🎯 最终总结：
索引用 B+Tree，是因为：
🥇 1. 读磁盘就是最贵 → 要减少 I/O
🥇 2. 一个节点一页，提高扇出降低高度
🥇 3. 范围查询大量使用 → 链表顺序扫快
🥇 4. 内节点不存数据 → 扇出更大 → 树更矮
🥇 5. 主键自增插入不会导致随机分裂 → 高效稳定
数据库里的 B+Tree
不是数据结构课上的玩具
而是高度适配存储介质的“工程产物”。