MySQL 索引的底层数据结构详解

大纲

• MySQL 锁的使用
• MySQL 索引的使用
• MySQL 索引的底层数据结构详解
• MySQL 索引的最左前缀原则详解

索引的介绍

索引概述

MySQL 官方对索引的定义为：索引（Index）是帮助 MySQL 高效获取数据的数据结构。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。简而言之，索引的本质是数据结构。

索引结构

MySQL 的索引是在存储引擎层实现的，不同的存储引擎支持不同的索引结构，主要包含以下几种：

MySQL 不同的存储引擎对于索引结构的支持情况如下：

提示

在 MySQL 中，通常所说的索引，如果没有特别指明，都是指 B+ 树数据结构的索引。

索引的数据结构

二叉树

假如说 MySQL 的索引结构采用二叉树的数据结构，比较理想的结构如下：

如果主键（数据）是顺序插入的，则会形成一个单向链表，结构如下：

所以，如果选择二叉树作为索引结构，会存在以下缺点：

• 按顺序插入时，会形成一个链表，查询性能大大降低。
• 大数据量情况下，层级较深，检索速度慢。

由于红黑树（如上所示）也是一颗二叉树，因此也存在 “大数据量情况下，层级较深，检索速度慢” 的问题。所以，在 MySQL 的索引结构中，并没有选择二叉树或者红黑树，而选择的是 B+ 树。那什么是 B+ 树呢？在详解 B+ 树 之前，先来介绍一下 B- 树。

B- 树

• 定义：

  • B- 树是一种多叉路平衡查找树，相对于二叉树，B- 树每个节点可以有多个分支，即多叉。
  • 以一颗最大度数（max-degree）为 5 (5 阶) 的 B- 树为例，那这个 B- 树每个节点最多存储 4 个 Key，5 个指针。
  • 树的度数指的是一个节点的子节点个数。

• 特点：

  • 5 阶的 B- 树，每一个节点最多存储 4 个 Key，对应 5 个指针。
  • 一旦节点存储的 Key 数量到达 5，就会裂变，中间元素向上分裂。
  • 在 B- 树中，非叶子节点和叶子节点都会存放数据。

B+ 树

B+ 树是 B- 树的变种，以一颗最大度数（max-degree）为 4（4 阶）的 B+ 树为例，来看一下其结构示意图：

从上图可以看到，两部分：

• 绿色框框起来的部分，是索引部分，仅仅起到索引数据的作用，不存储数据。
• 红色框框起来的部分，是数据存储部分，在其叶子节点中要存储具体的数据。

B+ 树与 B- 树的区别：

• B+ 树的叶子节点会形成一个单向链表。
• B+ 树的所有数据都只会存放在叶子节点。
• B+ 树的非叶子节点仅仅起到索引数据作用，具体的数据都是存放在叶子节点。

B+ 树相比 B- 树的优势：

• 单一节点存储更多的元素，使得查询的 I/O 次数更少。
• 所有查询都要查找到叶子节点，查询性能稳定。
• 所有叶子节点形成有序链表，便于范围查询。

上述所看到的结构是标准的 B+ 树的数据结构，接下来再看看 MySQL 中优化之后的 B+ 树。MySQL 索引数据结构对经典的 B+ 树进行了优化，在原 B+ 树的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的 B+ 树，提高区间访问的性能，利于排序。

为什么 InnoDB 选择 B+ 树作为索引结构？

• 相对于二叉树，B+ 树的层级更少，搜索效率更高。
• 相对 Hash 索引，B+ 树支持范围查找以及排序操作。
• 对于 B- 树，无论是叶子节点还是非叶子节点都会保存数据，这样会导致一页中存储的键值减少，指针跟着减少；要同样保存大量数据，只能增加树的高度，导致性能降低。
• B+ 树中间节点没有卫星数据（索引元素所指向的数据记录），只有索引。这就意味着同样的大小的磁盘页可以容纳更多节点元素，在相同的数据量下，B+ 树更加 “矮胖”，I/O 操作更少。
• 因为卫星数据的不同，导致查询过程也不同；B- 树的查找只需找到匹配元素即可，最好情况下查找到根节点，最坏情况下查找到叶子结点，所说性能很不稳定，而 B+ 树每次必须查找到叶子结点，性能稳定。

提示

MySQL 索引使用的是 B+ 树，因为索引是用来加快查询速度的，而 B+ 树会对数据进行排序，所以它可以提高查询速度。另外，在一个 B+ 树的节点中可以存储多个元素，从而可以使得 B+ 树的高度不会太高。在 MySQL 中一个 InnoDB ⻚就是一个 B+ 树节点，一个 InnoDB ⻚默认 16KB， 所以一般情况下一颗两层的 B+ 树可以存 2000 万行左右的数据。通过利用 B+ 树的叶子节点存储所有数据，并进行排序，而且叶子节点之间通过链表连接，这样可以很好地支持范围查询等 SQL 语句。

