1. 核心概念

索引（Index）是帮助 MySQL 高效获取数据的数据结构。在 InnoDB 中，索引通常实现为 B+ 树。

2. 原理分析

2.1 减少 IO 次数 (核心原因)

  • 不命中索引：全表扫描（Full Table Scan）。假设表有 1000万行，数据分布在 10万个数据页中，数据库需要从磁盘读取这 10万个页到内存进行比对，IO 开销巨大。
  • 命中索引：B+ 树扫描。B+ 树是多路平衡查找树，高度通常只有 3-4 层。
    • 查找某一行数据，只需要从根节点向下遍历 3-4 个节点（即 3-4 次 IO）就能定位到数据。
    • 数量级差异：3次 IO vs 10万次 IO。

2.2 算法复杂度

  • 全表扫描：线性查找，时间复杂度 O(N)。
  • 索引查找：二分查找（及变种），时间复杂度 O(logN)。

2.3 范围查询优化

B+ 树的叶子节点通过 双向链表 连接。

  • 当执行范围查询（如 WHERE id > 100）时，一旦找到起点，只需顺着链表遍历即可，无需重新回溯，效率极高。

3. 性能考量

虽然索引快，但不是越多越好：

  1. 写代价：每次 INSERT/UPDATE/DELETE 都需要维护 B+ 树结构（分裂、合并），会降低写性能。
  2. 空间代价：索引文件也会占用磁盘空间。

4. 总结

面试回答示例： “索引快的主要原因是它将 随机 IO 变成了顺序 IO 并且大幅减少了 IO 次数。 全表扫描是 O(N) 复杂度，需要加载所有数据页。 而 InnoDB 的 B+ 树索引通常只有 3-4 层高，通过 O(logN) 的二分查找算法，只需要 3-4 次磁盘 IO 就能定位到目标数据。此外，B+ 树叶子节点的有序链表结构也极大地加速了范围查询。”