MySQL索引原理与B+树结构

MySQL 是业务系统中最常见的数据库，但用好它并不容易。索引设计、SQL 优化、事务处理都是日常开发中需要关注的点。本文从实际场景出发，讲常见问题和解决思路。

一、为什么需要索引

#

1.1 无索引的查询代价

假设有一张用户表，包含100万条记录：

SELECT * FROM user WHERE id = 500000;

如果没有索引，MySQL需要逐行扫描（全表扫描），直到找到匹配记录。时间复杂度为O(n)。

#

1.2 索引的本质

索引是一种数据结构，用于快速定位数据。MySQL的InnoDB引擎使用B+树作为默认索引结构。

二、B树与B+树

#

2.1 二叉搜索树的局限

普通二叉搜索树在极端情况下会退化为链表，查找效率变为O(n)。即使使用AVL树或红黑树保持平衡，由于每个节点只存储一个关键字，当数据量巨大时，树的高度仍然很高，导致磁盘I/O次数过多。

#

2.2 B树（Balanced Tree）

B树是一种多路平衡搜索树，每个节点可以存储多个关键字：

• 每个节点最多有m个子节点（m阶B树）
• 除根节点外，每个节点至少有m/2个子节点
• 所有叶子节点在同一层

      [30, 60]
     /    |    \
[10,20] [40,50] [70,80]

B树的每个节点都存储数据，导致：

• 单个节点能存储的键值对减少
• 树的高度相对较高
• 范围查询需要中序遍历，效率低

#

2.3 B+树的优势

B+树是B树的改进版，也是MySQL索引的实际实现：

结构特点：

• 非叶子节点只存储键值，不存储数据
• 所有数据都存储在叶子节点
• 叶子节点之间通过指针相连，形成有序链表

        [30 | 60]
       /    |    \
 [10|20] [40|50] [70|80]  ← 非叶子节点（仅索引键）
   ↓       ↓       ↓
数据页    数据页    数据页  ← 叶子节点（存数据+索引键）
   ↕       ↕       ↕
双向链表连接

核心优势：

1. 更矮更胖：非叶子节点不存数据，单个节点容纳更多键，树高更低
2. 顺序访问：叶子节点链表连接，范围查询只需遍历链表
3. 稳定性能：所有查询都到达叶子节点，IO次数一致

三、InnoDB的B+树实现

#

3.1 页（Page）结构

InnoDB以页为单位管理数据，默认每页16KB：

+-----------------+
|  File Header    |  ← 38字节，页号、上一页、下一页
+-----------------+
|  Page Header    |  ← 56字节，页状态、记录数量
+-----------------+
|  Infimum        |  ← 最小虚拟记录
+-----------------+
|  Supremum       |  ← 最大虚拟记录
+-----------------+
|  User Records   |  ← 实际数据记录（按主键排序）
+-----------------+
|  Free Space     |  ← 空闲空间
+-----------------+
|  Page Directory |  ← 页目录，加速页内查找
+-----------------+
|  File Trailer   |  ← 校验和
+-----------------+

#

3.2 聚簇索引（Clustered Index）

InnoDB表数据本身就是按B+树组织的索引结构，称为聚簇索引：

• 叶子节点存储完整的行数据
• 数据按主键顺序物理存储

    主键B+树
       [10]
      /    \
   [3,7]   [15,20]
     ↓       ↓
+--------+ +--------+ +--------+
| id=3   | | id=10  | | id=15  |
| name=A | | name=B | | name=C |
| ...    | | ...    | | ...    |
+--------+ +--------+ +--------+

叶子节点 = 完整的数据行

特点：

• 一个表只能有一个聚簇索引（主键）
• 查询主键效率最高
• 插入按主键顺序最快（避免页分裂）

#

3.3 二级索引（Secondary Index）

非主键索引都是二级索引：

• 叶子节点存储：索引列 + 主键值
• 查询时需要”回表”：先查二级索引获取主键，再查聚簇索引获取完整数据

 name列的二级索引
     [Bob]
    /     \
[Alice]  [David]
   ↓        ↓
 id=3     id=15   ← 叶子存主键值
 
 回表查询：根据id=3再去聚簇索引查完整数据

#

3.4 覆盖索引

如果查询的所有列都在二级索引中，无需回表：

-- 假设有联合索引(name, age)
SELECT id, name, age FROM user WHERE name = 'Alice';
-- 覆盖索引，不回表

SELECT * FROM user WHERE name = 'Alice';
-- 需要回表查其他列

四、索引页分裂与合并

#

4.1 页分裂（Page Split）

当插入数据导致页满时，触发页分裂：

1. 申请一个新页
2. 将原页约一半数据移动到新页
3. 更新父节点的指针

插入前：
[1, 2, 3, 4, 5]  ← 页已满

插入6：
[1, 2, 3]  ← 原页
[4, 5, 6]  ← 新页

父节点新增指向新页的指针

性能影响：

• 页分裂涉及多个页的修改，成本较高
• 频繁页分裂导致页空间利用率降低（通常50%左右）
• 数据物理顺序变得不连续，影响顺序读性能

