InnoDB 为什么用 B+ 树做索引？

InnoDB 选用 B+树做索引的核心原因（对比二叉树、B树、哈希）

一、先理清关键结构差异

1. 二叉搜索树/红黑树：层高太高，大数据量磁盘IO爆炸
2. Hash索引：不支持范围查询、排序、前缀模糊
3. B树：数据+索引混在所有节点
4. B+树：非叶子只存键，叶子全存数据、链表串联，InnoDB主键索引聚簇存储

二、B+树适配磁盘IO（最关键）

磁盘是块设备，按页（默认16KB）IO读取，一次IO加载一页节点：

1. 非叶子节点无数据，单页能存更多索引键→ 树高度极低（千万级数据一般3层）
   • 3层B+：根页(内存)+中间页(1次IO)+叶子页(1次IO)，最多2次磁盘IO查到数据
2. B树节点存「key+数据」，单页存的键变少，树更高、IO更多。

三、优势1：范围查询、ORDER BY、LIKE前缀极快

B+所有叶子节点用双向链表有序串联：

• > < >= <= between、排序、全表扫不用回溯上层，顺着链表遍历即可；
• Hash是散列无序，完全无法高效范围检索；二叉树范围要多次递归查找。

四、优势2：聚簇索引天然适配InnoDB存储模型

InnoDB主键是