MySQL 索引原理：B+Tree 为什么统治了数据库世界

面试必问题：「为什么 MySQL 用 B+Tree 而不是二叉树/哈希/B-Tree？」

磁盘 IO 是根本原因

CPU L1 Cache:  ~1ns
内存访问:      ~100ns
SSD 随机读:    ~100μs   ← 比内存慢 1000 倍
HDD 随机读:    ~10ms    ← 比内存慢 100,000 倍

数据库的瓶颈永远是磁盘 IO。索引的目标：用最少的磁盘 IO 找到数据。

B+Tree 结构

              [30|60]          ← 非叶子节点只存 key
            /    |    \
      [5|15]  [40|50]  [70|80]  ← 内部节点
       /  \    /  \    /  \
    [叶子节点 — 存全部数据 + 双向链表]

• 所有数据在叶子节点
• 叶子节点用双向链表连接（范围查询友好）
• 非叶子节点只存 key，一页能存更多 → 树更矮

为什么不是其他结构

聚簇索引 vs 二级索引

-- InnoDB 的聚簇索引：数据存在叶子节点
-- PK 就是聚簇索引
SELECT * FROM users WHERE id = 100;  -- 一次 B+Tree 查找

-- 二级索引：叶子节点存主键值
-- 需要「回表」
SELECT * FROM users WHERE name = 'Alice';
-- 1. 在 name 索引找主键 id
-- 2. 用 id 去聚簇索引找完整行

覆盖索引：查询列全在索引里，避免回表。

-- 不用回表
SELECT id, name FROM users WHERE name = 'Alice';

B+Tree 统治数据库 40 年，靠的是对磁盘 IO 的极致优化。