为什么 InnoDB 默认用 B + 树做索引结构？

InnoDB 选择 B+ 树索引的原因

高效的磁盘 I/O 操作
B+ 树是多叉树结构，层数较少（通常 3-4 层），能显著减少磁盘 I/O 次数。相比二叉树（如 AVL 树或红黑树），B+ 树的矮胖结构更适合磁盘这种慢速存储设备。

顺序访问性能优异
B+ 树的叶子节点通过指针串联成链表，范围查询（如WHERE id BETWEEN 10 AND 100）只需定位起始节点后顺序遍历，无需回溯上层节点。这种特性特别适合数据库常见的范围查询场景。

更高的空间利用率
B+ 树非叶子节点仅存储键值（不存数据），单个节点能容纳更多索引项，进一步降低树高。相比 B 树（非叶子节点存储数据），B+ 树的非叶子节点能承载更多分支。

稳定的查询效率
所有数据均存储在叶子节点，任何查询都需要从根节点到叶子节点的路径，路径长度恒定。这种稳定性使得查询时间复杂度始终为 $O(\log n)$，而 B 树可能在非叶子节点命中数据导致查询时间波动。

更适合全表扫描
由于叶子节点包含全量数据且有序链接，全表扫描时只需遍历叶子节点链表即可，无需访问上层索引结构。这种设计对分析型查询（如COUNT(*)）更友好。

与缓冲池机制协同
InnoDB 的缓冲池（Buffer Pool）会缓存热点索引页。B+ 树的局部性原理（相邻数据物理存储邻近）能提升缓存命中率，减少实际磁盘读取。