逐道-Ethan.Yang
逐道-Ethan.Yang

# 索引深入解析

作者：Ethan.Yang
博客：https://blog.ethanyang.cn (opens new window)

# 索引是什么?

在数据库中，**索引（Index）**相当于书籍的目录，它可以加快我们查找数据的速度。实际应用中，索引对查询性能的提升可以达到几十倍甚至上百倍。

举例说明

select * from user where name='张三'
1

如果 name 字段没有加索引，那么 InnoDB 会进行全表扫描，逐行比较，性能极低。

如果 name 字段加了索引，InnoDB 会根据 B+ 树索引结构快速定位目标行，无需扫描整个表，查询效率显著提升。

底层本质：磁盘结构

数据库的数据是以页（Page）为单位存储在磁盘文件中的，每一行数据在磁盘中都有一个地址（Row ID 或主键 ID）。 有了索引后，MySQL 会先从索引树中找到对应主键，然后再根据主键到表中定位数据行，避免全表扫描。

# InnoDB 索引类型

InnoDB 中支持多种索引，常见的有：

索引类型 描述
普通索引（Normal） 最基本的索引类型，对字段无唯一性要求。
唯一索引（Unique） 要求索引列的值必须唯一。主键也是一种唯一索引，但不允许为 NULL。
全文索引（Fulltext） 用于对大文本字段（如文章内容、评论等）进行高效全文搜索，适合替代 LIKE '%关键字%' 的低效查询。InnoDB 从 MySQL 5.6 开始支持全文索引。

# 索引存储类型推演

索引还有一种Hash结构, 用的较少, 主要讲解B+树, Hash一般不支持顺序的范围查找

# 从二分查找开始：静态数组查找

结构：

  • 一个升序数组，通过 二分法进行查找。

优点：

  • 查找效率高：时间复杂度 O(log n)。

缺点：

  • 插入/删除代价大：时间复杂度 O(n)，因为需要移动数组元素。
  • 静态结构：不适合频繁增删操作。
  • 只能全量加载进内存，不适合磁盘管理的大数据量场景。

# 二叉查找树（Binary Search Tree, BST）

结构：

  • 每个节点最多有两个子节点。
  • 左子树 < 根节点 < 右子树。

优点：

  • 插入、删除、查找：平均 O(log n)。
  • 动态结构，适合频繁变更数据。

缺点：

  • 极端情况下（如插入升序序列）会退化成链表，性能降为 O(n)。
  • 不平衡问题严重，必须引入自平衡机制。

# 红黑树（Red-Black Tree）：内存平衡查找结构

结构：

  • 一种自平衡的二叉查找树，通过红黑节点颜色规则，保证近似平衡。

优点：

  • 查找、插入、删除都是 O(log n)。
  • 保证树的最长路径不超过最短路径的两倍，避免性能恶化。
  • 广泛用于内存结构：如 Java 的 TreeMap、C++ STL 的 map。

缺点（对比 B+ 树）：

特性 红黑树 B+ 树
节点分布 节点少，树高 节点多，树矮
数据位置 所有节点都有 data 只有叶子节点存 data
顺序遍历 中序遍历效率低 叶子节点链表，范围查询高效
扇出能力 2 分支 上百分支
IO 次数 高 低，极大减少磁盘 IO
磁盘友好 ❌ ✅ 非常友好，天然磁盘设计

🔍 总结：红黑树适合内存结构，但在磁盘中查找数据，访问节点意味着一次磁盘 IO，所以红黑树会频繁地做磁盘 IO，效率不高。

# B 树（Balanced Tree）

结构：

  • 多路查找树，每个节点可有多个 key 和多个子树。
  • 所有叶子节点深度相同（平衡）。
  • 节点中包含 key 和 data。

优点：

  • 每个节点对应一个磁盘页（通常 4K），一次磁盘 IO 可以加载多个 key。
  • 由于扇出（每层分支数）大，树的高度低，减少了 IO 次数。

