高频面试题：理解MySQL索引在美团面试中的重要性以及索引底层数据结构的详细解析

在经历过几场技术面试的朋友们都知道，数据库索引是面试中经常被提及的知识点。这不仅对面试准备至关重要，利用索引还能够显著提高SQL查询的性能，成为一种高性价比的SQL优化手段。

索引的概述

索引是一种旨在加快数据检索速度的数据结构，实质上可视为一种排序的数据结构。

可以将索引的作用比作书籍的目录。例如，在查找字典中的某个字时，若没有目录，则需要逐页翻找，效率极低；而有了目录后，仅需查找字的位置，然后直接翻到相应的页即可。

索引的底层数据结构类型多种多样，常见的包括：B树、B+树、Hash表及红黑树。在MySQL中，无论是InnoDB还是MyISAM存储引擎，均采用B+树作为索引结构。

索引的优缺点

优点：

• 使用索引能显著提高数据检索的速度（大幅减少需要检索的数据量），这也是创建索引的主要目的。
• 创建唯一性索引能够确保数据库表中每行数据的唯一性。

缺点：

• 创建和维护索引会消耗大量时间。当对表中的数据进行增删改操作时，若数据有索引，则索引也需实时更新，这将降低SQL的执行效率。
• 索引需要使用物理文件存储，因而也会占用一定的空间。

然而，使用索引是否一定能提升查询性能？

在大多数情况下，索引查询的速度确实快于全表扫描，但若数据库中的数据量不大，则使用索引未必能带来显著的提升。

索引底层数据结构的选择

Hash表

哈希表是以键值对形式组织的数据集合，通过键（key）可以快速检索到对应的值（value），从而实现接近O(1)的检索速度。

为何可以通过key快速获取value呢？ 这是因为哈希算法（或称散列算法）。利用哈希算法，我们能够快速找到key对应的索引位置，进而找到相应的值。

hash = hashfunc(key)  
index = hash % array_size  

但哈希算法存在Hash冲突的问题，即多个不同的key可能产生相同的索引。通常情况下，解决此问题的方法是链地址法，例如在JDK 1.8之前，HashMap就采用链地址法来处理哈希冲突。不过，自JDK 1.8起，为了减少链表过长导致的搜索时间，HashMap引入了红黑树。

为了减少Hash冲突的发生，好的哈希函数应能“均匀地”将数据分布于整个可能的哈希值集合中。

MySQL的InnoDB存储引擎虽然不直接支持常规哈希索引，但它提供了一种特殊的“自适应哈希索引”（Adaptive Hash Index），该索引并非传统意义上的纯哈希索引，而是结合了B+树与哈希索引的特点，以便更好地适应实际应用中的数据访问模式与性能需求。每个哈希桶实际上是一个小型B+树结构，能够存储多个键值对，而不仅限于单个键。这有助于降低哈希冲突链的长度，提高索引的效率。有关自适应哈希索引的详细信息，可参考MySQL各种“Buffer”之Adaptive Hash Index。

既然哈希表高效，为何MySQL不使用其作为索引的数据结构呢？ 主要是因为哈希索引不支持顺序和范围查询。例如在需要对表中数据进行排序或范围查询时，哈希索引显得无能为力。同时，每次IO操作只能检索一个元素。

以以下SQL为例：

SELECT * FROM tb1 WHERE id < 500;  

在这个范围查询中，直接遍历小于500的叶子节点即可。而哈希索引是依据哈希算法进行定位，意味着需要对1到499的每个数据执行一次哈希计算，效率极低，这便是哈希索引的最大缺陷。

二叉查找树（BST）

二叉查找树是一种基于二叉树的结构，其特性包括：

1. 左子树所有节点的值均小于根节点的值。
2. 右子树所有节点的值均大于根节点的值。
3. 左右子树也都是二叉查找树。

在平衡的情况下，二叉查找树的查询时间复杂度为O(log2(N))，效率较高。然而在最坏的情况下（如有序插入节点），树可能退化为线性链表，导致查询效率下降至O(N)。

综上所述，二叉查找树的性能高度依赖于其平衡程度，因此并不适合作为MySQL底层索引的数据结构。

为了解决这一问题并提升查询效率，研究人员开发了多种基于二叉查找树的改进型数据结构，如平衡二叉树、B树、B+树等。

AVL树

