MySQL索引探索:解锁高效数据访问的秘密

2023年 7月 19日 167.1k 0

MySQL索引

索引定义

索引是存储引擎用于快速找到记录的一种数据结构。MySQL引入索引的目的是提高查询效率,主要思想是通过空间换时间。

索引分类

我们经常从以下几个方面对索引进行分类:

MySQL索引.png

数据结构分类

下面是MySQL常见存储引擎分别支持的索引:

存储引擎 B+树索引 Hash索引 Full-text索引
Innodb Yes No Yes
MyIsam Yes No Yes
Memory Yes Yes NO

对上表进行横向查看可以了解到,B+tree是MySQL中被存储引擎采用最多的索引类型。

Hash 索引

Hash 索引是比较常见的一种索引,他的单条记录查询的效率很高,时间复杂度为1。但是,Hash索引并不是最常用的数据库索引类型,尤其是我们常用的Mysql Innodb引擎就是不支持hash索引的。主要有以下原因:

  • Hash索引适合精确查找,但是范围查找不适合
  • Hash表还存在Hash函数选择和Hash值冲突等问题。

Full-texts索引

全文索引,通过建立倒排索引,可以极大的提升检索效率,解决判断字段是否包含的问题. 例如: 有title字段,需要查询所有包含 "政府"的记录. 需要 like "%政府%"方式查询,查询速度慢,当查询包含"政府" OR "中国"的需要是,sql难以简单满足.全文索引就可以实现这个功能.

B+树

B+树介绍

