直接回答：MySQL InnoDB 索引底层是 B+ 树。选 B+ 树的核心原因：树高低（扇出大，千万级数据通常 3-4 层，每次查找只需 3-4 次磁盘 IO）；内部节点只存键不存数据，单页能容纳更多索引项；数据全在叶子节点且叶子间有双向链表，天然支持高效的范围扫描和排序。

展开解析：与其他结构对比：

  • 哈希索引：等值查询 O(1)，但不支持范围、排序和最左前缀，冲突处理也麻烦。
  • 二叉树/B 树：二叉树退化后高度不可控；B 树数据存在所有节点，单页键少、层数更高，范围查询还要中序遍历跳层。
  • 跳表：Redis 用它做内存索引尚可，但磁盘场景下按页读取的局部性不如 B+ 树。

相关要点：磁盘 IO 是数据库性能的决定因素，B+ 树让每个节点正好对应一个页（默认 16KB）；InnoDB 主键索引的叶子存整行（聚簇），二级索引叶子存主键值，引出回表概念。

追问方向：为什么不用 B 树、聚簇索引与回表、页分裂与索引维护成本。