Mysql索引-面试题

索引用于快速查询和检索数据，本质可以看成是一种排序好的数据结构

索引底层：B+树

索引的作用：

• 唯一索引 --> 保证数据表中的每一行数据的唯一性。
• 减少检索数据量，减少IO次数。

索引底层数据结构

Hash表

哈希表是键值对的集合，通过Key查询对应Value，哈希表可以快速检索数据O(1)
如何通过Key快速取出Value ？ --> 哈希算法（散列算法）

快速找到key对应的index ，找到index也就找到对应的value

存在问题：Hash冲突

Hash冲突：不同的key最后得到的index相同

解决： 链表地址法（1.8之前）、红黑树（1.8之后）

二叉查找树（BST）

性质：左小右大

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

当二叉查找树平衡（树的每个节点的左右子树深度相差不超过 1），查询的时间复杂度为 O(log2(N))，具有比较高的效率。然而，当二叉查找树不平衡时，例如在最坏情况下（有序插入节点），树会退化成线性链表（也被称为斜树），导致查询效率急剧下降，时间复杂退化为 O（N）。

二叉查找树的性能非常依赖于它的平衡程度，这就导致其不适合作为 MySQL 底层索引的数据结构。

AVL（自平衡二叉查找）树

性质：任何节点的左右子树高度差不超过1，因此也被称为高度平衡二叉树，它的查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn)。

实现：采用了旋转操作来保持平衡。主要有四种旋转操作：LL 旋转、RR 旋转、LR 旋转和 RL 旋转。

由于 AVL 树需要频繁地进行旋转操作来保持平衡，因此会有较大的计算开销进而降低了数据库写操作的性能。并且， 在使用 AVL 树时，每个树节点仅存储一个数据，而每次进行磁盘 IO 时只能读取一个节点的数据，如果需要查询的数据分布在多个节点上，那么就需要进行多次磁盘 IO。 磁盘 IO 是一项耗时的操作，在设计数据库索引时，我们需要优先考虑如何最大限度地减少磁盘 IO 操作的次数。所以，实际应用中，AVL 树使用的并不多。

红黑树

红黑树是一种自平衡二叉查找树，通过在插入和删除节点时进行颜色变换和旋转操作，使得树始终保持平衡状态，它具有以下特点：

1. 每个节点非红即黑；
2. 根节点总是黑色的；
3. 每个叶子节点都是黑色的空节点（NIL 节点）；
4. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
5. 从任意节点到它的叶子节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。

和 AVL 树不同的是，红黑树并不追求严格的平衡，而是大致的平衡。正因如此，红黑树的查询效率稍有下降，因为红黑树的平衡性相对较弱，可能会导致树的高度较高，这可能会导致一些数据需要进行多次磁盘 IO 操作才能查询到，这也是 MySQL 没有选择红黑树的主要原因。也正因如此，红黑树的插入和删除操作效率大大提高了，因为红黑树在插入和删除节点时只需进行 O(1) 次数的旋转和变色操作，即可保持基本平衡状态，而不需要像 AVL 树一样进行 O(logn) 次数的旋转操作。

红黑树的应用还是比较广泛的，TreeMap、TreeSet 以及 JDK1.8 的 HashMap 底层都用到了红黑树。对于数据在内存中的这种情况来说，红黑树的表现是非常优异的。

B树 和 B+树

异同：

