InnoDB 为什么使用 B+ 树作为索引结构？

简化版

InnoDB 使用 B+ 树，是因为它能用很低的树高承载大量数据，减少磁盘 I/O，并且叶子节点天然按键有序，适合范围查询。相比哈希索引只能做等值查找，B+ 树同时兼顾等值、范围、排序和分页等常见查询场景。

详细版

B+ 树适合数据库索引，核心原因有四个：

树高低：一个页里能放很多 key，千万级数据通常也只需要少数几层，查询路径短。
磁盘友好：节点大小可以和数据页匹配，一次 I/O 读一个页，顺序访问叶子节点也更高效。
范围查询强：叶子节点按 key 有序并通过链表相连，between、>、order by 可以顺着叶子节点扫描。
稳定可控：插入、删除、查找都是对数复杂度，性能波动相对小。

InnoDB 的索引分为两类：

聚簇索引：主键索引的叶子节点直接存整行数据，所以一张 InnoDB 表的数据本身就是按主键组织的一棵 B+ 树。
二级索引：普通索引的叶子节点存的是索引列值 + 主键值。通过二级索引查到主键后，如果还需要其他列，就要再回到聚簇索引查整行，也就是常说的回表。

完整版教学

一、数据库索引首先要适配磁盘模型

面试里问 B+ 树，不能只答“查找快”。数据库的数据通常比内存大，真正昂贵的是磁盘 I/O。索引结构的设计目标是：尽量少读页，并且尽量顺序读。

B+ 树每个节点可以存很多 key，不是二叉树那种一个节点只分两路。分叉多以后，树高会很低，比如高度 3 或 4 就能覆盖大量数据。一次查询通常只需要从根节点、内部节点一路走到叶子节点，读少数几个页就能定位记录。

InnoDB 默认页大小通常是 16KB。一个内部节点页里如果每个索引项平均占几十字节，就能放下几百个子节点指针；树高每增加一层，能管理的数据量会按“几百倍”扩张。粗略估算，一个三层 B+ 树就可能覆盖百万到千万级记录，而不是像二叉树那样随着记录数增长出很长路径。

一次主键查询的典型路径：

根页 -> 内部页 -> 叶子页
 1       1        1

通常只需少数页访问，树高低是数据库索引非常核心的收益。

二、为什么不是二叉树或红黑树

二叉树、红黑树更适合内存结构。它们每个节点分叉少，数据量一大树高就高，查一次可能跳很多节点。对内存来说这是指针访问，对磁盘来说就可能变成大量随机 I/O，代价很高。

B+ 树把多个 key 放进一个页里，利用了磁盘按页读取的特点。一次读页能拿到一批 key，比较多次后再决定走哪个子节点，这比频繁读很多小节点更适合数据库。

假设有 1000 万条记录，平衡二叉树高度大约是 log2(10000000)≈24，一次查找可能经过 20 多个节点；如果这些节点分散在磁盘页上，随机 I/O 成本很高。而 B+ 树的分叉数可能是几百，树高常见只有 3 到 4 层，访问路径明显短。数据库索引追求的不是单次 CPU 比较最少，而是整体 I/O 次数最少。

结构	分叉数量	适合场景	数据库索引短板
二叉搜索树	2	内存教学模型	树高高，磁盘随机访问多
红黑树	2	内存有序集合	节点小且分散，不贴合页读写
B 树	多路	外存索引	数据可在内部节点，范围扫描不如 B+ 树统一
B+ 树	多路	数据库索引	写入可能分裂页，但综合更适合

记忆钩子：内存结构怕比较次数，数据库索引更怕随机读页；B+ 树的优势是用高扇出把页访问次数压下来。

三、为什么不是哈希索引

哈希索引做等值查询很快，但短板也明显：

不支持范围查询，比如 id > 100；
不适合排序，因为哈希后的值没有顺序；
不适合最左前缀匹配；
遇到哈希冲突还要额外处理。

MySQL 业务查询里很少只有等值查询，范围、排序、分页、分组都很常见。B+ 树虽然等值查询不一定比哈希极限更快，但综合能力更强，所以成为 InnoDB 常规索引的主力结构。

比如下面几类 SQL，B+ 树可以利用有序性连续扫描：

where id between 100 and 200
where create_time >= '2026-07-01'
order by create_time limit 20
where name like 'Tom%'

