Summer Reverie

外观

索引

约 1945 字大约 6 分钟

2025-07-24

B+ 树索引

索引的核心目标是减少磁盘 I/O 次数以提升查询效率。MySQL 的 InnoDB 存储引擎以页 (Page) 为磁盘 I/O 单位（默认 16KB）。B+ 树的节点大小与页对齐，使得树高度直接影响 I/O 次数。

为什么使用 B+ 树作为索引的数据结构？

通过对比其他数据结构说明 B+ 树的优势：

数据结构优点缺点
哈希表等值查询时间复杂度 O(1)不支持范围查询，退化为全表扫描
二叉查找树理想情况下查询效率较高有序插入时退化为链表，树高剧增，导致磁盘 I/O 次数过多
B 树多路平衡，树高低于二叉树非叶子节点存储数据记录，减少索引键容量，限制分支因子
B+ 树查询稳定、范围查询高效、树高最低无主要缺陷

B+ 树的三大核心特性：

  1. 非叶子节点仅存储索引键：显著提升分支因子（单个节点容纳更多键），减少树高和磁盘 I/O。
  2. 数据记录仅存于叶子节点：保证查询路径长度固定（从根节点到叶子节点）。
  3. 叶子节点形成有序双向链表：支持高效范围遍历。

B 树和 B+ 树的区别

特性B 树B+ 树
数据存储位置所有节点存储索引键 + 数据记录非叶子节点仅存索引键；数据记录存于叶子节点
分支因子较低（数据记录占用空间）极高（无数据记录占用）
范围查询效率低（需中序遍历，跨节点访问）极高（叶子节点链表直接遍历）
查询稳定性不稳定（数据可能在非叶子节点找到）稳定（必须访问叶子节点）

什么是聚集索引和二级索引？

在 InnoDB 存储引擎中，索引主要分为聚集索引 (Clustered Index) 和二级索引 (Secondary Index)。

  1. 聚集索引 (Clustered Index)

    • 定义: 叶子节点存储完整行数据，物理存储顺序与索引逻辑顺序一致。
    • 结构: 每张表有且仅有一个聚集索引。
    • 选择规则:
      1. 如果表定义了 PRIMARY KEY，则主键索引就是聚集索引。
      2. 如果没有 PRIMARY KEY，InnoDB 会选择第一个不包含 NULL 值的 UNIQUE 索引作为聚集索引。
      3. 如果以上两者都没有，InnoDB 会隐式地创建一个名为 GEN_CLUST_INDEX 的 6 字节隐藏主键作为聚集索引。
    • 叶子节点存储内容: 主键值 + 完整的行记录。

  2. 二级索引 (Secondary Index)

    • 定义: 二级索引，也称为非聚集索引。它的叶子节点不存储完整的行数据，而是存储索引键的值和对应记录的主键值。
    • 结构: 一张表可以拥有多个二级索引。
    • 叶子节点存储内容: 索引列的值 + 主键值。

什么是回表和索引覆盖？

这两个概念都与二级索引的使用密切相关。

  1. 回表 (Table Access by Index RowID)

    • 定义: 使用二级索引查询时，若所需列未完全覆盖，需用主键值回查聚集索引获取完整数据。这个再次查询聚集索引的过程，就称为“回表”。
    • 示例:
      -- age 列上存在二级索引
SELECT id, age, name FROM student WHERE age = 20;
    • 执行过程:
      1. 在 age 索引树中搜索 age = 20 的记录，找到对应的叶子节点。
      2. 从叶子节点中获取该记录的主键值 (例如 id = 101)。
      3. 使用获取到的主键值 101，回到主键索引 (聚集索引) 中进行查找。
      4. 在主键索引的叶子节点中找到 id = 101 的完整行记录，并从中读取 id, age, name 字段返回。
    • 影响: 回表操作需要进行两次索引查找，增加了额外的磁盘 I/O 和查询开销，应尽量避免。

  2. 索引覆盖 (Covering Index)

    • 定义: 当一个查询语句所需要获取的所有列数据，都恰好能从一个二级索引的叶子节点中直接获取时，就不再需要进行回表操作。这种情况就称为“索引覆盖”。
    • 示例:
      -- age 列上存在二级索引
