MySQL 面试之索引篇
综合
【基础】什么是索引？为什么要使用索引？
要点
“索引”是数据库为了提高查找效率的一种数据结构。
日常生活中，我们可以通过检索目录，来快速定位书本中的内容。索引和数据表，就好比目录和书，想要高效查询数据表，索引至关重要。在数据量小且负载较低时，不恰当的索引对于性能的影响可能还不明显；但随着数据量逐渐增大，性能则会急剧下降。因此，设置合理的索引是数据库查询性能优化的最有效手段。
【基础】索引的优点和缺点是什么？
要点
✔️️️️️️️ 索引的优点：
- 索引大大减少了服务器需要扫描的数据量，从而加快检索速度。
- 索引可以帮助服务器避免排序和临时表。
- 索引可以将随机 I/O 变为顺序 I/O。
- 支持行级锁的数据库，如 InnoDB 会在访问行的时候加锁。使用索引可以减少访问的行数，从而减少锁的竞争，提高并发。
- 唯一索引可以确保每一行数据的唯一性，通过使用索引，可以在查询的过程中使用优化隐藏器，提高系统的性能。
❌ 索引的缺点：
- 创建和维护索引要耗费时间，这会随着数据量的增加而增加。
- 索引需要占用额外的物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立组合索引那么需要的空间就会更大。
- 写操作（
INSERT/UPDATE/DELETE）时很可能需要更新索引，导致数据库的写操作性能降低。
基于以上，可以归纳出索引的基本使用规则：
- 索引不是越多越好，不要为所有列都创建索引
- 要尽量避免冗余和重复索引
- 要考虑删除未使用的索引
- 尽量的扩展索引，不要新建索引
- 频繁作为
WHERE过滤条件的列应该考虑添加索引
【基础】何时适用索引？何时不适用索引？
要点
✔️️️️ 什么情况适用索引？
- 字段的数值有唯一性的限制，如用户名。
- 频繁作为
WHERE条件或JOIN条件的字段，尤其在数据表大的情况下。 - 频繁用于
GROUP BY或ORDER BY的字段。将该字段作为索引，查询时就无需再排序了，因为 B+ 树本身就是按序存储的。 - DISTINCT 字段需要创建索引。
❌ 什么情况不适用索引？
- 频繁写操作（
INSERT/UPDATE/DELETE），也就意味着需要更新索引。 - 很少作为
WHERE条件或JOIN条件的字段，也就意味着索引会经常无法命中，没有意义，还增加空间开销。 - 非常小的表，对于非常小的表，大部分情况下简单的全表扫描更高效。
- 特大型的表，建立和使用索引的代价将随之增长。可以考虑使用分区技术或 Nosql。
【基础】索引有哪些分类？
要点
MySQL 索引可以从以下四个维度来分类：
- 按【数据结构】分类：B+tree 索引、Hash 索引、Full-text 索引
- 按【物理存储】分类：聚簇索引、二级索引（辅助索引）
- 按【字段特性】分类：主键索引、普通索引、前缀索引
- 按【字段个数】分类：单列索引、联合索引（复合索引、组合索引）
【中级】创建索引有哪些基本原则？
要点
- 索引不是越多越好，不要为所有列都创建索引。要考虑到索引的维护代价、空间占用和查询时回表的代价。索引一定是按需创建的，并且要尽可能确保足够轻量。一旦创建了多字段的联合索引，我们要考虑尽可能利用索引本身完成数据查询，减少回表的成本。
- 要尽量避免冗余和重复索引。
- 要考虑删除未使用的索引。
- 尽量的扩展索引，不要新建索引。
- 频繁作为
WHERE过滤条件的列应该考虑添加索引。
【中级】哪些情况下，索引会失效？
要点
导致索引失效的情况有：
- 对索引使用左模糊匹配
- 对索引使用函数或表达式
- 对索引隐式类型转换
- 联合索引不遵循最左匹配原则
- 索引列判空 - 索引列与 NULL 或者 NOT NULL 进行判断的时候也会失效
- WHERE 子句中的 OR
【基础】= 和 in 的顺序对于命中索引是否有影响？
要点
不需要考虑 =、IN 等的顺序，MySQL 会自动优化这些条件的顺序，以匹配尽可能多的索引列。
【示例】如有索引 (a, b, c, d)，查询条件 c > 3 and b = 2 and a = 1 and d < 4 与 a = 1 and c > 3 and b = 2 and d < 4 等顺序都是可以的，MySQL 会自动优化为 a = 1 and b = 2 and c > 3 and d < 4，依次命中 a、b、c、d。
数据结构
【基础】索引有哪些常见数据结构？
要点
在 MySQL 中，索引是在存储引擎层而不是服务器层实现的，所以，并没有统一的索引标准。不同存储引擎的索引的数据结构也不相同。下面是 MySQL 常用存储引擎对一些主要索引数据结构的支持：
| 索引数据结构/存储引擎 | InnoDB 引擎 | MyISAM 引擎 | Memory 引擎 |
|---|---|---|---|
| B+ 树索引 | ✔️️️️️️️ | ✔️️️️️️️ | ✔️️️️️️️ |
| Hash 索引 | ❌ | ❌ | ✔️️️️️️️ |
| Full Text 索引 | ✔️️️️️️️ | ✔️️️️️️️ | ❌ |
MySQL 索引的常见数据结构：
- 哈希索引
- 因为索引数据结构紧凑，所以查询速度非常快。
- 只支持等值比较查询 - 包括
=、IN()、<=>；不支持任何范围查询，如WHERE price > 100。 - 无法用于排序 - 因为哈希索引数据不是按照索引值顺序存储的。
- 不支持部分索引匹配查找 - 因为哈希索引时使用索引列的全部内容来进行哈希计算的。如，在数据列 (A,B) 上建立哈希索引，如果查询只有数据列 A，无法使用该索引。
- 不能用索引中的值来避免读取行 - 因为哈希索引只包含哈希值和行指针，不存储字段，所以不能使用索引中的值来避免读取行。不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能影响不大。
- 哈希索引有可能出现哈希冲突
- 出现哈希冲突时，必须遍历链表中所有的行指针，逐行比较，直到找到符合条件的行。
- 如果哈希冲突多的话，维护索引的代价会很高。
- B 树索引
- 适用于全键值查找、键值范围查找和键前缀查找，其中键前缀查找只适用于最左前缀查找。
- 所有的关键字（可以理解为数据）都存储在叶子节点，非叶子节点并不存储真正的数据，所有记录节点都是按键值大小顺序存放在同一层叶子节点上。
- 所有的叶子节点由指针连接。
【中级】为什么 InnoDB 采用 B+ 树索引？
要点
二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。其查询时间复杂度是 $$O(log(N))$$。
当然为了维持 $$O(log(N))$$ 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 $$O(log(N))$$。
随着数据库中数据的增加，索引本身大小随之增加，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘 I/O 消耗，相对于内存存取，I/O 存取的消耗要高几个数量级。可以想象一下一棵几百万节点的二叉树的深度是多少？如果将这么大深度的一颗二叉树放磁盘上，每读取一个节点，需要一次磁盘的 I/O 读取，整个查找的耗时显然是不能够接受的。那么如何减少查找过程中的 I/O 存取次数？
一种行之有效的解决方法是减少树的深度，将二叉树变为 N 叉树（多路搜索树），而 B+ 树就是一种多路搜索树。
B+ 树索引适用于全键值查找、键值范围查找和键前缀查找，其中键前缀查找只适用于最左前缀查找。
理解 B+Tree 时，只需要理解其最重要的两个特征即可：
- 首先，所有的关键字（可以理解为数据）都存储在叶子节点，非叶子节点并不存储真正的数据，所有记录节点都是按键值大小顺序存放在同一层叶子节点上。
- 其次，所有的叶子节点由指针连接。如下图为简化了的 B+Tree。
细节
B+ 树 vs B 树
- B+ 树只在叶子节点存储数据，而 B 树的非叶子节点也要存储数据，所以 B+ 树的单个节点的数据量更小，在相同的磁盘 I/O 次数下，就能查询更多的节点。
- 另外，B+ 树叶子节点采用的是双链表连接，适合 MySQL 中常见的基于范围的顺序查找，而 B 树无法做到这一点。
B+ 树 vs 二叉树
- 对于有 N 个叶子节点的 B+ 树，其搜索复杂度为
O(logdN)，其中 d 表示节点允许的最大子节点个数为 d 个。 - 在实际的应用当中， d 值是大于 100 的，这样就保证了，即使数据达到千万级别时，B+ 树的高度依然维持在 1~3 层左右，也就是说一次数据查询操作只需要做 1~3 次的磁盘 I/O 操作就能查询到目标数据。
- 而二叉树的每个父节点的儿子节点个数只能是 2 个，意味着其搜索复杂度为
O(logN)，这已经比 B+ 树高出不少，因此二叉树检索到目标数据所经历的磁盘 I/O 次数要更多。
一言以蔽之，使用 B+ 树，而不是二叉树，是为了减少树的高度，也就是为了减少磁盘 I/O 次数。
B+ 树索引和 Hash 索引的差异
- B+ 树索引支持范围查询；Hash 索引不支持。
- B+ 树索引支持联合索引的最左匹配原则；Hash 索引不支持。
- B+ 树索引支持排序；Hash 索引不支持。
- B+ 树索引支持模糊查询；Hash 索引不支持。
- Hash 索引的等值查询比 B+ 树索引效率高。
综上，Hash 索引的应用场景很苛刻，不适用于绝大多数场景。
【中级】B+ 树索引能存多少数据？
要点
在 InnoDB 存储引擎中，B+ 树默认数据页大小为 16KB。
所有 B+ 树都是从高度为 1 的树开始，然后根据数据的插入，慢慢增加树的高度。随着插入 B+ 树索引的记录变多，1 个页（16K）无法存放这么多数据，所以会发生 B+ 树的分裂，B+ 树的高度变为 2。
非叶子节点可存储的记录数
根节点和中间节点存放的是索引键对，由（索引键、指针）组成。
索引键就是排序的列，而指针是指向下一层的地址，在 MySQL 的 InnoDB 存储引擎中占用 6 个字节。若主键是 BIGINT 类型，占 8 个字节。也即是说，这样的一个键值对需要 8+6 = 14 字节。
非叶子节点可存储的记录数 = 页大小（16K） / 键值对大小（14） ≈ 1100
叶子节点可存储的记录数
为了方便计算，假设数据记录的平均大小为 1000 字节（实际一般小于这个值），则
叶子节点可存储的记录数 = 页大小（16K） / 记录平均大小（1000） ≈ 16
由此可知，树高度为 2 的 B+ 树索引，有一个根节点，约 1100 个叶子节点。因此，最多能存放的记录数为：
二层 B+ 树记录数 ≈ 1100 * 16 = 16,100
如何推算不同高度的 B+ 树可存储的记录数
综上所述，数据记录的平均大小为 1000 字节，主键为 BIGINT 的表，可以按如下推算其可存储的记录数：
- 高度为 2 的 B+树索引最多能存放约
1100 * 16 = 16,100条记录（约 1.6 万），查询时只需 2 次 I/O。 - 高度为 3 的 B+树索引最多能存放约
1100 * 1100 * 16 = 19,360,000条记录（约 2 千万），查询时只需 3 次 I/O。 - 高度为 4 的 B+树索引最多能存放约
1100 * 1100 * 1100 * 16 = 21,296,000,000条记录（约 200 多亿），查询时只需 4 次 I/O。
优化 B+ 树索引的插入性能：
- 顺序插入（如自增 ID 或时间列）的维护代价小，性能较好。
- 无序插入（如用户昵称）会导致页分裂、旋转等开销较大的操作，影响性能。
- 主键设计应尽量使用顺序值（如自增 ID），以保证高并发场景下的性能。
聚簇索引和非聚簇索引
【中级】聚簇索引和非聚簇索引有什么区别？
要点
根据叶子节点的内容，索引类型分为主键索引和非主键索引。
主键索引又被称为聚簇索引（clustered index），其叶子节点存的是整行数据。
- 聚簇表示数据行和相邻的键值紧凑地存储在一起，因为数据紧凑，所以访问快。
- 因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。
- InnoDB 的聚簇索引实际是在同一个结构中保存了 B 树的索引和数据行。
非主键索引又被称为二级索引（secondary index），其叶子节点存的是主键的值。数据存储在一个位置，索引存储在另一个位置，索引中包含指向数据存储位置的指针。
- 如果语句是
select * from T where ID=500，即聚簇索引查询方式，则只需要搜索主键索引树； - 如果语句是
select * from T where k=5，即非聚簇索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。
也就是说，基于非聚簇索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。
显然，主键长度越小，非聚簇索引的叶子节点就越小，非聚簇索引占用的空间也就越小。
【基础】什么是覆盖索引？
要点
覆盖索引是指：二级索引上的信息满足查询所需的所有字段，不需要回表查询聚簇索引上的数据。
由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。
字段特性索引
【基础】AUTO_INCREMENT 列达到最大值时会发生什么？
要点
配置主键
在 MySQL 中，如果表定义的自增 ID 到达上限后，再申请下一个 ID，得到的值不变！因此会导致重复值的错误。
没有配置主键
如果 InnoDB 表中没有配置主键，InnoDB 会自动创建一个不可见的、长度为 6 个字节的 row_id 作为默认主键。
InnoDB 在全局维护一个 dict_sys.row_id 值。每次插入一行数据时，都会获取当前的 dict_sys.row_id 值，并将其加 1。row_id 的范围是 0 到 2^48 - 1。当 row_id 达到上限后，会从 0 开始重新循环。
如果插入的新数据的 row_id 在表中已存在，老数据会被新数据覆盖，且不会产生任何报错。可以通过 gdb 动态修改 dict_sys.row_id 来验证这一行为。
【基础】普通键和唯一键，应该怎么选择？
要点
唯一索引的主要作用是保证数据的唯一性，而普通索引则更灵活。在业务代码保证不会写入重复数据的情况下，普通索引和唯一索引在查询性能上几乎没有差别。
普通索引 在更新操作中性能更优，尤其是在写多读少的场景下，能够利用 change buffer 减少磁盘 I/O。
唯一索引 适用于需要保证数据唯一性的场景，但在更新操作中性能较差，因为它无法使用 change buffer。
在业务允许的情况下，优先选择普通索引，因为它可以利用 change buffer 来提升更新性能。如果业务要求必须保证数据的唯一性，则必须使用唯一索引。
细节
查询过程的性能差异：对于查询操作，普通索引和唯一索引的性能差异微乎其微。唯一索引在找到第一个满足条件的记录后会停止检索，而普通索引需要继续查找下一个记录，但由于数据页的读取方式，这种差异可以忽略不计。
更新过程的性能差异：更新操作中，普通索引可以利用 change buffer 来优化性能，而唯一索引则不能使用 change buffer。
- change buffer 是一种将更新操作缓存在内存中的机制，减少了对磁盘的随机读取，从而提升了更新操作的性能。
- 唯一索引在更新时需要检查唯一性约束，必须将数据页读入内存，增加了磁盘 I/O 的开销。
change buffer 的应用
- change buffer 的数据是持久化的，即使机器掉电重启，change buffer 中的数据也不会丢失，因为它会被写入磁盘。
- change buffer 适用于写多读少的场景，如账单类、日志类系统，因为这些场景下数据页在写入后不会立即被访问，change buffer 可以显著减少磁盘 I/O。
- 对于写后立即查询的场景，change buffer 的效果不明显，甚至可能增加维护成本。
change buffer vs. redo log
- redo log 主要减少随机写磁盘的 I/O 消耗，将随机写转换为顺序写。
- change buffer 主要减少随机读磁盘的 I/O 消耗，通过缓存更新操作来减少磁盘读取。
【中级】为什么不推荐使用外键？
要点
逻辑外键是一种在应用程序层面上管理和维护数据完整性的方法，而不是通过数据库本身的外键约束。主要是利用应用程序代码来保证引用的完整性。
逻辑外键的优缺点：
优点：
- 灵活性高：应用程序层面控制，可以更灵活地实现复杂的业务逻辑。
- 性能优化：避免了数据库层面的约束检查，可以在某些情况下提高性能（详细看扩展知识）。
- 跨数据库兼容性：逻辑外键在不同类型的数据之间更容易迁移。
缺点：
- 代码复杂性增加：需要在应用程序代码中手动实现和维护引用完整性，增加了代码的复杂性和错误的可能性。
- 一致性风险：如果应用程序代码未正确实现引用完整性检查，可能导致数据不一致。
- 维护成本高：逻辑外键需要开发人员持续关注和维护，增加了维护成本。
物理外键的优缺点：
优点：
- 自动维护引用完整性：数据库会自动检查和维护外键约束，确保数据的一致性。
- 减少应用层复杂性：开发人员不需要手动管理引用完整性，减少了代码的复杂性和错误的可能性。
- 数据完整性保障：数据库层面的约束能够更有效地防止非法数据的插入或更新。
缺点：
- 性能开销：外键约束会增加插入、更新和删除操作的开销，特别是在处理大量数据时。
- 迁移和复制的复杂性：在进行数据库迁移或复制时，外键约束可能会增加复杂性，需要小心处理。
- 灵活性较低：物理外键在某些复杂业务逻辑下可能不够灵活，需要更多的手动控制。
【中级】什么是前缀索引？
要点
“前缀索引”是指索引开始的部分字符。对于 BLOB/TEXT/VARCHAR 这种文本类型的列，必须使用前缀索引，因为数据库往往不允许索引这些列的完整长度。
前缀索引的优点是可以大大节约索引空间，从而提高索引效率。
前缀索引的缺点是会降低索引的区分度。此外，order by 无法使用前缀索引，无法把前缀索引用作覆盖索引。
字段个数索引
【中级】什么是索引最左匹配原则？
要点
不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这里的最左，可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。
如果是联合索引，那么 key 也由多个列组成，同时，索引只能用于查找 key 是否存在（相等），遇到范围查询 (>、<、BETWEEN、LIKE) 就不能进一步匹配了，后续退化为线性查找。因此，列的排列顺序决定了可命中索引的列数。
应该将选择性高的列或基数大的列优先排在多列索引最前列。但有时，也需要考虑 WHERE 子句中的排序、分组和范围条件等因素，这些因素也会对查询性能造成较大影响。“索引的选择性”是指不重复的索引值和记录总数的比值，最大值为 1，此时每个记录都有唯一的索引与其对应。索引的选择性越高，查询效率越高。如果存在多条命中前缀索引的情况，就需要依次扫描，直到最终找到正确记录。
【中级】什么是索引下推？
要点
索引下推是一种减少回表查询、提高查询效率的技术。索引下推主要应用于联合索引。
它允许 MySQL 在使用索引查找数据时，将部分查询条件下推到存储引擎层进行过滤，从而减少需要从表中读取的数据行，减少 IO 操作。
索引下推注意点：
- MySQL 5.6 及以后版本支持索引下推，适用于 InnoDB 和 MyISAM 存储引擎。
- 如果查询中包含子查询，索引下推可能不会生效。
- 使用函数或表达式时，索引下推不会生效。
- 使用聚簇索引（主键）查询时，索引下推不会生效，因为它主要针对非聚簇索引。