AVL树是计算机科学中最早提出的自平衡二叉查找树，得名于其发明者G.M. Adelson-Velsky和E.M. Landis。AVL树的特征在于保证任何节点的左右子树高度之差不超过1，因此也被称作高度平衡二叉树，其查找、插入和删除的时间复杂度均为O(logn)。

AVL树通过旋转操作维持平衡，主要有四种旋转方式：LL旋转、RR旋转、LR旋转和RL旋转。虽然AVL树能够保持平衡，但频繁的旋转操作会导致较大的计算开销，进而降低查询性能。此外，在使用AVL树时，每个节点仅存储一个数据，而每次进行磁盘IO时只能读取一个节点的数据，这意味着如果需要查询的数据分布在多个节点上，就需进行多次磁盘IO。由于磁盘IO是一项耗时的任务，因此在设计数据库时，我们需优先考虑如何最大限度地减少磁盘IO的数量。

因此，AVL树在实际应用中使用较少。

红黑树

红黑树是一种自平衡的二叉查找树，通过在节点插入和删除时进行颜色变换和旋转，确保树的平衡性。它具有以下特征：

1. 每个节点要么是红色，要么是黑色。
2. 根节点总是黑色。
3. 每个叶子节点是黑色（NIL节点）。
4. 如果节点是红色，则其子节点必须为黑色（反之不一定）。
5. 从根节点到每个叶节点或空子节点的路径必须包含相同数量的黑色节点。

与AVL树不同，红黑树并不追求严格的平衡，而是保持大致平衡。因此，虽然查询效率稍有下降，红黑树在插入和删除节点时的效率显著提升，因为只需进行O(1)次的旋转和变更即可保持基本平衡，而不必像AVL树那样进行O(logn)次的旋转。

红黑树的应用较为广泛，TreeMap、TreeSet以及JDK 1.8的HashMap底层均采用红黑树。在内存中的数据处理上，红黑树表现优异。

B树与B+树

B树（多路平衡查找树）及其变体B+树是大多数数据库系统和文件系统采用的索引结构。

B树和B+树有何异同？

• B树的每个节点不仅存储键(key)，还存储数据(data)，而B+树的叶子节点只存储键值和数据，内节点仅存储键。
• B树的叶子节点是独立的，B+树的叶子节点通过指针链表连接相邻的叶子节点。
• B树的检索过程可能在未达到叶子节点时终止，而B+树的检索效率稳定，始终从根节点到叶子节点进行。
• 在B树中进行范围查询时，需先找到下限值并进行中序遍历，而B+树的范围查询则可以直接遍历链表。

总结而言，B+树在IO次数更少、查询效率更稳定和范围查询更适用等方面相较于B树具有明显优势。

在MySQL中，MyISAM引擎和InnoDB引擎均使用B+树作为索引结构，但两者的实现方式存在差异：

• 在MyISAM引擎中，B+树的叶节点的data域存储的是数据记录的地址，通过B+树检索时，若找到指定的Key，则取出其data域的值，再以该值为地址读取相应的数据记录，这称作“非聚簇索引（非聚集索引）”。
• 在InnoDB引擎中，数据文件本身即为索引文件，表数据文件以B+树组织，叶节点的data域保存完整的数据记录，主索引的key为数据表的主键，因此InnoDB表数据文件本身即为主索引。而其余索引则为辅助索引，其data域存储相应记录主键的值而非地址。这便是与MyISAM的不同之处。通过主索引搜索时，直接找到key所在的节点即可取出数据；而通过辅助索引查找时，则需要先获取主键的值，再访问主索引。因此，在设计表时，不建议使用过长或非单调的字段作为主键，以免导致主索引的频繁分裂。

索引类型总结

按照数据结构维度分类：

• BTree索引：MySQL中默认且最常用的索引类型，只有叶子节点存储value，非叶子节点仅存储指针和key。MyISAM和InnoDB实现BTree索引均采用B+树，但实现方式不同。
• 哈希索引：类似键值对形式，一次即可定位。
• RTree索引：一般不使用，仅支持几何数据类型，范围查找效率低，通常用搜索引擎如ElasticSearch代替。
• 全文索引：对文本内容进行分词，目前仅支持CHAR、VARCHAR和TEXT列，通常不使用，效率较低，通常用搜索引擎如ElasticSearch代替。

按照底层存储方式分类：