#

4.2 页合并（Page Merge）

删除数据导致页利用率过低时（默认低于50%），可能触发页合并：

删除前：
Page A: [1, 2, 3]      ← 3条记录
Page B: [4, 5]         ← 2条记录，利用率低

删除后合并：
Page A: [1, 2, 3, 5]   ← 合并后
Page B: 空闲           ← 归还到空闲列表

#

4.3 顺序主键的优势

使用自增ID作为主键：

• 新数据总是追加到最后一页
• 几乎不会发生页分裂
• 数据物理连续，顺序读取效率高

使用UUID作为主键：

• 插入位置随机
• 频繁触发页分裂
• 数据物理分散，随机IO多

五、索引的物理存储

#

5.1 表空间文件

InnoDB数据存储在表空间文件中：

ibdata1          # 系统表空间（共享）
user.ibd         # 独立表空间（每张表一个文件，推荐）

配置独立表空间：

[mysqld]
innodb_file_per_table = ON

#

5.2 索引与数据的关系

-- 查看表空间信息
SELECT * FROM information_schema.innodb_sys_tablespaces 
WHERE name = 'database/user';

#

5.3 索引高度估算

假设：

• 页大小：16KB
• 主键类型：BIGINT（8字节）
• 指针大小：6字节
• 每行数据：1KB

非叶子节点：

• 每个键值对大小：8 + 6 = 14字节
• 每页可容纳：16KB / 14B ≈ 1170个键

叶子节点：

• 每页可容纳：16KB / 1KB = 16条记录

树高计算：

• 高度1（根节点）：1170个指针
• 高度2：1170 × 1170 = 136万指针
• 高度3：1170 × 1170 × 16 ≈ 2190万条记录

结论：2000万数据的表，树高通常只有3层，最多3次IO即可定位数据。

六、索引使用最佳实践

#

6.1 选择合适的列建索引

适合建索引的列：

• WHERE条件中频繁使用的列
• JOIN关联条件中的列
• ORDER BY / GROUP BY的列
• 区分度高的列（唯一值比例高）

不适合建索引的列：

• 区分度极低的列（如性别）
• 频繁更新的列（维护索引成本高）
• 小表（全表扫描更快）
• 很长的字符串列

#

6.2 索引设计原则

1. 最左前缀原则：联合索引(a,b,c)，查询条件必须包含最左边的列
2. 避免冗余索引：已有(a,b)，不需要单独的(a)
3. 控制索引数量：单表不超过5个索引，索引过多影响写入性能
4. 优先使用覆盖索引：减少回表次数

#

6.3 索引失效场景

-- 1. 使用函数
WHERE YEAR(create_time) = 2024   -- 失效
WHERE create_time >= '2024-01-01' AND create_time < '2025-01-01'  -- 有效

-- 2. 类型转换
WHERE user_id = '123'   -- user_id是int，发生隐式转换，失效
WHERE user_id = 123     -- 有效

-- 3. 使用NOT、<>、!=
WHERE status <> 1   -- 可能失效（取决于数据分布）

-- 4. LIKE以%开头
WHERE name LIKE '%张%'   -- 失效
WHERE name LIKE '张%'    -- 有效（用到索引）

-- 5. OR条件
WHERE id = 1 OR name = 'a'   -- name无索引时，id索引也失效

七、查看索引信息

#

7.1 查看表索引

SHOW INDEX FROM user;

#

7.2 查看索引统计

-- 查看索引 cardinality（区分度）
SHOW INDEX FROM user \G;

-- Cardinality越高，索引区分度越好
-- Cardinality / 总行数 接近1表示区分度好

#

7.3 分析索引使用情况

-- 查看查询是否使用索引
EXPLAIN SELECT * FROM user WHERE name = 'Alice';

-- 查看索引大小
SELECT 
    index_name,
    ROUND(stat_value * @@innodb_page_size / 1024 / 1024, 2) AS size_mb
FROM mysql.innodb_index_stats
WHERE table_name = 'user';

八、总结

概念	说明
B+树	多路平衡树，非叶子节点只存键，叶子节点存数据并双向链表连接
聚簇索引	数据与索引在一起，叶子节点存完整行数据，按主键排序
二级索引	叶子节点存索引列+主键，需要回表
覆盖索引	查询列全在索引中，无需回表
页分裂	页满时分裂成两页，影响插入性能
页合并	页利用率过低时合并，回收空间

理解B+树的结构特点，有助于：

• 合理设计表结构和主键
• 优化索引设计
• 写出高效SQL
• 诊断性能问题

核心要点

1. 索引设计的原则：最左前缀原则、避免索引列参与计算、选择合适的索引类型

2. SQL 优化的方法：使用 EXPLAIN 分析执行计划、避免 SELECT *、优化 JOIN

3. 事务隔离级别的选择：根据业务需求选择合适的级别

4. 常见的锁问题：行锁、表锁、死锁的处理

总结

MySQL 优化是一个持续的过程，需要结合业务特点和数据量来调整。在实际项目中，定期分析慢查询日志、优化索引、调整配置参数，都能提升数据库性能。