MySQL索引学习

索引数据结构

什么是索引？为什么索引能加快查询？

索引的数据结构是什么？

B+树和B树、红黑树有什么区别？为什么使用B+树？

索引是一种排好序的快速查找的数据结构。在索引上查找数据的过程可以类比在二叉搜索树上进行数据查询，可以根据数据的大小关系省略对一些数据的查询操作，从而减少磁盘I/O的次数，加快查询效率。

索引的具体实现由底层的存储引擎决定，例如在InnoDB存储引擎下，索引是由B+树实现的。

B树和B+树都是通过多叉树的形式，将树的高度降低，以此减少磁盘I/O的次数。但较于B树，B+树有以下优点：

• B+的树非叶子节点不存放数据只存放索引，而B树的内节点既存数据又存索引。因此数据量相同的情况下，B+树的内节点可以存放更多的索引，这使得B+树可以比B树更“矮胖”，查询底层节点时磁盘I/O次数更少
• B+树有大量的冗余节点（所有非叶子节点都是冗余节点），这些冗余节点使得B+树在插入、删除的情况下，树形变化不大，效率更高
• B+树的叶子节点之间通过链表相互连接，有利于范围查询

索引存储

堆表和索引组织有什么区别？分别应用场景是什么？

在堆表的组织中，数据和索引是分开存储的，B+树叶子节点存放的是索引+数据的地址，地址指向堆表中的数据。索引是排序后的数据，而堆表中的数据是无序的

• 堆表中的索引都是二级索引，即使是主键索引也是二级索引，每次查询都要回表
• 由于索引的叶子节点存放了数据在堆表中的地址，当堆表的数据发生变化且位置发生了改变，那么所有索引中的地址都要进行变更
• 只支持表锁，并发性能差

在索引组织表（聚簇索引，InnoDB存储引擎实现的数据组织方式）中，数据和索引是一起存储在B+树中的，B+树叶子节点存放的是索引+行记录。

索引就是数据，数据就是索引

• 索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
• 在索引组织表中，二级索引具有天然优势：若记录发生了改变，其他索引无须进行维护，除非记录的主键发生了改变
• 支持行级锁，并发性能高

联合索引

aba

索引失效

有哪些索引失效的场景？为什么会失效？

• 对索引使用左或者左右模糊匹配

  • B+树索引是按照索引值有序排列存储的，只能根据前缀进行匹配比较

• 对索引使用函数

  • 索引保存的是索引字段的原始值，而不是经过函数计算后的结果，自然不能进行索引比较

• 对索引进行表达式计算

  • 索引保存的是索引字段的原始值，而不是经过表达式计算后的结果，自然不能进行索引比较