缺点：

  • 每个节点都存储 data，导致中间节点比较重，扇出降低。
  • 范围查询效率不高：必须中序遍历树。

# B+ 树：MySQL 的核心选择

结构：

  • B 树的升级版。
  • 所有实际数据只存储在叶子节点，中间节点只存 key。
  • 所有叶子节点通过指针组成链表，形成一个有序的数据层。

B+ 树优点（也是 MySQL 使用它的原因）：

特性 优势说明
磁盘 IO 少 扇出大（每页能存更多 key），树更矮。磁盘读取层数更少。
范围查询高效 所有 data 在叶子，叶子节点链表结构，一次扫描即可。
内存/磁盘友好 中间节点不带 data，结构稳定，支持高并发查询。
查找效率稳定 所有查找都在叶子节点结束，查询路径固定，有助于预测和优化缓存。

# 举个例子（对比红黑树 vs B+ 树）

假设：

  • 每个节点一个磁盘页为 4KB。
  • key 为 8B，指针为 8B。

B+ 树一个节点能容纳的 key 数：

一个节点 ≈ 4KB = 4096B
一个 key + pointer = 8 + 8 = 16B
4096 / 16 ≈ 256 个 key
1
2
3

即：每层最多分成 256 个分支，高度极低：

  • 256^1 = 256 条记录
  • 256^2 = 65,536 条记录
  • 256^3 = 16,777,216 条记录（只需 3 层）
  • 256^4 = 4,294,967,296（40 亿+记录，仅需 4 次磁盘 IO）

而红黑树每次查找最多访问 log₂(n) 个节点：

  • 40 亿数据需要大约 log₂(4e9) ≈ 32 次 IO，性能远逊于 B+ 树。

# InnoDB 中 B+Tree 的具体实现

在 InnoDB 存储引擎中：

  • 每个索引都会对应一棵 B+ 树。
  • 数据表中默认存在一个 主键索引（聚簇索引），即一级索引。
  • 每创建一个非主键的普通索引，都会额外创建一棵 二级索引（辅助索引），即二级 B+ 树。

# 一级索引（主键索引）与二级索引的区别：

项目 一级索引（主键） 二级索引（普通索引）
B+ 树结构 一棵B+树 每个索引一棵独立的B+树
叶子节点存储 整行数据 主键值
是否回表 ❌ 不需要 ✅ 需要回表（除非覆盖索引）

# 为什么叶子节点存的是主键值而不是行地址？

  • InnoDB 不存储物理地址，而是统一通过 主键索引树（聚簇索引）来定位数据行。
  • 避免地址变化、提升一致性，方便事务和 MVCC 管理。

无论表中有没有显示索引, 表都是一个B+树结构, 会有默认索引, 而全表扫描本质上是对B+树叶子节点从左到右的扫描, 比如name是非索引字段, 但是where上有name, 那么就会根据默认的B+树叶子节点挨个扫描, 再逐个判断name字段和where上的是否一致

# 举一个例子

CREATE TABLE user (
  id BIGINT PRIMARY KEY,        -- 主键索引（聚簇索引）
  name VARCHAR(100),            -- 普通字段
  age INT,
  INDEX idx_name(name),         -- 二级索引
  INDEX idx_age(age)            -- 二级索引
);

INSERT INTO user (id, name, age) VALUES (1, 'Tom', 20);
INSERT INTO user (id, name, age) VALUES (2, 'Bob', 25);
INSERT INTO user (id, name, age) VALUES (3, 'Amy', 22);

