文章目录前言1. 为什么需要索引2. 索引底层数据结构演化2.1 二叉搜索数BST2.2 平衡二叉树AVL2.3 红黑树2.4 Hash 表2.5 B树2.6 B 数❗Mysql使用为什么 InnoDB 选择 B 树3. InnoDB索引机制3.1 聚簇索引主键索引3.2 二级索引辅助索引3.3 回表查询3.4 覆盖索引4. 索引分类4.1 主键索引4.2 唯一索引4.3 普通索引4.4 联合索引结语前言在数据库中随着数据量增长查询效率会急剧下降。例如SELECT*FROMuserWHEREid1;如果没有索引数据库只能进行全表扫描Full Table Scan逐行匹配数据当数据达到百万级甚至千万级时查询性能会显著下降。因此数据库引入了索引机制。索引的本质帮助数据库快速定位数据的数据结构。1. 为什么需要索引索引在数据库中扮演着“目录“的角色。想象一本没有目录的厚书你要找某个知识点只能一页页翻而有了目录直接定位到章节即可。具体来说索引带来的好处有大幅提升查询速度对于WHERE、JOIN、ORDER BY、GROUP BY等操作索引能减少扫描的数据量从全表 O(n) 降到 O(log n) 甚至更低。减少磁盘 I/O数据库数据存储在磁盘上没有索引时可能产生大量随机 I/O索引结构如 B 树能将随机 I/O 转为顺序 I/O或大幅减少 I/O 次数。唯一性约束唯一索引可以保证表中某列或列组合的值不重复。辅助排序与分组索引本身已经有序可以避免额外的 filesort 操作。当然索引也有代价占用额外的存储空间。增、删、改数据时需要同步维护索引降低写入性能。不合理的索引可能被优化器忽略甚至拖慢查询。因此索引需要根据查询模式合理设计并非越多越好。2. 索引底层数据结构演化2.1 二叉搜索数BSTBST的特点每个节点的左子树中所有节点的值都小于该节点每个节点的右子树中所有节点的值都大于该节点左右子树本身也是 BST这一规则保证了左小右大使得每次比较都能排除一半的候选范围所以BST的效率非常高。但BST存在一个致命问题如果插入顺序是1、2、3、4、5树就会变为这时查找数据只能全部遍历复杂度变为O(n)性能崩了。2.2 平衡二叉树AVLAVL 是第一种字平衡二叉搜索树它规定任意节点左右子树高度差(平衡因子)不能超过1从而实现树的平衡。在每次插入或删除操作后会从受影响的节点向上回溯检查平衡因子左高 - 右高。若平衡因子绝对值大于 1则通过旋转操作恢复平衡左旋、右旋、左右双旋、右左双旋。AVL 的特点查询效率稳定严格平衡使得树高保持在 O(log n)查找、插入、删除均为 O(log n)。适合读多写少的场景因为维持平衡的旋转成本较高频繁插入删除会导致多次旋转。每个节点存储一个高度值或平衡因子额外占用少量空间。插入顺序2/5/6/3/1/4AVL虽然解决了 BST 的退化问题但仍然是二叉树。当数据量巨大千万级时树高约为 log₂(10⁷) ≈ 24 层查询一个数据可能需要 24 次磁盘 I/O每次 I/O 都很慢。数据库索引需要更“矮胖”的结构以减少 I/O 次数。因此 AVL 并未被主流数据库采用为索引结构。2.3 红黑树红黑树也是一种自平衡二叉搜索树但它不追求 AVL 那样的“绝对平衡”而是保证从根到叶子的最长路径不超过最短路径的 2 倍从而近似平衡。在每次- 插入或删除后通过变色和旋转左旋/右旋来恢复规则。红黑树的五条规则每个节点是红色或黑色。根节点是黑色。所有叶子节点NIL 空节点是黑色。红色节点的两个子节点必须是黑色即不能有连续的两个红色节点。从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点黑高一致。插入顺序2/5/6/3/1/4红黑树 vs AVL特性AVL红黑树平衡性严格高度差 ≤1松散最长路径≤2倍最短路径查询性能更快更矮稍慢略高插入/删除性能多次旋转较慢变色少量旋转较快适用场景读多写少读写相当如 Java HashMap、Linux CFS为什么数据库不用红黑树红黑树仍然是二叉树树高较高I/O 次数多。此外红黑树不擅长范围查询——需要中序遍历回溯效率低。因此它只适用于内存中的数据结构如 TreeMap、TreeSet不适合磁盘索引。2.4 Hash 表Hash 表散列表是另一种常见的数据结构通过哈希函数将键映射到数组中的某个位置实现 O(1) 的等值查询。Hash 索引的特点查询极快只需一次哈希计算 一次定位等值查询复杂度 O(1)。不支持范围查询哈希映射是随机的数据在物理上无序无法进行 BETWEEN等操作。哈希冲突不同键计算出相同哈希值需要通过拉链法、开放寻址法等解决冲突多了性能下降。不支持排序无法利用索引做ORDER BY。无法利用前缀查找对LIKE abc%无效因为哈希是对完整键值计算的。2.5 B树B 树也称 B- 树全称为多路平衡查找树B 树是 B 树的一种变体。B 树和 B 树中的 B 是Balanced平衡的意思。目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 BTree 作为索引结构B-树的特点每个节点既存索引键也存完整数据节点内键值有序排列所有叶子节点在同一层保持绝对平衡一个节点可以有多个子节点M阶B树最多M个子节点非叶子节点的键值将子树分隔开遵循左小右大查找过程从根节点开始每层做二分查找一旦命中就立刻返回不需要走到叶子节点。2.6 B 数❗Mysql使用MySQL 与 B 树没有直接关系和 B 树有直接关系的是MySQL的默认存储引擎InnoDB而 InnoDB 默认使用B Tree。除 InnoDB 外MySQL还支持其他存储引擎如MyISAM。B 树的特点所有数据存储在叶子结点非叶子节点只存键值叶子节点通过双向链表连接范围查询效率极高非叶子节点的键会在叶子节点中重复出现树高通常只有3~4层I/O 次数极少查询过程从根节点出发递归向下经过内部节点到达叶子节点完成查找。B树与B树的对比对比维度B树B树数据存储位置所有节点存储数据只有叶子节点存数据非叶子节点存键 数据只存键占用空间小叶子节点链表没有双向链表连接查找路径命中即返回路径不固定必须到叶子节点路径固定范围查询需要中序遍历效率低直接走链表效率极高等值查询最好情况根节点命中更快固定走到叶子稍慢树的高度相对较高相对较矮IO 次数较多较少稳定性不稳定层数不同稳定都到叶子为什么 InnoDB 选择 B 树磁盘 I/O 更少非叶子节点不存数据一个磁盘块可存储大量键分叉因子极大树高通常 3~4 层千万数据也只需 3~4 次 I/O。范围查询高效叶子链表使得BETWEEN、、、ORDER BY等只需遍历叶子节点无需回溯。全表扫描更友好直接遍历叶子链表即可相当于顺序读磁盘。数据存储稳定所有数据都在叶子查询任何记录的 I/O 次数相同性能可预测。3. InnoDB索引机制前面介绍了 BTree 以及索引的数据结构那么在 MySQL 中索引到底是如何存储的在 MySQL 的 InnoDB 存储引擎中索引并不是独立存在的而是以BTree的形式组织数据并且根据存储内容的不同分为聚簇索引Clustered Index二级索引Secondary Index理解这两者的区别是掌握 MySQL 索引底层原理的关键。3.1 聚簇索引主键索引聚簇索引是指数据和索引存储在一起在InnoDB中主键索引就是聚簇索引它的叶子节点保存的不是地址而是完整的数据行。例如创建如下表结构CREATETABLEuser(idINTPRIMARYKEY,nameVARCHAR(50),ageINT);假设user表中的数据有idnameage1Tom183Jack225Alice20聚簇索引的B Tree结构就是聚簇索引具有以下特点主键有序存储因为B Tree 天然有序所以执行语句SELECT*FROMuserORDERBYid;执行效率较高。查询速度快执行参训语句SELECT*FROMuserWHEREid3;只需要一次 BTree 查找即可定位完整数据。时间复杂度为O(logN)。注意主键不能太大因为二级索引叶子节点保存的是主键值如果主键越大不仅索引占用的空间越大还会导致io越多从而查询性能下降。推荐采用自增长主键BIGINT AUTO_INCREMENT不推荐UUID。因为UUID长度较大且无序容易导致 BTree 页分裂影响插入性能与索引效率。3.2 二级索引辅助索引除了主键外创建的索引都叫二级索引。例如在user表的name字段上创建一个名为idx_name的 B 树索引。sql语句如下CREATEINDEXidx_nameONuser(name);此时idx_name的结构为此时叶子节点保存的是(name, id)而非(name, age)因为真正的数据在聚簇索引中二级索引只是记录主键值。如何获取数据答案是回表查询。3.3 回表查询既然二级索引只保存主键值那么查询完整数据时还需要再查一次聚簇索引。这个过程就叫回表。例如SELECT*FROMuserWHEREnameJack;它背后的执行流程是第一步先走二级索引name Jack获取主键id 3第二步再走聚簇索引id 3找完整数据。这就是回表查询比之主键索引查询二级索引查询多查了一次B Tree 所以二级索引查询通常比主键索引慢。主键索引 VS 二级索引对比项主键索引聚簇索引二级索引辅助索引创建方式定义 PRIMARY KEY 时自动创建必须手动CREATE INDEX树结构1 棵 B 树每建一个索引就多 1 棵独立 B 树叶子节点存储整行完整数据(索引列值主键 ID)查询完整数据直接读取无需回表需要回表查主键索引一个表有多少个只能有 1 个可以有多个增删改效率只维护一棵树相对快每多一个索引写入就更慢占用空间存储所有真实数据只存索引列 主键空间较小适用场景按主键查询、获取完整数据按非主键字段name/age/phone查询3.4 覆盖索引有没有办法不回表如果查询字段都存在与索引中那么就不需要回表。这就是覆盖索引。假设已经建立了索引INDEX(name)执行SELECTnameFROMuserWHEREnameJack;因为二级索引叶子节点本身存(name, id)查询的字段name已经包含在索引中所以不需要回表。而执行SELECTname,ageFROMuserWHEREnameJack;由于age不在索引中所以必须回表。如果想减少io提升性能那么建立联合索引INDEX(name, age)也可以直接走覆盖索引无需回表。覆盖索引的应用场景有统计数量SELECTCOUNT(name)FROMuserWHEREnameJack;范围查询SELECTnameFROMuserWHEREnameLIKEJ%;不需要回表纯索引查询性能很高。二级索引 VS 覆盖索引对比项二级索引覆盖索引本质一种索引结构一种查询效果 / 优化状态是否独立存在是独立的 B 树不是独立索引是二级索引的一种理想使用场景叶子节点存储(索引列, 主键ID)依然是(索引列, 主键ID)或联合索引多存几个字段查询必须回表必须回表拿完整数据完全不回表查询速度较快多一次回表 I/O极快少一次 I/O满足条件只要创建索引就成立查询的所有字段都在索引里才成立例子INDEX(name)SELECT name FROM user WHERE namexxx核心作用加速 WHERE 条件查找避免回表极致提升查询性能4. 索引分类从业务角度来看MySQL 中常见索引有主键索引唯一索引普通索引联合索引4.1 主键索引主键索引起到了唯一标识一条数据的作用它的特点是唯一、不允许为NULL、一张表只能有一个。例如CREATETABLEuser(idINTPRIMARYKEY);# 等价于# PRIMARY KEY(id)在 InnoDB 中 主键索引就是聚簇索引。4.2 唯一索引唯一索引要求值必须唯一但可以为NULL。例如要求user表邮箱表唯一CREATEUNIQUEINDEXidx_emailONuser(email);4.3 普通索引普通索引是最基础的索引它的唯一作用就是提高查询速度。它允许值重复允许值为NULL。例如CREATEINDEXidx_nameONuser(name);适用于高频查询字段。4.4 联合索引联合索引即多列共同组成一个索引联合索引并不等于覆盖索引但联合索引更容易形成覆盖索引从而减少回表查询。例如INDEX(name,age,city)这条语句底层排序规则是先按照name排序。name相同再按age排序。age相同再按city排序。例如(Alice,18,Beijing) (Alice,20,Shanghai) (Bob,19,Hangzhou)所以下面SQL能命中WHEREnameAlice也能命中WHEREnameAliceANDage18但WHEREage18❗通常无法命中。原因是MySQL遵循最左前缀原则即必须从最左边开始匹配。例如索引(name, age, city)可用name、(name, age)、(name, age, city)不能直接age city (age, city)。详细讲解将在后续第五节展开。结语索引的本质是一种帮助数据库快速定位数据的数据结构。从最开始的 BST到解决退化问题的 AVL、红黑树再到最终适用于磁盘存储的 BTree我们可以发现数据库索引的设计核心始终是在查询效率、磁盘 I/O、范围检索、写入成本之间寻找平衡。而在 MySQL 的 InnoDB 中索引并不只是一个“加速器”它本身就是数据的组织方式主键索引聚簇索引决定数据如何存储二级索引通过主键关联数据回表查询影响查询成本覆盖索引能够进一步减少 I/O 开销但真正决定索引性能的并不仅仅是“有没有索引”而是索引是否建得合理SQL 是否真正命中了索引。很多线上慢查询问题本质上不是数据库性能差而是索引设计不合理、联合索引使用错误、或者索引发生了失效。下一篇我们将正式进入 MySQL 索引中最容易出问题、也是面试高频考点之一联合索引与最左前缀原则为什么索引建了却不生效