B+树索引是一种多路平衡查找树,所有记录节点按照键值大小顺序存放在同一层的叶节点上,各叶节点 通过指针进行链接,它具有如下的特征:

  • 平衡多路查找树:B+树是一种平衡树,它保持所有叶子节点的深度相同,从根节点到叶子节点的路径长度相等或相差不超过1。这使得B+树在插入和删除操作时能够保持树的平衡,提供稳定的性能。
  • 多路性:B+树的每个非叶子节点可以存储多个键值对,这意味着每个节点可以拥有多个子节点。相比于二叉查找树,B+树的每个节点能够存储更多的数据,减少了树的高度,提高了查找效率。
  • 叶子节点存储数据:B+树的所有数据都存储在叶子节点上,而非叶子节点只存储键值信息。这种结构使得范围查询更加高效,因为相关数据在存储上是紧密排列的,减少了磁盘I/O的开销。
  • 有序性:B+树的节点中的键值对按照顺序排列,使得范围查询更加高效。同时,有序性也有助于利用顺序I/O提高读取性能。
  • 分级索引:B+树的非叶子节点可以看作是索引的一部分,它们形成了多级索引结构。这使得B+树能够快速定位到叶子节点,并找到对应的数据。
  • 高度平衡:B+树的平衡性保证了树的高度相对较低。由于每个节点可以存储多个键值对,B+树在存储大量数据时仍能保持相对较小的高度,减少了磁盘I/O的次数。
  • din_btree1.png

    B+树每层能存储多少数据?

    B+树的层数与它能够存储的数据量之间存在一定的关系。每个层级上的节点数量是根据B+树的阶数(Order)来确定的。B+树的阶数定义了一个节点中键值对的最大数量。

    假设B+树的阶数为m,其中根节点为第一层,叶子节点为最底层。根据B+树的特性,除了根节点和叶子节点外,其他层级上的节点都是索引节点。而叶子节点存储实际的数据。

    每个节点中的键值对数量取决于节点的类型。对于非叶子节点,每个节点中的键值对数量范围是 [m/2, m](向上取整)。对于叶子节点,每个节点中的键值对数量范围是 [m/2, m-1](向下取整)。

    其次,每个叶子节点可以存储的数据行数取决于叶子节点的容量以及每行数据的大小。假设叶子节点的容量为c,那么每个叶子节点可以存储的数据行数约等于 c / 每行数据大小。

    因此,如果B+树的层数为m(包括根节点和叶子节点),那么它能够存储的数据量大约为:

    数据量 = m^(h-1)*(c/每行数据大小)

    InnoDB存储引擎的最小存储单元是页,页可以用于存放数据也可以用于存放键值+指针,在B+树中叶子节点存放数据非叶子节点存放键值+指针
    在计算机中,磁盘存储数据最小单元是扇区,一个扇区的大小是512字节。
    文件系统中,最小单位是块,一个块大小就是4k;
    InnoDB存储引擎最小储存单元是页,一页大小就是16k。
    如果一行记录的数据大小为1k,那么单个叶子节点可以存的记录数 =16k/1k =16
    我们假设主键ID为bigint类型,长度为8字节,而指针大小在InnoDB源码中设置为6字节,所以就是8+6=14字节,16k/14B =16*1024B/14B = 1170

    因此,一棵高度为2的B+树,能存放1170^(2-1)(16K/1K) =18720条这样的数据记录。同理一棵高度为3的B+树,能存放1170^(3-1)(16K/1K) =21902400,也就是说,可以存放两千万左右的记录。B+树高度一般为1-3层,已经满足千万级别的数据存储。

    这里的数据量是一个估计值,实际上会受到数据的分布、存储引擎的实现等因素的影响。但它可以给出一个大致的数据存储能力范围。

    B+tree和B-tree

    B+tree是B-Tree(B树)的一个变种。

    B+tree只在叶子节点存储数据,而B-tree非叶子节点也存储数据。

    因此,B+tree单个节点的数量更小,在相同的磁盘IO下能查询更多的节点。

    另外B+tree叶子节点采用单链表链接适合MySQL中常见的基于范围的顺序检索场景,而B-tree无法做到这一点。

    image.png

    B+tree和红黑树

    对于有N个叶子节点的B+tree,搜索复杂度为O(logdN) ,d是指degree是指B+tree的度,表示节点允许的最大子节点个数为d个,在实际的运用中d值是大于100的,即使数据达到千万级别时候B+tree的高度依然维持在3-4左右,保证了3-4次磁盘I/O就能查到目标数据.

    image.png

    B+tree索引与Hash表

    范围查询是MySQL数据库中常见的场景,而Hash表不适合做范围查询,Hash表更适合做等值查询,另外Hash表还存在Hash函数选择和Hash值冲突等问题。

    因为这些原因,B+tree索引要比Hash表索引有更广的适用场景。

    物理存储分类

    当我们基于 InnoDB 引擎创建一张表的时候,都会创建一个聚簇索引,每张表都有唯一的聚簇索引:

  • 如果这张表定义了主键索引,那么这个主键索引就作为聚簇索引。
  • 如果这张表没有定义主键索引,那么该表的第一个唯一非空索引作为聚簇索引。
  • 如果这张表也没有唯一非空索引,那么 InnoDB 内部会生成一个隐藏的主键作为聚簇索引,这个隐藏的主键是一个 6 个字节的列,该列的值会随着数据的插入自增
  • MySQLInnoDB存储引擎中, 聚簇索引与非聚簇索引最大的区别,在于叶节点是否存放一整行记录。聚簇索引叶子节点存储了一整行记录,而非聚簇索引叶子节点存储的是主键信息,因此,一般非聚簇索引还需要回表查询。

    • 一个表中只能拥有一个聚簇索引(因为一般聚簇索引就是主键索引),而非聚集索引一个表则可以存在多个。
    • 一般来说,相对于非聚簇索引,聚簇索引查询效率更高,因为不用回表。

    而在MyISM存储引擎中,它的主键索引,普通索引都是非聚簇索引,因为数据和索引是分开的,叶子节点都使用一个地址指向真正的表数据。

    字段特性分类

    普通索引

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

    name 字段就是一个普通索引(括号外面的是索引名,里边的是索引的字段)。

    唯一索引

    唯一性索引则在普通索引的基础上增加了数据唯一性的约束,一张表中可以同时存在多个唯一性索引,唯一性索引创建方式如下:

    UNIQUE KEY `name` (`name`)
    

    主键索引

    主键索引则是在唯一性索引的基础上又增加了不为空的约束(换言之,添加了唯一性索引的字段,是可以包含 NULL 值的),即 NOT NULL+UNIQUE,一张表里最多只有一个主键索引,当然一个主键索引中可以包含多个字段。

    前缀索引

    在传统的索引创建中,MySQL会为每个索引键存储完整的列值。但是,对于较长的列,比如文本或大型字符串,这样的索引可能会占用大量的存储空间。而前缀索引允许您只存储列值的前几个字符作为索引键,从而减少所需的存储空间。

    要创建前缀索引,您可以在创建索引时指定索引的长度。指定的长度表示将被用于索引的字符数。以下是创建前缀索引的示例:

    CREATE INDEX idx_name ON table1 (name(5));
    

    使用前缀索引时,需要权衡查询性能和索引大小。较短的前缀长度可以减少索引的大小,但可能会导致索引选择性下降,从而降低查询性能。较长的前缀长度可以提高查询性能,但会增加索引的大小。

    字段个数分类

    单列索引

    单列索引是指在单个列上创建的索引。它仅针对表中的单个列进行索引,以提高在该列上的查询性能。单列索引可以是唯一索引或非唯一索引。创建单列索引可以使用以下语法:

    CREATE INDEX index_name ON table_name (column_name);
    

    联合索引

    联合索引是指在多个列上创建的索引。它将多个列的值组合起来作为索引键,以提高涉及这些列的查询性能。联合索引可以是唯一索引或非唯一索引。创建联合索引可以使用以下语法:

    CREATE INDEX index_name ON table_name (column1, column2, ...);
    

    最左前缀原则

    索引的最左前缀原则,可以是联合索引的最左N个字段。比如我们建立一个组合索引(a,b,c),其实可以相当于建了(a),(a,b),(a,b,c)三个索引。

    举个例子,假设有一个联合索引 (column1, column2, column3),并且执行以下查询:

    SELECT * FROM your_table WHERE column1 = 'value1' AND column2 = 'value2';
    

    根据最左匹配原则,MySQL可以利用索引的最左边的两列 (column1, column2) 来定位匹配的行,而不需要扫描整个索引。

    索引优化常见问题

    什么是回表?如何减少回表?

    当查询的数据在索引树中,找不到的时候,需要回到主键索引树中去获取,这个过程叫做回表。

    比如有个表table1,name字段有个普通索引:

    select * from table1 where name='张三';
    

    需要查询所有列的数据,idx_name普通索引不能满足,需要拿到主键id的值后,再回到id主键索引查找获取,这个过程就是回表。

    什么是覆盖索引?

    我们将上面的查询SQLselect * 修改为 select id, name的话,其实是不需要回表的。因为idname的值,都在idx_name索引树的叶子节点上。

    覆盖索引是select的数据列只用从索引中就能够取得,不必回表,换句话说,查询列要被所建的索引覆盖。

    什么是索引下推?

    给你这个SQL:

    select * from employee where name like '小%' and age=28 and sex='0';
    

    其中,nameage为联合索引(idx_name_age)。

    如果是Mysql5.6之前,在idx_name_age索引树,找出所有名字第一个字是“小”的人,拿到它们的主键id,然后回表找出数据行,再去对比年龄和性别等其他字段。如图:

    图片

    有些朋友可能觉得奇怪,idx_name_age(name,age)不是联合索引嘛?为什么选出包含“小”字后,不再顺便看下年龄age再回表呢,不是更高效嘛?所以呀,MySQL 5.6就引入了索引下推优化,可以在索引遍历过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数。

    因此,MySQL5.6版本之后,选出包含“小”字后,顺表过滤age=28

    图片

    大表如何添加索引

    如果一张表数据量级是千万级别以上的,那么,如何给这张表添加索引?

    我们需要知道一点,给表添加索引的时候,是会对表加锁的。如果不谨慎操作,有可能出现生产事故的。可以参考以下方法:

  • 先创建一张跟原表A数据结构相同的新表B
  • 在新表B添加需要加上的新索引。
  • 把原表A数据导到新表B
  • rename新表B为原表的表名A,原表A换别的表名;
  • 如何知道语句是否走索引查询?

    explain查看SQL的执行计划,这样就知道是否命中索引了。

    explainSQL一起使用时,MySQL将显示来自优化器的有关语句执行计划的信息。例如:EXPLAIN SELECT * FROM your_table WHERE column = 'value';。执行这个语句后,MySQL会返回一个解释计划(Execution Plan),其中包含有关查询执行的信息。您可以检查EXPLAIN结果中的"key"列,它显示了被选择用于查询的索引。如果在该列中出现了索引的名称,表示该查询使用了索引。

    一般来说,我们需要重点关注type、rows、filtered、extra、key

    type

    type表示连接类型,查看索引执行情况的一个重要指标。以下性能从好到坏依次:system > const > eq_ref > ref > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL

    • system:这种类型要求数据库表中只有一条数据,是const类型的一个特例,一般情况下是不会出现的。
    • const:通过一次索引就能找到数据,一般用于主键或唯一索引作为条件,这类扫描效率极高,,速度非常快。
    • eq_ref:常用于主键或唯一索引扫描,一般指使用主键的关联查询
    • ref : 常用于非主键和唯一索引扫描。
    • ref_or_null:这种连接类型类似于ref,区别在于MySQL会额外搜索包含NULL值的行
    • index_merge:使用了索引合并优化方法,查询使用了两个以上的索引。
    • unique_subquery:类似于eq_ref,条件用了in子查询
    • index_subquery:区别于unique_subquery,用于非唯一索引,可以返回重复值。
    • range:常用于范围查询,比如:between ... and 或 In 等操作
    • index:全索引扫描
    • ALL:全表扫描

    rows

    该列表示MySQL估算要找到我们所需的记录,需要读取的行数。对于InnoDB表,此数字是估计值,并非一定是个准确值。

    filtered

    该列是一个百分比的值,表里符合条件的记录数的百分比。简单点说,这个字段表示存储引擎返回的数据在经过过滤后,剩下满足条件的记录数量的比例。

    extra

    该字段包含有关MySQL如何解析查询的其他信息,它一般会出现这几个值:

    • Using filesort:表示按文件排序,一般是在指定的排序和索引排序不一致的情况才会出现。一般见于order by语句
    • Using index :表示是否用了覆盖索引。
    • Using temporary: 表示是否使用了临时表,性能特别差,需要重点优化。一般多见于group by语句,或者union语句。
    • Using where : 表示使用了where条件过滤.
    • Using index condition:MySQL5.6之后新增的索引下推。在存储引擎层进行数据过滤,而不是在服务层过滤,利用索引现有的数据减少回表的数据。
    key

    该列表示实际用到的索引。一般配合possible_keys列一起看。

    相关文章

    Oracle如何使用授予和撤销权限的语法和示例
    Awesome Project: 探索 MatrixOrigin 云原生分布式数据库
    下载丨66页PDF,云和恩墨技术通讯(2024年7月刊)
    社区版oceanbase安装
    Oracle 导出CSV工具-sqluldr2
    ETL数据集成丨快速将MySQL数据迁移至Doris数据库

    发布评论