哈希结构把 key 映射成散列位置，100 和 101 的哈希值不保证相邻，所以很难自然支持范围和排序。面试里可以承认哈希在等值查询上有优势，但数据库通用索引要覆盖更多查询模式，B+ 树的综合收益更稳定。

四、聚簇索引和二级索引怎么理解

InnoDB 表一定有聚簇索引。优先使用主键作为聚簇索引；如果没有主键，会选择合适的唯一非空索引；再没有则生成隐藏 row id。

聚簇索引的叶子节点存整行数据，所以按主键查非常直接。二级索引的叶子节点不存整行，而是存主键值。比如有索引 idx_name(name)：

select age from user where name = 'Tom';

如果 age 不在二级索引里，InnoDB 会先从 idx_name 找到主键，再用主键去聚簇索引取整行，这就是回表。回表不是错，但回表次数多会拖慢查询。

这也解释了为什么 InnoDB 强烈建议有短、稳定、递增或近似递增的主键。二级索引叶子节点保存主键值，主键越长，所有二级索引都会被带着变宽；主键频繁变化还会牵动聚簇索引组织。自增主键通常能减少页分裂和随机插入，但业务上也要考虑分库分表、热点写入等场景。

聚簇索引 PRIMARY:
id=10 -> [整行数据]

二级索引 idx_name:
name='Tom' -> id=10

按 name 查 age:
idx_name 找 id=10 -> PRIMARY 找整行 -> 返回 age

五、B+ 树索引最怕什么用法

B+ 树依赖“有序”来快速定位。如果查询条件破坏了索引列的原始顺序，就可能用不上索引或只能用一部分：

对索引列做函数：where date(create_time) = '2026-07-19'；
隐式类型转换：字符串列拿数字比较；
前置模糊匹配：like '%abc'；
联合索引没有按最左前缀使用。

这些问题的本质都是：优化器无法沿着 B+ 树从有序 key 中快速定位范围。

例如 where date(create_time) = '2026-07-19' 会把索引列包在函数里，B+ 树上保存的是原始 create_time，不是每行计算后的 date(create_time)。更可取的写法是把条件改成范围：

where create_time >= '2026-07-19 00:00:00'
  and create_time <  '2026-07-20 00:00:00'

这个改写保留了索引列原始有序性，MySQL 可以定位到一天的连续时间区间。索引失效类面试题，本质上都可以往“是否破坏 B+ 树有序查找”上归因。

六、页分裂、顺序扫描和范围查询

B+ 树所有数据都在叶子节点，叶子节点之间还有有序链表。这让范围查询很自然：先从根走到范围起点所在叶子页，然后沿叶子链表向后扫即可。比如 id between 1000 and 1100，定位到 1000 后，后续 101 条记录大概率能顺序读取相邻叶子页。

写入时，B+ 树也有代价。如果一个叶子页满了，新 key 插入中间位置，就可能触发页分裂；如果主键随机，插入位置分散，会增加页分裂和缓存命中压力。自增主键常被推荐，不是因为业务上一定更美，而是它让数据更倾向于追加写，符合 B+ 树页组织方式。

七、常见误区与追问

误区：B+ 树只是因为时间复杂度是 O(logN) 才适合索引。 数据库更关心磁盘页访问次数、范围扫描和缓存局部性，单纯说复杂度不够完整。
误区：二级索引叶子节点存完整行。 InnoDB 二级索引叶子节点存索引列和主键值，查索引外列需要再回聚簇索引。
误区：哈希索引一定比 B+ 树好。 哈希适合等值查找，但不适合范围、排序、前缀匹配，综合场景不如 B+ 树通用。
误区：主键长短只影响主键索引。 InnoDB 二级索引会保存主键值，主键过长会放大所有二级索引空间。
追问：为什么 B+ 树范围查询强？ 因为所有数据集中在有序叶子节点，叶子节点通过链表连接，定位起点后可以顺序扫描后续记录。
追问：为什么对索引列使用函数可能导致索引效果变差？ 因为 B+ 树按原始列值排序，函数计算后的值不再对应原有有序区间，优化器难以直接定位。

八、加强记忆

InnoDB 选 B+ 树，是因为它贴合磁盘页模型：多路分叉让树高低，叶子有序链表让范围扫描顺，所有数据放在叶子节点让访问路径稳定。聚簇索引叶子节点存整行，二级索引叶子节点存主键，查不到目标列就回表。把“页、树高、叶子链表、聚簇和二级索引”串起来，索引结构、最左前缀、覆盖索引和回表就能一起讲清楚。

简化版

详细版