• 聚簇索引：索引结构和数据存放在一起，InnoDB中的主键索引属于聚簇索引。
• 非聚簇索引：索引结构和数据分开存放，二级索引（辅助索引）便属于非聚簇索引。MySQL的MyISAM引擎不论主键还是非主键均使用非聚簇索引。

按照应用维度分类：

• 主键索引：加速查询且列值唯一（不允许NULL），表中仅能有一个。
• 普通索引：仅用于加速查询。
• 唯一索引：加速查询且列值唯一（可以为NULL）。
• 覆盖索引：索引包含所有查询所需字段的值。
• 联合索引：由多列值组成的一个索引，专为组合搜索设计，其效率高于索引合并。
• 全文索引：对文本内容进行分词以进行搜索，目前仅支持CHAR、VARCHAR和TEXT列，通常不使用，效率较低，通常用搜索引擎如ElasticSearch代替。

MySQL 8.x中实现的索引新特性：

• 隐藏索引：即不可见索引，不会被优化器使用，但仍需维护，通常用于软删除和灰度发布场景。主键不允许设置为隐藏。
• 降序索引：此前版本支持通过DESC指定索引为降序，但创建的仍是常规升序索引。直到MySQL 8.x版本才开始真正支持降序索引。此外，在MySQL 8.x版本中对GROUP BY语句不再进行隐式排序。
• 函数索引：自MySQL 8.0.13版本起，支持在索引中使用函数或表达式值，即索引中可包含函数或表达式。

主键索引

数据表的主键列使用主键索引。

一张数据表仅能有一个主键，且主键不能为NULL或重复。在MySQL的InnoDB表中，若未显式指定主键，InnoDB会自动检查表中是否有唯一索引且不允许存在NULL值的字段，若有，则该字段为默认主键；若无，则自动创建一个6Byte的自增主键。

二级索引

二级索引（Secondary Index）又称辅助索引，叶子节点存储的是主键。通过二级索引，可以定位主键位置。

唯一索引、普通索引、前缀索引等均属于二级索引。

对于不了解的读者可以先暂时保留疑问，后续会有解答，或可自行搜索。

1. 唯一索引（Unique Key）：是一种约束，唯一索引的属性列不能出现重复值，但允许数据为NULL，一张表允许创建多个唯一索引。
2. 普通索引（Index）：普通索引的唯一作用是加速数据查询，一张表可以创建多个普通索引，允许数据重复和NULL。
3. 前缀索引（Prefix）：仅适用于字符串类型，前缀索引是对文本的前几个字符创建索引，相比于普通索引，数据更小，因为仅提取前几个字符。
4. 全文索引（Full Text）：用于检索大文本数据中的关键词，目前MySQL 5.6之前仅MyISAM引擎支持，5.6后InnoDB也支持。

聚簇索引与非聚簇索引

聚簇索引

聚簇索引（Clustered Index）是指索引结构与数据一起存储的索引，并非单独的索引类型。InnoDB中的主键索引属于聚簇索引。

在MySQL中，InnoDB引擎的.ibd文件同时包含该表的索引和数据，表的索引（B+树）的每个非叶子节点存储索引，叶子节点存储索引以及对应的数据。

聚簇索引的优缺点

优点：

• 查询速度极快：聚簇索引的查询速度非常快，因为整个B+树本身就是多叉平衡树，叶子节点有序，定位到索引节点相当于定位到数据。相比非聚簇索引，聚簇索引少了一次读取数据的IO操作。
• 排序查询和范围查询优化：聚簇索引在主键的排序查找和范围查询中表现出色。

缺点：

• 依赖有序数据：B+树是多路平衡树，若索引数据无序，则插入时需排序，若数据为整型则好，若为字符串或UUID这类较长难比较的数据，插入或查找速度将变得慢。
• 更新代价高：若对索引列数据进行修改，相应的索引也需要调整，且聚簇索引的叶子节点存储数据，修改代价较大，故主键索引一般不可修改。

非聚簇索引

非聚簇索引（Non-Clustered Index）是指索引结构与数据分开存放的索引，并非单独的索引类型。二级索引（辅助索引）属于非聚簇索引。MySQL的MyISAM引擎，无论主键还是非主键均使用非聚簇索引。

非聚簇索引的叶子节点不一定存储数据的指针，因为二级索引的叶子节点存储的是主键，需通过主键再去查找数据。