-- 假设叶子节点每页容量为2条记录
-- 字符串大小比较使用InnoDB内部算法进行排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

  1. 按主键查询（聚簇索引）

    select * from test where id = 2
    1

    • 直接访问聚簇索引，无需回表

    • 查询流程：

      1. 从根节点 [2] 导航到叶子节点

      2. 叶子节点存 [1, Tom, 20] 和 [2, Bob, 25]

      3. 通过叶子节点顺序查找或双向链表找到 id=2

    • 最终返回记录：2, 'Bob', 25按照age / name 索引查询

  2. 按二级索引查询

    SELECT * FROM user WHERE name = 'Tom';
    1

    • 查询流程：

      1. 在二级索引 idx_name 中查找 Tom → 得到主键 id=1
      2. 使用 id=1 回表访问聚簇索引
      3. 在聚簇索引叶子节点找到完整记录 [1, 'Tom', 20]

    • 最终返回记录：1, 'Tom', 20

# MySQL InnoDB 索引的使用最佳实践

  1. 主键索引设计 主键叶子节点存储完整数据，应选用稳定、递增的字段（如自增 ID）避免页分裂。

  2. 根据查询频率建立索引 WHERE、JOIN、ORDER BY、GROUP BY 中频繁出现的字段适合建索引，提升查询性能。

  3. 使用覆盖索引避免回表 查询字段全在索引中，无需回表，查询更快。

    # 对 (name, age) 建联合索引：
SELECT name, age FROM user WHERE name = 'Tom';
    1
    2

  4. 对长字符串使用前缀索引 长字符串字段如邮箱、URL，用前 N 位建索引，节省空间。

    CREATE TABLE user (
  id INT PRIMARY KEY,
  email VARCHAR(255),
  ...
);
# 只给前10位建立索引
CREATE INDEX idx_email_prefix ON user(email(10));
    1
    2
    3
    4
    5
    6
    7

  5. 合理使用联合索引 多字段建联合索引时，查询条件需从最左列开始，否则索引失效。

  6. 选择高基数字段建索引 唯一值越多，过滤能力越强。避免单独索引性别、状态等低基数字段。 以性别为例, 就算走了性别的索引, 1000w条中还是会有500w条是男或者女, 还是要扫描500w次

  7. 避免函数/表达式影响索引使用 避免在索引列上使用函数、表达式或计算（如 WHERE YEAR(date) = 2023 或 age + 1 = 30），否则索引失效。尽量写成直接条件（如 date BETWEEN '2023-01-01' AND '2023-12-31'，age = 29）。

  8. LIKE查询注意使用方式 LIKE 'abc%' 可以使用索引，LIKE '%abc' 无法利用索引，因为前缀模糊匹配无法排序访问。

# MySQL索引失效的常见场景

  1. 函数或表达式包裹索引列 如果在索引列上使用了函数，如 UPPER(name) = 'BOB' 或 DATE(create_time) = '2024-01-01'，MySQL无法利用索引。

  2. 隐式类型转换导致失效 比如索引列是字符串类型，但查询条件用了数字，MySQL会做隐式转换，导致索引失效。

  3. 不等于操作符 WHERE col <> 1 或 WHERE col != 1 这类操作不会使用索引，通常会触发全表扫描。

  4. OR 条件未命中索引 WHERE col1 = 1 OR col2 = 2，如果这两个条件没有都使用索引，可能导致索引失效。

  5. 范围查询后不能使用索引列 对联合索引来说，如果使用了范围条件（如 >、<、BETWEEN）后，联合索引后续的列就无法利用索引。

​ 例如联合索引是 (a, b, c)，条件是 WHERE a > 1 AND b = 2，索引只能用到 a，b 列索引失效。

  1. 前缀模糊查询失效 LIKE '%abc' 因为以通配符开头，无法利用索引。

  2. 索引列允许 NULL 查询 部分情况下用 IS NULL 或 IS NOT NULL 可能导致索引失效，尤其是在老版本 MySQL 中。

  3. 过多索引导致维护成本高 虽然不是“失效”，但过多索引会导致写入（INSERT/UPDATE/DELETE）时维护索引开销过大，影响性能。

← 事务 →