Hash

MySQL 中除了支持 B+ 树索引，还支持一种 Hash 索引类型。

• 结构：
  • 哈希索引就是采用一定的 Hash 算法，将键值换算成新的 Hash 值，映射到对应的槽位上，然后存储在 Hash 表中。

如果两个（或多个）键值，映射到一个相同的槽位上，那就会产生哈希冲突（也称为哈希碰撞），可以通过链表来解决。

• 特点：
  • Hash 索引只支持对等比较（如 =，in），不支持范围查询（如 between、>、<、…）。
  • 无法利用索引完成排序操作。
  • 查询效率高，通常（不存在哈希冲突的情况）只需要一次检索就可以了，效率通常要高于 B+ 树索引。

存储引擎的支持

在 MySQL 中，支持 Hash 索引的是 Memory 存储引擎。而 InnoDB 中具有自适应 Hash 功能，Hash 索引是 InnoDB 存储引擎根据 B+ 树索引在指定条件下自动构建的。

联合索引的数据结构

联合索引的定义

联合索引又叫组合索引（复合索引），例如下表：

CREATE TABLE `test` (
  `id` bigint NOT NULL AUTO_INCREMENT,
  `name` varchar(24) NOT NULL,
  `age` int NOT NULL,
  `position` varchar(32) NOT NULL,
  `address` varchar(128) NOT NULL,
  `birthday` date NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `idx_name_age_position` (`name`,`age`,`position`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

如下索引就是一个联合索引：

`idx_name_age_position` (`name`,`age`,`position`) USING BTREE

联合索引的结构

联合索引的底层数据结构如下：

比较相等时，先比较第一列的值，如果相等，再继续比较第二列，以此类推。了解联合索引的存储结构后，就知道索引最左前缀匹配原则是怎么回事了。在使用联合索引时，对于索引列的定义顺序将会影响到最终查询时索引的使用情况。例如联合索引 (name, age, position)，MySQL 会从最左边的列优先匹配，如果最左边的带头大哥 name 字段没有使用到，在未使用覆盖索引的情况下，就只能全表扫描（因为索引失效了）。简而言之，使用联合索引时，MySQL 会优先使用联合索引的第一列进行匹配，此后才会匹配下一列；如果不指定第一列匹配的值，也就无法得知下一步查询哪个节点。

聚簇索引与非聚簇索引

概念介绍

在 InnoDB 存储引擎中，根据索引的存储形式，又可以分为两种：聚簇索引（主键索引、聚集索引）、非聚簇索引（非主键索引、辅助索引、二级索引）。

• 聚簇索引（Clustered Index）：

  • 定义：索引和数据存储在一起。数据表中的记录按索引的键值顺序存储在磁盘上。每个表只能有一个聚簇索引。
  • 特点：
    • 数据存储顺序：数据物理上按索引键的顺序存储。
    • 主键：通常主键会自动成为聚簇索引，但也可以指定其他列为聚簇索引。
    • 索引结构：InnoDB 的聚簇索引是按照主键顺序构建 B+ 树结构的。
    • 检索速度：对索引键的查询速度较快，因为数据和索引在一起。
    • 插入和更新：插入和更新可能会比较慢，因为需要保持数据的物理顺序。
    • 适用场景：适用于经常需要范围查询的场景，比如查找某一范围内的数据。

• 非聚簇索引（Non-Clustered Index）：

  • 定义：索引和数据分开存储。非聚簇索引存储的是索引键值和指向数据记录的指针。每个表可以有多个非聚簇索引。
  • 特点：
    • 数据存储顺序：数据的物理存储顺序与索引无关。
    • 索引存储：索引存储的是键值和指向数据的指针。
    • 检索速度：对索引键的检索速度较快，但访问实际数据时需要通过指针进行二次查找。
    • 插入和更新：插入和更新相对较快，因为不需要保持数据的物理顺序。
    • 适用场景：适用于查找特定值或者少量记录的场景。

• 聚簇索引的选取规则：

  • 如果存在主键（Primary Key），主键索引就是聚簇索引。
  • 如果不存在主键，将使用第一个唯一（Unique）索引作为聚簇索引。
  • 如果表没有主键，或没有合适的唯一索引，则 InnoDB 会自动创建一个隐藏的 row-id 作为聚簇索引。

存储引擎的支持

• InnoDB 使用的是聚簇索引，树的叶子节点上的 data 就是数据本身。
• MyISAM 使用的是非聚簇索引，树的叶子节点上的 data 不是数据本身，而是数据存放的地址。

使用案例

当执行如下的 SQL 语句时（name 字段建立了索引），具体的查找过程是什么样子的？

具体查找过程如下:

• (1) 由于是根据 name 字段进行查询，所以先根据 name=’Arm’ 条件到 name 字段的二级索引中进行匹配查找，但是在二级索引中只能查找到 Arm 对应的主键值 10。
• (2) 由于查询返回的数据是主键值，所以此时，还需要根据主键值 10，到聚集索引中查找对应的数据记录。
• (3) 最终拿到这一行的数据，直接返回即可。

思考题目一

以下两条 SQL 语句（id 字段为主键，name 字段建立了索引），哪个执行效率更高？为什么？

• A. select * from user where id = 10;
• B. select * from user where name = ‘Arm’;

A 语句的执行效率要高于 B 语句。因为 A 语句直接走聚簇索引，可以直接返回数据。而 B 语句需要先查询 name 字段的非聚簇索引（二级索引），然后再查询聚簇索引，也就是需要进行回表查询，所以效率不高。

什么是回表查询

先根据普通索引（非聚簇索引）查询到主键值，再根据主键值在聚簇索引中获取行记录，这就是回表查询。值得一提的是，回表查询，相对于只扫描一遍聚簇索引的性能，要低一些。

使用覆盖索引来避免回表：

• 什么是覆盖索引：指索引包含了查询中涉及的所有列（包括需要筛选、排序和返回的列），这样就可以直接从索引中获取所有需要的数据，而不需要访问数据表本身。覆盖索引是一种避免回表查询的优化策略，只需要在一棵索引树上就能获取 SQL 所需的所有列数据，无需回表，速度更快。

• 具体的实现方式：将被查询的字段都建立普通索引或者联合索引，这样的话就可以直接返回索引中的数据，不需要再通过聚簇索引去定位行记录，避免了回表操作的执行。

思考题目二

InnoDB 主键索引的 B+ 树最多能存储多少条记录？

假设：一行数据大小为 1k，一页中就可以存储 16 行这样的数据（页的大小 16K）。
InnoDB 的指针占用 6 个字节的空间，主键即使为 bigint，占用字节数为 8。

高度为 2 时：设 key 为 n ，则指针数量为 n + 1。
n * 8 + (n + 1) * 6 = 16 * 1024，算出 n 约为 1170

每一个指针指向一个页，一个页是 16K，一行数据大小为 1k。
1171 * 16 = 18736，指针 × 行数 = 记录。

也就是说，如果 B+ 树的高度为 2，则可以存储 18000 条左右记录。

高度为 3 时：第一层根节点只有一个节点，一个节点由上面算出来是 1171 个指针，在第 2 层每一个节点那就也有 1171 个指针。
所以此时指针共有 1711 * 1171 个，再 x16 就是记录数。
1171 * 1171 * 16 = 21939856

也就是说，如果 B+ 树的高度为 3，则可以存储 2200w 条左右的记录。

所以 InnoDB 中的 B+ 树高度一般为 1 ~ 3 层，就可以满足千万级别的数据存储。在查找数据时，一次页的查找代表一次 I/O，所以通过主键索引查询通常只需要 1 ~ 3 次 I/O 操作即可查找到数据。

索引的创建

语法介绍

• 创建索引

CREATE [ UNIQUE | FULLTEXT ] INDEX index_name ON table_name (index_col_name, ... ) ;

• 查看索引

SHOW INDEX FROM table_name ;

• 删除索引

DROP INDEX index_name ON table_name ;

使用案例

-- A. name 字段为姓名字段，该字段的值可能会重复，为该字段创建索引。
CREATE INDEX idx_user_name ON tb_user(name);

-- B. phone 手机号字段的值，是非空，且唯一的，为该字段创建唯一索引。
CREATE UNIQUE INDEX idx_user_phone ON tb_user(phone);

-- C. 为 profession、age、status 创建联合索引。
CREATE INDEX idx_user_pro_age_sta ON tb_user(profession, age, status);

-- D. 为 email 建立合适的索引来提升查询效率。
CREATE INDEX idx_email ON tb_user(email);

面试题

高频面试题一

面试题：为什么建议 InnoDB 表必须创建主键，并且推荐使用整型的自增主键？

• (1) 如果在创建表时不设置主键，InnoDB 会自动从第一列开始筛选一列数据不重复的列（唯一列）做为主键，如果找不到这样的列，就会自动创建一个隐藏的列（row-id）做为主键，这会大大增加 MySQL 的工作量，所以建议在创建 InnoDB 表时一定要设置主键。

• (2) 使用整型的字段做为主键，一方面在数据比较时不需要进行转换，另一方面存储也比较节省空间。那为什么要强调主键自增呢？如果主键 ID 是无序的，那么很有可能新插入的值会导致当前节点分裂，此时 MySQL 不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过 OPTIMIZE TABLE 来重建表并优化填充页面。反之，如果每次插入有序，那就会在当前页后面连续写入，写不下就会重新分配一个节点，内存都是连续的，这样效率自然也就最高了。

高频面试题二

面试题：为什么非聚簇索引结构的叶子节点存储的是主键值？

非聚簇索引的叶子节点存储主键值而非全部数据，主要也是为了一致性和节省空间。如果非聚簇索引储存的也是数据，那么每次插入 MySQL 都不得不更新每棵索引树，这样就加剧了新增、更改数据时的性能损耗，并且这样一来空间利用率也不高，必然产生了大量冗余数据。

高频面试题三

面试题：为什么 InnoDB 选择 B+ 树作为索引结构？

• 相对于二叉树，B+ 树的层级更少，搜索效率更高。
• 相对 Hash 索引，B+ 树支持范围查找以及排序操作。
• 对于 B- 树，无论是叶子节点还是非叶子节点都会保存数据，这样会导致一页中存储的键值减少，指针跟着减少；要同样保存大量数据，只能增加树的高度，导致性能降低。
• B+ 树中间节点没有卫星数据（索引元素所指向的数据记录），只有索引。这就意味着同样的大小的磁盘页可以容纳更多节点元素，在相同的数据量下，B+ 树更加 “矮胖”，I/O 操作更少。
• 因为卫星数据的不同，导致查询过程也不同；B- 树的查找只需找到匹配元素即可，最好情况下查找到根节点，最坏情况下查找到叶子结点，所说性能很不稳定，而 B+ 树每次必须查找到叶子结点，性能稳定。

高频面试题四

面试题：B 树与 B+ 树的区别是什么？

B 树和 B+ 树是两种不同的树形数据结构，主要用于数据库索引和文件系统。

• B 树：

  • (1) 节点结构：每个节点包含键值和指向子节点的指针。一个节点可以存储多个键值和多个指针。
  • (2) 数据存储：所有节点（包括叶子节点和非叶子节点）都可以存储数据记录。
  • (3) 查找路径：在查找过程中，可以在任意节点上找到目标键值。
  • (4) 叶子节点：叶子节点没有链表结构，不需要相互连接。
  • (5) 保证有序：键值在节点内是按顺序排列的，而且节点之间的子节点指针也会根据键值的顺序进行排列。

• B+ 树：

  • (1) 节点结构：非叶子节点只存储键值和指向子节点的指针，不存储数据记录。
  • (2) 数据存储：所有数据记录都存储在叶子节点上，非叶子节点仅用于索引。
  • (3) 查找路径：在查找过程中，所有查找最终都会落在叶子节点上，因为数据记录只存储在叶子节点。
  • (4) 叶子节点：所有叶子节点形成一个有序的链表，便于范围查询和顺序访问。
  • (5) 保证有序：键值在非叶子节点内是按顺序排列的，而且数据记录在叶子节点内也是按顺序排列的。

B 树与 B+ 树的区别如下：

• (1) 叶子节点的结构：

  • B 树：叶子节点之间没有链表结构。
  • B+ 树：叶子节点通过链表连接，便于顺序访问。

• (2) 数据存储位置：

  • B 树：数据记录存储在所有节点上。
  • B+ 树：数据记录只存储在叶子节点上，非叶子节点仅用于索引。

• (3) 查询效率：

  • B 树：查询时可能在非叶子节点找到数据，搜索路径较短。
  • B+ 树：所有查询都必须到达叶子节点，但叶子节点之间的有序链表结构提高了范围查询和顺序访问的效率。

• (4) 范围查询：

  • B 树：范围查询不如 B+ 树高效，叶子节点之间没有链表结构。
  • B+ 树：范围查询更高效，因为叶子节点按顺序链表连接。

综上所述，B 树和 B+ 树各有优劣。B 树在查找单个键值时可能效率更高，而 B+ 树在范围查询和顺序访问方面表现更佳，因此在数据库系统中，B+ 树更为常用。

参考资料

• MySQL 6 种索引数据结构详解
• 深入理解 MySQL 索引底层数据结构
• 索引原理分析 (AVL 树、B-Tree、B+Tree)