非聚簇索引的优缺点

优点：

• 更新代价相对较小。非聚簇索引的更新代价不如聚簇索引大，因为非聚簇索引的叶子节点不存储数据。

缺点：

• 依赖有序数据：与聚簇索引相同，非聚簇索引也依赖有序数据。
• 可能需二次查询（回表）：这也是非聚簇索引的主要缺点。当查到对应的指针或主键后，可能还需在数据文件中查询。

以下为MySQL表的文件截图：

聚簇索引与非聚簇索引的对比

非聚簇索引一定回表查询吗（覆盖索引）？

非聚簇索引并不一定回表查询。

例如，用户希望使用SQL查询用户名，而用户名字段正好建立了索引。

SELECT name FROM table WHERE name='guang19';  

在这种情况下，索引的key即为name，直接返回结果，无需回表查询。

即使在MYISAM中，主键索引确实需回表，因为其叶子节点存储的是指针。然而，如果SQL查询的就是主键呢？

SELECT id FROM table WHERE id=1;  

主键索引的key即为主键，查询后直接返回即可。这种情况称作覆盖索引。

覆盖索引

如果索引包含（或覆盖）所有需要查询字段的值，我们称之为覆盖索引（Covering Index）。在InnoDB存储引擎中，若不是主键索引，叶子节点存储的是主键+列值。最终仍需“回表”，即通过主键再查一次，这会比较慢。而覆盖索引意味着要查询的字段恰好是索引字段，因此可直接通过索引获取数据，避免回表查询。

例如，当需要查询主键时，如果通过主键索引直接可查询到主键；如若需要查询name字段，而name字段有索引，则能直接根据索引获取数据而无需回表。

以下是覆盖索引效果的简单演示：

1. 创建一张名为cus_order的表，以便进行测试。为便于测试，该表仅包含id、score、name三个字段。

CREATE TABLE `cus_order` (  
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,  
  `score` int(11) NOT NULL,  
  `name` varchar(11) NOT NULL DEFAULT '',  
  PRIMARY KEY (`id`)  
) ENGINE=InnoDB AUTO_INCREMENT=100000 DEFAULT CHARSET=utf8mb4;  

2. 创建一个简单的存储过程（PROCEDURE）用于插入100万条测试数据。

DELIMITER ;;  
CREATE DEFINER=`root`@`%` PROCEDURE `BatchinsertDataToCusOder`(IN start_num INT,IN max_num INT)  
BEGIN  
      DECLARE i INT default start_num;  
      WHILE i < max_num DO  
          insert into `cus_order`(`id`, `score`, `name`)  
          values (i,RAND() * 1000000,CONCAT('user', i));  
          SET i = i + 1;  
      END WHILE;  
  END;;  
DELIMITER ;  

3. 存储过程定义完成后，执行存储过程插入数据。

CALL BatchinsertDataToCusOder(1, 1000000); # 插入100万条随机数据  

等待片刻，100万条测试数据便插入完成。

4. 创建覆盖索引并使用EXPLAIN命令分析。

为对这100万条数据按score进行排序，执行以下SQL语句：

SELECT `score`, `name` FROM `cus_order` ORDER BY `score` DESC; # 降序排序  

使用EXPLAIN命令分析该SQL，通过Extra字段的Using filesort可知未使用覆盖索引。

当然，这是正常现象，因为尚未创建索引。

接下来，为score和name两个字段建立联合索引：

ALTER TABLE `cus_order` ADD INDEX id_score_name(score, name);  

创建完成后，再用EXPLAIN命令分析该SQL。

通过Extra字段的Using index，说明该SQL成功使用了覆盖索引。

有关EXPLAIN命令的详细介绍，请参见：MySQL执行计划分析。

联合索引

通过表中的多个字段创建索引，称为联合索引，也称为组合索引或复合索引。

例如，使用score和name两个字段创建联合索引：

ALTER TABLE `cus_order` ADD INDEX id_score_name(score, name);  

最左前缀匹配原则

最左前缀匹配原则指的是，在使用联合索引时，MySQL将根据联合索引中的字段顺序，从左到右依次与查询条件匹配，若查询条件中存在与联合索引最左侧字段匹配的字段，则将利用该字段过滤数据，直至所有字段匹配完成或遇到范围查询（如>、<）时停止匹配。对于>=、<=、BETWEEN、like的前缀匹配范围查询则不会停止匹配。因此，在使用联合索引时，建议将区分度高的字段放在最左边，以获得更好的数据过滤效果。