• B 树的所有节点既存放键(key) 也存放数据(data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
• B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
• B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。
• 在 B 树中进行范围查询时，首先找到要查找的下限，然后对 B 树进行中序遍历，直到找到查找的上限；而 B+树的范围查询，只需要对链表进行遍历即可。

综上，B+树与 B 树相比，具备更少的 IO 次数、更稳定的查询效率和更适于范围查询这些优势。

聚簇索引 && 非聚簇索引

聚簇索引（聚集索引）：树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。而其余的索引都作为 辅助索引 ，辅助索引的 data 域存储相应记录主键的值而不是地址。 --> 索引和数据不分开存放的索引。

InnoDB 中的主键索引就属于聚簇索引。

在 MySQL 中，InnoDB 引擎的表的 .ibd文件就包含了该表的索引和数据，对于 InnoDB 引擎表来说，该表的索引(B+树)的每个非叶子节点存储索引，叶子节点存储索引和索引对应的数据。

优点：

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

缺点：

• 依赖于有序的数据：因为 B+树是多路平衡树，如果索引的数据不是有序的，那么就需要在插入时排序，如果数据是整型还好，否则类似于字符串或 UUID 这种又长又难比较的数据，插入或查找的速度肯定比较慢。
• 更新代价大：如果对索引列的数据被修改时，那么对应的索引也将会被修改，而且聚簇索引的叶子节点还存放着数据，修改代价肯定是较大的，所以对于主键索引来说，主键一般都是不可被修改的。

非聚簇索引（非聚集索引）：B+Tree 叶节点的 data 域存放的是数据记录的地址。在索引检索的时候，首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，则取出其 data 域的值，然后以 data 域的值为地址读取相应的数据记录。 --> 索引和数据存放在一起的索引。

二级索引(辅助索引)就属于非聚簇索引。

非聚簇索引的叶子节点并不一定存放数据的指针，因为二级索引的叶子节点存放的是主键，根据主键再回表查数据。

优点：

更新代价比聚簇索引要小 。非聚簇索引的更新代价就没有聚簇索引那么大了，非聚簇索引的叶子节点是不存放数据的。

缺点：

• 依赖于有序的数据:跟聚簇索引一样，非聚簇索引也依赖于有序的数据
• 可能会二次查询(回表):这应该是非聚簇索引最大的缺点了。 当查到索引对应的指针或主键后，可能还需要根据指针或主键再到数据文件或表中查询。

联合索引

面试题：（知识点：最左前缀匹配原则）

1. 如果有索引联合索引（a、b、c），查询a = 1 AND c = 1会走索引么？c = 1 呢？b = 1 AND c = 1呢

• 查询 a=1 AND c=1：根据最左前缀匹配原则，查询可以使用索引的前缀部分。因此，该查询仅在 a=1 上使用索引，然后对结果进行 c=1 的过滤。

• 查询 c=1 ：由于查询中不包含最左列 a，根据最左前缀匹配原则，整个索引都无法被使用。

• 查询b=1 AND c=1：和第二种一样的情况，整个索引都不会使用。

隐藏索引

解决问题：

数据库中新版本可能会引入：

• 新增字段。
• 表重构。
• 创建/修改索引。

灰度发布：逐步发布新版本的技术。简单来说就是：将新版本或新功能逐步推送给部分用户，一般在真实的测试环境中测试新版本的稳定性和用户反馈，当验证新版本无重大问题的时候，次啊逐步拓展到所有用户。

目的：通过流量逐步引导和回滚机制确保新版本的稳定性和兼容性。使用K8S、负载均衡器、服务网格等技术可以实现灵活的灰度发布流程，并结合监控和反馈软件，确保线上环境的安全和稳定。

使用索引的建议

选择合适的字段创建索引

• 不为NULL的字段
• 频繁被查询的字段
• 被作为条件查询的字段
• 频繁需要排序的字段
• 连接表的的查询条件字段

注意：频繁更新的字段 “慎” 用索引

字符串使用前缀索引代替普通索引。

面试题

1. Mysql索引失效的场景有哪些？

• 索引建立不当 或 使用顺序未遵循最左匹配原则
  • 最左匹配原则顾名思义：最左优先，以最左边的为起点任何连续的索引都能匹配上。同时遇到范围查询(>、<、between、like)就会停止匹配。
• 索引列上使用了函数
• 索引列上有计算操作
• Like左边包含%
• 使用OR关键字
• In使用不当
• not in 和 not exists
• order By 使用不当

分析SQL语句是否走索引查询

使用EXPLAIN命令来分析SQL的执行计划（一条SQL在经过Mysql查询优化器的优化后，具体的执行方案）

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)

各个字段的含义如下：