SELECT id, age FROM student WHERE age = 20;
    • 执行过程:
      1. 在 age 索引树中搜索 age = 20 的记录，找到对应的叶子节点。
      2. 二级索引的叶子节点本身就存储了 age 和 主键 id 的值。查询所需的所有列 (id, age) 均已获取。
      3. 直接返回结果，无需回表查询主键索引。
    • 优势: 索引覆盖是一种高效的查询优化策略，它减少了查询主键索引的步骤，避免了回表带来的性能损耗，显著提升了查询效率。

索引失效

在 MySQL 中，如果查询优化器 (Optimizer) 判断使用索引的成本高于全表扫描，或者 WHERE 子句的用法不满足特定规则，就会导致索引失效，转而执行全表扫描。

常见的索引失效场景有哪些？

  1. 在索引列上进行计算、函数或类型转换

    • 描述: 对索引列进行任何形式的计算、函数调用（包括隐式类型转换）都会导致索引失效。因为索引保存的是原始值，对列进行操作后，索引树将无法直接用于查找。
    • 索引失效：
      • 索引使用表达式计算：SELECT * FROM user WHERE age + 10 = 30;
      • 索引使用函数：select * from t_user where length(name)=6;
      • 索引蕴含隐式类型转换: SELECT * FROM user WHERE phone = 18812345678; MySQL 会将字符串类型的 phone 字段转换为数字类型进行比较，相当于 CAST(phone AS signed)，这属于函数操作，导致索引失效。

  2. 违反联合索引的最左前缀法则 (Leftmost Prefix Rule)

    • 描述: 当创建一个联合索引，如 INDEX(col1, col2, col3) 时，查询必须从索引的最左侧列开始，并且不能跳过中间的列。
    • 原理: 联合索引的 B-Tree 结构是按照索引定义中的列顺序进行排序的。首先按 col1 排序，col1 相同时再按 col2 排序，以此类推。如果查询条件没有 col1，优化器将无法利用这个 B-Tree 结构来定位数据。
    • 示例: 对于 INDEX(a, b, c)：

      • 有效查询:

        • 使用 a：WHERE a = 1;
        • 使用 a, b：WHERE a = 1 AND b = 2;
        • 使用 a, b, c：WHERE a = 1 AND b = 2 AND c = 3;
        • 仅使用 a，因为 b 被跳过：WHERE a = 1 AND c = 3;

      • 失效查询:

        • 缺少最左侧的 a：WHERE b = 2;
        • 缺少最左侧的 a 和 b：WHERE c = 3;
        • 缺少最左侧的 a：WHERE b = 2 AND c = 3;

  3. 使用 LIKE 查询时以通配符开头

    • 描述: LIKE 查询如果以 % 或 _ 作为开头，索引将无法被利用。
    • 原理: B-Tree 索引是有序的，必须知道前缀才能进行范围查找。未知的前缀使得数据库无法定位到索引树中的起始点。
    • 示例:
      • 索引失效：SELECT * FROM user WHERE name LIKE '%name';
      • 索引有效：SELECT * FROM user WHERE name LIKE 'name%';

  4. 在 WHERE 子句中使用 OR 连接条件

    • 描述: 当 OR 条件的一侧是索引列，而另一侧是非索引列时，整个查询的索引将会失效。
    • 原理: 优化器认为，既然对非索引列的查询无论如何都需要进行全表扫描，那么不如直接对整个 OR 条件进行全表扫描。
    • 示例: 假设 id 是主键索引，age 是非索引列。
      • 索引失效（全表扫描）：SELECT * FROM user WHERE id = 1 OR age = 18;