• 对索引隐式类型转换

  • MySQL在遇到字符串和数字比较时，会先将字符串转换成数字，再进行数字比大小

  • 如下两条SQL语句，第一条索引失效，第二条索引正常工作

  • # 先将name转换为整型数字，再进行比较
    select * from users where name = 101010
    # 等价于 select * from users where cast(name as signed int) = 101010
    
    
    select * from users where id = '1'
    # 等价于 select * from users where id = cast('1' as signed int)
    
    - 联合索引非最左匹配
    
      - 联合索引是先按照第一个索引键排序，再按照第二个索引键排序，以此类推
    
    - where子句中的or
    
      - or前的条件列是索引列，而or后的条件列不是索引列则会导致索引失效
    
    ## 索引选择
    
    > MySQL数据库中的优化器是怎么执行的？根据什么标准选择索引的？
    
    ![image-20240916132934153](https://raw.githubusercontent.com/lyydsheep/pic/main/202409161330104.png)
    
    MySQL数据库由Server层和Engine层组成：
    
    - Server层有SQL分析器、SQL优化器、SQL执行器，用于负责SQL语句的具体执行过程
    - Engine层用于存储具体的数据，例如InnoDB引擎，还有用于在内存中存储临时结果集的TempTable引擎
    
    其中SQL优化器用于分析SQL语句在使用不同索引时所需要的成本，并选择成本最小的执行计划（或全局扫描），作为SQL最优执行方案，这种优化器也叫做CBO（Cost-based optimizer）优化器
    
    在MySQL中，一条SQL的计算成本按如下公式计算：
    
    ```sql
    Cost = Server Cost + Engine Cost
    	 = CPU Cost + IO Cost
    

基于SQL优化器的工作原理，有如下实际案例经验：

• 一般只对高选择度的字段和字段组合建立索引，低选择度的字段如性别，不创建索引

• 低选择性，但是存在数据倾斜，例如优化器认为P状态有1/3，实际上P状态只有1/100，可以考虑创建索引

  • 通过创建直方图，让优化器知道实际的数据分布

  • ANALYZE TABLE orders 
    
    UPDATE HISTOGRAM ON o_orderstatus;
    
    ## 索引应用
    
    > 建立索引有什么优点和缺点？
    >
    > 如何正确建立索引？
    >
    > 哪些场景下适合建立索引？
    >
    > 哪些场景下不适合建立索引？
    
    可以参考[原文](https://juejin.cn/post/7149074488649318431)
    
    ### 一、MySQL中各索引分析
    
    #### 1.1 为什么选自增Id作为主键？
    
    在MySQL表中，一般都是用**自增Id**作为主键，这确保了数据的唯一性，但为什么又需要**自增**性质？
    
    在InnoDB存储引擎中，主键索引以聚簇的形式**有序**存储，即索引即数据、数据即索引按照主键大小依次排列存储在磁盘上。如果使用无序的uuid作为主键，虽然uuid也能保证数据的唯一性，但是很有可能会破坏原本的树结构
    
    举个例子：
    
    灰色节点作为一条新数据，如果按照**uuid大小排列**，它应该插入在第二个位置，那么后续节点都要挪动，时间复杂度（不小于）$$O(n)$$，这就导致插入数据十分占用CPU资源。
    
    ![image-20240917114122420](https://raw.githubusercontent.com/lyydsheep/pic/main/202409171141423.png)
    
    但使用**自增Id**就不会有这个问题，新来的数据直接放到最后，因此数据表的主键值最好选用带有顺序性的值。
    
    #### 1.2 联合索引的最左匹配原则
    
    > 最左匹配原则就是指在联合索引中，如果你的 SQL 语句中用到了联合索引中的最左边的索引，那么这条 SQL 语句就可以利用这个联合索引去进行匹配。
    
    为`id, name, age`这三个字段建立联合索引，此时一个SQL语句如下：
    
    ```sql
    SELECT * FROM users WHERE name = 'lyydsheep' AND age = 1;
    

这条SQL语句是用不上联合索引的，因为查询条件中没有出现从最左端开始的连续字段。而下列这条SQL语句就能使用上联合索引

SELECT * FROM users WHERE id = 1 AND name = 'lyydsheep';

根本原因就是id字段是全局有序，而name、age字段是局部有序的

1.3 唯一索引的快慢问题

唯一索引相比于普通索引的优势就在于唯一索引限定了字段值必须是唯一的，当找到一条数据后旧立马停止检索。而普通索引仍需要走完整个索引树，因为可能存在多个相同的字段值的数据。

唯一索引在查询时比普通索引快上一截，但插入数据时就不同了，因为要确保数据唯一性，插入数据前要检察一遍表中是否存在相同的数据。普通索引就没有这顾虑了，因此普通索引插入数据会更快一些。

二、建立索引的原则

2.1 应该遵守的原则

• ①经常频繁用作查询条件的字段应酌情考虑为其创建索引。

• ②表的主外键或连表字段，必须建立索引，因为能很大程度提升连表查询的性能。

• ③建立索引的字段，一般值的区分性要足够高，这样才能提高索引的检索效率。

• ④建立索引的字段，值不应该过长，如果较长的字段要建立索引，可以选择前缀索引。

• ⑤建立联合索引，应当遵循最左前缀原则，将多个字段之间按优先级顺序组合。

• ⑥经常根据范围取值、排序、分组的字段应建立索引，因为索引有序，能加快排序时间。

• ⑦对于唯一索引，如果确认不会利用该字段排序，那可以将结构改为Hash结构。

• ⑧尽量使用联合索引代替单值索引，联合索引比多个单值索引查询效率要高。

2.2 额外的注意点

• ❶值经常会增删改的字段，不合适建立索引，因为每次改变后需维护索引结构。

• ❷一个字段存在大量的重复值时，不适合建立索引，比如之前举例的性别字段。

• ❸索引不能参与计算，因此经常带函数查询的字段，并不适合建立索引。

• ❹一张表中的索引数量并不是越多越好，一般控制在3，最多不能超过5。

• ❺建立联合索引时，一定要考虑优先级，查询频率最高的字段应当放首位。

• ❻当表的数据较少，不应当建立索引，因为数据量不大时，维护索引反而开销更大。

• ❼索引的字段值无序时，不推荐建立索引，因为会造成页分裂，尤其是主键索引。

索引常见考题

参考原文

索引的分类

从四个角度对索引进行分类：

• 以数据结构分类：B+树索引、Hash索引、Full-text索引
• 以物理存储分类：聚簇索引、二级索引
• 以字段特性分类：主键索引、唯一索引、普通索引、前缀索引
• 以字段个数分类：单列索引、联合索引

按数据结构分类

不同的存储引擎所支持的索引类型不同，具体如下图

按物理存储分类

• 聚簇索引的B+树叶子节点存放的是实际数据，包含了数据行所有字段的数据
• 二级索引的B+树叶子节点存放的是主键值，并非实际数据。因此，如果所查询数据不二级索引叶子节点中，那么需要再进行一次回表操作；反之则是索引覆盖

按字段特性分类

主键索引

建立在主键之上的索引，一般在建表时创建，一张表最多只能有一个主键索引，并且主键字段不允许有NULL值

如果没有指明主键，则系统会按照一下规则挑选并创建主键索引

• 选择第一个不包含NULL值的唯一列作为主键列
• 下下策，InnoDB自动生成一个自增的隐藏id列作为聚簇索引的索引键

建表时，创建主键索引的方式如下：

CREATE TABLE table_name (
    ...
    PRIMARY KEY (column_name) USING BTREE
)

唯一索引

建立在UNIQUE字段上的索引，一张表可以有多个唯一索引，但是索引键值必须唯一，允许有NULL值

建表时，创建唯一索引的方式如下：

CREATE TABLE table_name(
    ...
    UNIQUE KEY(column1, column2...)
)

建表后，创建唯一索引的方式如下：

CREATE UNIQUE INDEX idx_name ON table_name(column1, column2...)

前缀索引

以字符类型字段的前缀为键值建立索引，主要目的是为了减少存储空间，优化查询效率，可以用在字符类型为char、varchat、binary、varbinary的列上

建表时，创建前缀索引的方式如下：

CREATE TABLE table_name(
    ...
    INDEX(column1(length))
)

建表后，创建前缀索引的方式如下 :

CREATE INDEX idx_name ON table_name (column1(length))

按字段个数分类

主要介绍联合索引的几个特点

• 范围查询
  • 联合索引的最左匹配，在遇到范围查询（>、<）时，就会停止匹配。也就是说，范围查询的字段会用到联合索引，但之后的字段不会使用联合索引
  • 值得注意的是，对于>=、<=、between xxx and、like这类含有相等意义的范围查询，不会立刻停止匹配，即再范围查询之后的字段仍会用上联合索引，但只针对部分数据
• 索引下推
  • MySQL 5.6 引入索引下推优化，可以在联合索引遍历过程中，利用联合索引中未用上的查询条件对数据进行过滤，减少回表次数
• 索引区分度
  • 在建立联合索引时，要尽可能 把区分度大的字段放在前面，这样联合索引被SQL用到的概率更大
• 用于排序
  • 减少Using filesort的次数

优化索引的方法

• 前缀索引优化
  • 使用前缀索引可以减小索引字段的大小，增加一个索引页中存储的数据量，有效提高索引查询的效率
• 覆盖索引优化
  • 将所要查询的字段建立成联合索引，在SQL查询过程中就能在二级索引B+树的叶子节点上找到所需要的全部数据，而不需要再通过聚簇索引查询获得，减少回表的操作
• 主键索引最好是自增的
  • 插入一条数据都是追加操作，不需要移动数据，避免了页分裂带来的性能消耗和大量的内存碎片
  • 索引字段不宜过长，减少二级索引的存储空间
• 索引最好设置为NOT NULL
  • 索引列存在NULL值会加重索引选择的负担
  • 减少物理存储空间，如果表中存在允许为NULL的字段，那么行格式中至少会占用1字节空间存储NULL值列表
• 防止索引失效