相关阅读：联合索引的最左匹配原则全网都在说的一个错误结论。

索引下推

索引下推（Index Condition Pushdown）是MySQL 5.6版本中提供的一项索引优化功能，能够在非聚簇索引遍历过程中，对索引中包含的字段进行判断，以过滤不符合条件的记录，从而减少回表的次数。

正确使用索引的建议

选择合适的字段建立索引

• 不为NULL的字段：索引字段的数据应尽量不为NULL，数据库较难优化NULL字段。如果字段频繁被查询且不可避免为NULL，建议使用0,1,true,false等语义清晰的短值作为替代。
• 频繁查询的字段：索引字段应是查询操作非常频繁的字段。
• 作为条件查询的字段：在WHERE条件中被使用的字段应考虑建立索引。
• 频繁用于排序的字段：索引本身已排序，因此可加快排序查询时间。
• 经常用于连接的字段：常用于连接查询的字段可以考虑建立索引，以提高多表连接查询的效率。

对频繁更新的字段建立索引需谨慎

尽管索引可以提高查询效率，但维护索引的成本亦不容小觑。若某字段不经常查询，反而频繁修改，则不应在此字段上建立索引。

限制每张表的索引数量

索引并非越多越好，建议单张表的索引不超过5个。虽然索引能提升效率，但也可能降低插入和更新的效率，甚至在某些情况下影响查询效率。

MySQL优化器在评估如何优化查询时，会根据统一信息评估所有可用索引，以生成最佳执行计划，若有多个索引可用于查询，将增加优化器生成执行计划所需的时间，进而降低查询性能。

尽量考虑建立联合索引而非单列索引

索引占用磁盘空间，可理解为每个索引均对应一棵B+树。如果表字段过多且索引过多，当数据量达到一定规模，索引占用的空间将非常可观。若采用联合索引，将多个字段放在同一个索引上，将极大节省磁盘空间，提高数据修改操作的效率。

注意避免冗余索引

冗余索引指索引功能相同，能命中索引(a, b)则必能命中索引(a)，因此索引(a)便是冗余索引。例如（name, city）和（name）这两个索引就是冗余索引，在大多数情况下，应该扩展已有索引而非新建索引。

避免索引失效

索引失效是导致慢查询的主要原因之一，常见导致索引失效的情况包括：

• 使用SELECT *进行查询；SELECT *并不会直接导致索引失效（若不走索引大概率是因为WHERE查询范围过大），但可能引发网络传输及数据处理的浪费，无法利用索引覆盖。
• 创建了组合索引，但查询条件未遵循最左匹配原则。
• 在索引列上进行计算、函数、类型转换等操作。
• 使用以%开头的LIKE查询（如LIKE '%abc'）。
• 查询条件中使用OR，并且OR的前后条件中有一个列没有索引，相关索引均不会被使用。
• 发生隐式转换等情况。

删除长期未使用的索引

定期删除长期未使用的索引，冗余索引会造成不必要的性能损耗。

在MySQL 5.7中，可以通过查询sys库的schema_unused_indexes视图找出哪些索引未被使用。

学会分析语句是否走索引查询

通过EXPLAIN命令分析SQL的执行计划，可以判断语句是否命中索引。执行计划是指一条SQL语句经过MySQL查询优化器优化后，具体的执行方式。

EXPLAIN不会真正执行相关语句，而是通过查询优化器对语句进行分析，找出最佳查询方案并展示相关信息。

EXPLAIN的输出格式如下：

mysql> EXPLAIN SELECT `score`,`name` FROM `cus_order` ORDER BY `score` DESC;  
+----+-------------+-----------+------------+------+---------------+------+---------+------+--------+----------+----------------+  
| id | select_type | table     | partitions  | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra          |  
+----+-------------+-----------+------------+------+---------------+------+---------+------+--------+----------+----------------+  
|  1 | SIMPLE      | cus_order | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 997572 |   100.00 | Using filesort |  
+----+-------------+-----------+------------+------+---------------+------+---------+------+--------+----------+----------------+  
1 row in set, 1 warning (0.00 sec)  

各字段的含义如下：