索引的本质就是“给数据建立一套快速查找的目录”，而目录用什么数据结构组织，直接决定了查找效率的高低。一种数据结构能否胜任数据库索引，关键看两点：一是磁盘 I/O 次数多少，二是对范围查询和排序是否友好。下面逐一对比常见的数据结构，最终解释为什么 InnoDB 选择了 B+ 树。
二叉树
二叉查找树是最直观的索引结构：每个节点最多有两个子节点，左子节点值小于父节点，右子节点值大于父节点。查找时从根节点开始，比大小决定向左还是向右，时间复杂度理想情况下是 O(log n)。
但二叉树有两个致命问题：
- 不平衡导致性能劣化：如果插入的数据是递增的（如自增主键），二叉树会退化成一条单链表，查找复杂度变成 O(n)，跟全表扫描无异。
- 节点深度太大：即使树是平衡的，二叉树每个节点只存一个键值和两个指针，节点数等于记录数。对于百万行数据，树的高度就是 20 层左右，每次查找需要 20 次磁盘 I/O，这在数据库中不可能接受。
因此，直接使用二叉树做数据库索引是行不通的。
红黑树
红黑树是一种自平衡的二叉查找树，通过颜色标记和旋转操作保证最长路径不超过最短路径的两倍，避免了退化问题。平衡后的红黑树高度大约是 2log(n)，查找复杂度稳定在 O(log n)。Java 的 TreeMap 就基于红黑树实现。
但红黑树依然是以二叉树为基础的，每个节点只存一个键值和很小的数据，节点数还是等于记录数。百万行数据，红黑树高度依然会达到 20 层左右。对于内存中的数据结构来说这不是问题（内存访问极快），但放到磁盘上，20 次随机 I/O 依然是灾难。红黑树更适合纯内存场景，无法应对海量数据的磁盘索引需求。
B 树
B 树（多路平衡查找树）对二叉树做了根本性的改造：每个节点可以存放多个键值和多个子节点指针，一个节点的大小通常被设计为恰好装满一个磁盘页（InnoDB 中是 16KB）。这样一来，树的高度被大幅压缩。
比如，一个 16KB 的节点可以存放几百个键值，百万行数据的 B 树高度通常只有 3 层，查找一次最多只需要 3 次磁盘 I/O。这就是 B 树核心优势：极度矮胖，I/O 次数极少。
B 树还有一个特点：所有节点都可以存储数据。也就是说，键值可以散布在整棵树的任意位置，非叶子节点里也存着完整的行数据或数据指针。这样一来，等值查询可能直接在非叶子节点就找到目标，不必一定走到叶子节点。
那为什么 InnoDB 没有直接用 B 树而是选择了 B+ 树呢？问题出在范围查询和排序上。
因为 B 树的键值分散在各个节点，彼此没有明显的顺序链接。要查某个范围（如 WHERE id BETWEEN 1000 AND 2000），需要在不同层级的节点之间来回跳跃，I/O 模式从顺序变成了随机，性能大打折扣。而数据库中范围查询是家常便饭，B 树在这方面的短板使它难以成为最优选择。
B+ 树
B+ 树是 B 树的升级版，也是 InnoDB 索引的实际数据结构。它与 B 树最大的区别在于：
- 所有数据都存储在叶子节点：非叶子节点只存键值和子节点指针，不存实际数据。这让非叶子节点可以存放更多的键值，进一步降低树的高度。
- 叶子节点之间有双向链表连接：所有叶子节点按索引键值顺序串联在一起，形成一个有序的链表。
这两点改进直接解决了 B 树的痛点：
- 范围查询极快：先通过 B+ 树的查找定位到范围的起始叶子节点，然后沿着链表顺序向后扫描即可，完全不需要在树的不同层级之间跳跃。磁盘 I/O 是顺序的，效率接近全表扫描，但只扫描符合条件的分片。
- 等值查询更稳定：B 树可能在某非叶子节点就命中返回，但 B+ 树一定要走到叶子节点。这看似多了一两层 I/O，但实际由于树高极低（通常 3 层），多出的开销几乎不可感知，反而保证了每次查询的时间都高度一致，不会出现“偶尔很快、偶尔很慢”的抖动。
- 排序友好：因为叶子节点本身就是有序的，
ORDER BY查询可以直接利用索引的顺序，避免额外的文件排序。
这些特性让 B+ 树成为关系型数据库索引的黄金标准，InnoDB 的聚簇索引和二级索引全部采用 B+ 树结构。
哈希表
哈希表（Hash）通过哈希函数将键值映射到固定的存储位置，等值查询的时间复杂度是 O(1)，快得惊人。Memory 存储引擎支持哈希索引，InnoDB 也有自适应的哈希索引特性。
但哈希表在数据库索引中有明显的局限性：
- 不支持范围查询：哈希索引只能做精确匹配（
=或IN），对于>、<、BETWEEN、ORDER BY等操作完全用不上。 - 无法排序：哈希表中数据的存储顺序与键值大小无关，无法避免排序操作。
- 哈希冲突处理：冲突率升高时，查找性能会退化，虽然可以通过链地址法等缓解，但仍不如 B+ 树稳定。
- 不支持部分键匹配：联合索引中如果只用到第一列的部分匹配，哈希索引完全无法使用，必须给出完整的索引列值。
所以，哈希索引只适用于某些特定的等值查询场景，比如单条记录查找、精确匹配的缓存表等。MySQL 的 Memory 引擎和自适应哈希索引就是为这些场景服务，但不可能作为通用索引的主流方案。
对比总结
| 数据结构 | 等值查询 | 范围查询 | 排序 | I/O 效率 | 磁盘友好 | 适用场景 |
|---------|---------|---------|------|---------|----------|----------|
| 二叉树 | O(log n)，退化 O(n) | 差 | 中 | 极差 | 极差 | 无数据库使用 |
| 红黑树 | O(log n) 稳定 | 差 | 中 | 差 | 差 | 内存索引，少量数据 |
| B 树 | O(log n)，偶尔更快 | 差 | 中 | 好 | 好 | 某些文件系统 |
| B+ 树 | O(log n) 稳定 | 极优 | 极优 | 优秀 | 优秀 | 数据库索引标准方案 |
| 哈希表 | O(1) | 不支持 | 不支持 | 好（仅精确匹配） | 一般 | 自适应哈希、缓存 |
不难看出，B+ 树在等值查询、范围查询、排序和磁盘 I/O 之间取得了近乎完美的平衡，这就是它成为 InnoDB 索引唯一实现方式的原因。理解了这些数据结构的优劣，你就会明白为什么数据库领域几十年下来，B+ 树始终是索引的王道选择。