索引数据结构与算法：B+树索引原理，聚簇索引与非聚簇索引，索引下推与覆盖索引

大家好，我是你们的老朋友。今天我们来聊聊索引，这玩意儿可以说是MySQL性能优化的「心脏」。很多同学觉得索引就是快，但到底快在哪？为什么有时候加了索引反而慢？

我个人习惯是，先搞懂底层数据结构，再去谈优化。不然你调了半天参数，可能连方向都是错的。咱们今天就把B+树、聚簇索引、非聚簇索引、索引下推、覆盖索引这几个硬骨头啃下来。

一、B+树索引原理：为什么MySQL选了它？

先问个问题：为什么MySQL的InnoDB引擎选择了B+树，而不是二叉树、红黑树或者哈希表？

你想想看，数据库的数据是存在磁盘上的。磁盘读写一次，那叫一个慢——比内存慢几个数量级。所以我们的核心目标就是：尽量减少磁盘I/O次数。

二叉树呢？每个节点只存一个数据，树的高度太高了。比如100万条数据，二叉树的高度大概在20层左右。查一次数据要读20次磁盘，这谁受得了？

红黑树虽然平衡，但本质还是二叉树，高度问题没解决。

哈希表呢？等值查询确实快，O(1)的复杂度。但范围查询就废了——比如查「age > 20」，哈希表得全表扫描。

所以B+树登场了。它的核心设计是：

  • 非叶子节点只存索引，不存数据。这样每个节点能存更多的索引项，树的高度就矮了。一般3-4层就能搞定千万级数据。
  • 叶子节点存数据，并且用双向链表串联。这意味着范围查询特别爽——找到起点后，顺着链表往后读就行了。
  • 节点大小默认16KB。这个设计很巧妙，一次磁盘I/O刚好读一个节点，效率最大化。

核心结论：B+树用「矮胖」的结构，把磁盘I/O次数降到了极致。3层B+树，查任何数据最多读3次磁盘。这就是它成为MySQL默认索引的原因。

我记得有一次接手一个慢查询项目，表里2000万数据，查询要5秒。一看索引，用的是哈希索引。改成B+树后，查询降到了20毫秒。嗯，这就是数据结构的威力。

二、聚簇索引与非聚簇索引：一个表只能有一个

InnoDB里，聚簇索引和非聚簇索引的区别，说白了就是一句话：数据到底跟索引放在一起，还是分开存放。

2.1 聚簇索引

聚簇索引的叶子节点直接存了整行数据。InnoDB里，主键索引就是聚簇索引。

特点：

  • 一个表只能有一个聚簇索引（因为数据只能有一份）
  • 如果没有定义主键，InnoDB会选一个唯一的非空列作为聚簇索引
  • 如果连这个都没有，InnoDB会隐式生成一个6字节的row_id作为聚簇索引

我在项目中遇到过一个问题：有个表用了UUID作为主键。结果插入数据时，磁盘I/O飙升，写入性能极差。为什么？因为UUID是随机的，新数据要插入到B+树的中间位置，导致频繁的页分裂。后来改成自增ID，写入性能直接翻倍。

避坑指南：我曾经见过一个项目，主键用UUID，结果表才500万数据，索引碎片率高达40%。后来重建表，改成自增ID，空间节省了30%，查询快了50%。所以，主键尽量用自增ID，别用UUID。

2.2 非聚簇索引（二级索引）

非聚簇索引的叶子节点不存数据，只存主键值。所以通过非聚簇索引查询时，需要先找到主键，再回表查数据。这个过程叫「回表查询」。

举个例子：

-- 假设表结构
CREATE TABLE user (
    id INT PRIMARY KEY,
    name VARCHAR(50),
    age INT,
    INDEX idx_age (age)
);

-- 查询语句
SELECT * FROM user WHERE age = 25;

执行流程：

  1. 通过idx_age索引找到age=25的叶子节点，拿到主键id
  2. 用主键id回聚簇索引，找到完整数据行

这里有个关键点：非聚簇索引的叶子节点存的是主键值，不是数据行地址。为什么？因为数据行可能会移动（比如页分裂），如果存地址，地址变了所有索引都得更新。存主键值就稳了，主键不变就行。

三、覆盖索引：少一次回表，快一倍

覆盖索引，说白了就是：查询需要的所有字段，都在索引里找到了，不需要回表。

还是上面那个例子：

-- 这个查询需要回表
SELECT * FROM user WHERE age = 25;

-- 这个查询不需要回表（覆盖索引）
SELECT id, age FROM user WHERE age = 25;

第二个查询为什么快？因为idx_age索引的叶子节点里，已经存了id和age两个字段。查询直接返回，不用再去聚簇索引里找其他字段。

实战技巧：我建议你在设计索引时，尽量把查询频繁的字段都包含进去。比如经常查「根据年龄查姓名」，可以建一个联合索引(age, name)。这样查询SELECT name FROM user WHERE age = 25就能走覆盖索引，性能杠杠的。

覆盖索引的好处：

  • 减少磁盘I/O（少一次回表）
  • 减少内存消耗（索引通常比数据小）
  • 减少CPU开销（少一次B+树搜索）

四、索引下推：MySQL 5.6的隐藏福利

索引下推（Index Condition Pushdown，ICP）是MySQL 5.6引入的优化。它的核心思想是：在索引遍历过程中，提前过滤掉不满足条件的记录，减少回表次数。

没有ICP时，查询流程是这样的：

  1. 通过索引找到所有满足索引条件的记录
  2. 回表获取完整数据
  3. 在Server层过滤其他条件

有ICP时：

  1. 通过索引找到记录
  2. 在索引层面直接过滤其他条件
  3. 只有满足所有条件的记录才回表

举个例子：

-- 联合索引 (name, age)
SELECT * FROM user WHERE name LIKE '张%' AND age = 25;

没有ICP：先通过name找到所有姓张的记录（可能很多），然后回表，再过滤age=25。

有ICP：在索引遍历时，同时检查age=25，只有满足条件的才回表。回表次数大大减少。

我的经验：索引下推对联合索引的「中间断档」查询特别有效。比如联合索引(a, b, c)，查询条件是a=1 AND c=2。没有ICP时，只能通过a=1找到一堆记录，回表后再过滤c=2。有ICP时，在索引层面就把c=2过滤了，回表次数可能减少90%以上。

怎么确认ICP生效了？看执行计划：

EXPLAIN SELECT * FROM user WHERE name LIKE '张%' AND age = 25;
-- 如果Extra列显示 "Using index condition"，说明ICP生效了

五、总结：面试官最爱问的对比

特性 聚簇索引 非聚簇索引
叶子节点内容 完整数据行 主键值
表数量 只能1个 可以多个
查询方式 直接返回数据 需要回表
适用场景 主键查询、范围查询 非主键查询、排序、分组

最后说一句：索引不是越多越好。每个索引都会占用磁盘空间，而且写入数据时要维护所有索引，会拖慢写入性能。我见过一个表建了12个索引，结果写入慢得像蜗牛。嗯，适度才是王道。

好了，这一章就到这里。下一章我们聊聊「索引失效的十大场景」，都是我在实战中踩过的坑，保证让你少走弯路。

← 上一章 📖 返回目录 下一章 →