![MySQL:(一)索引底层原理与实现](/img/index.png)
MySQL:(一)索引底层原理与实现
一、 什么是索引?
索引是一个排序的列表,在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址,可以大大加快查询的速度,使用索引后可以不用扫描全表来定位某行的数据,而是先通过索引表找到该行数据对应的物理地址然后访问相应的数据。索引的作用类似于书的目录,可以根据目录中的页码快速找到所需的内容。
1.1 索引概述(了解)
当数据保存在磁盘类存储介质上时,它是作为数据块存放。这些数据块是被当作一个整体来访问的,这样可以保证操作的原子性。硬盘数据块存储结构类似于链表,都包含数据部分,以及一个指向下一个节点(或数据块)的指针,不需要连续存储。
记录集只能在某个关键字段上进行排序,所以如果需要在一个无序字段上进行搜索,就要执行一个线性搜索(Linear Search)的过程,平均需要访问 N/2 的数据块,N 是表示所占据的数据块数目。如果这个字段是一个非主键字段(也就是说,不包含唯一的访问入口), 那么需要在 N 个数据块上搜索整个表格空间。
但是对于一个有序字段,可以运用二分查找(BinarySearch),这样只需要访问 log2(N)的数据块。这就是为什么数据表使用索引后性能可以得到本质上提高的原因。
索引是对记录集的多个字段进行排序的方法。在一张表中为一个字段创建一个索引,将创建另外一个数据结构,包含字段数值以及指向相关记录的指针,然后对这个索引结构进行排序,允许在该数据上进行二分法排序。索引需要额外的磁盘空间。
对于 MyISAM 引擎而言,这些索引是被统一保存在一张表中的。如果很多字段都建立了索引,那么会占用大量的磁盘空间,这个文件将很快到达底层文件系统所能够支持的大小限制。
1.1.1 索引的作用
索引除了快没有其他的作用,数据库利用各种各样的快速定位技术,能够大大提高查询效率。特别是当数据量非常大,查询涉及多个表时,使用索引往往能使查询速度加快成千上万倍。
1.1.2 索引的查找过程
举一个例子,三个表t1、t2、t3,每个表中只有一个字段,但是每一个表中都有1000行记录,这些记录都是1~1000的数字。
执行以下的查找语句
1 | mysql>SELECT c1,c2,c3 FROM t1,t2,t3 WHERE c1=c2 AND c1=c3; |
在无索引的情况下处理此查询, 必须寻找 3 个表所有的组合,以便得出与 WHERE 子句相配的那些行。而可能的组合数目 为 1000×1000×1000(十亿)
如果对每个表进行索引,就能极大地加速查询进程,利用索引的查询处理如下。
从表 t1 中选择第一行,查看此行所包含的数据。
使用表 t2 上的索引,直接定位 t2 中与 t1 的值匹配的行。同理,利用表 t3 上的索引, 直接定位 t3 中与 t1 的值匹配的行。
扫描表 t1 的下一行并重复前面的过程,直到遍历 t1 中所有的行。
在这样的情况下,对表 t1 执行了一个完全扫描,但能够在表 t2 和 t3 上进行索引查找直接取出这些表中的行,比未用索引时要快一百万倍。
利用索引,MySQL 加速了 WHERE 子句满足条件行的搜索,而在多表连接查询时、在执行连接时加快了与其他表中的行匹配的速度。
二、索引的分类(逻辑分类)
逻辑的角度来划分,索引分为普通索引、唯一索引、主键索引、组合索引和全文索引。
2.1 普通索引
2.1.1 普通索引格式
普通索引是最基本的索引,它没有任何限制,也是大多数情况下用到的索引。
直接创建索引的方式
1 | # column 是指定要创建索引的列名 |
索引列的长度有一个最大上限 255 个字节(MyISAM 和 InnoDB 表的最大上限为 1000 个字 节),如果索引列的长度超过了这个上限,就只能用列的前缀进行索引。另外,BLOB 或 TEXT 类型的列也必须使用前缀索引。
2.1.2 创建普通索引
方法一:
1 | mysql> create table info (id int(4) not null,name varchar(10) not null,address varchar(50) default '未知'); ##创建一个表结构 |
方法二:
1 | 修改表结构的方式添加索引 |
1 | mysql> alter table info add index name_index (name); |
方法三:
在创建一个表结构时,就创建索引
1 | mysql> create table num (id int(3),index id_index(id)); |
1 | mysql> describe num; |
2.1.3 查看索引
1 | mysql> show index from info\G; |
2.2 唯一索引
唯一索引与普通索引类似,不同的就是:唯一索引的索引列的值必须唯一,但允许有空值(注意和主键不同)。如果是组合索引,则列值的组合必须唯一。唯一索引创建方法和普通索引类似。
1 | # 修改表结构的时候添加唯一索引: |
新建一个表
1 | mysql> create table info2 (id int(4) not null,name varchar(10) not null,address varchar(50) default '未知',primary key(id)); |
修改表结构的时候添加唯一索引:
1 | 格式 |
创建表的时候同时创建唯一索引:
1 | CREATETABLE`table`( |
2.3 主键索引
主键索引是一种特殊的唯一索引,一个表只能有一个主键,不允许有空值。一般是在建表的时候同时创建主键索引。
主键索引也就是primary key,在之前的创建表的过程中已经演示过,有两种方式。
第一种:在字段外创建
1 | mysql> create table info2 (id int(4) not null,name varchar(10) not null,address varchar(50) default '未知',primary key(id)); |
第二种:在字段内创建
1 | mysql> create table info2 (id int(4) not null primary key,name varchar(10) not null,address varchar(50) default '未知'); |
2.4 联合索引(组合索引)
组合索引,也称为联合索引,复合索引或多列索引,是指索引同时包含多个列。在创建联合索引时,可以指定多个列名,以逗号分隔。联合索引的列顺序非常重要,因为查询时使用了联合索引中的一部分列时,这些列必须按照联合索引中的顺序出现。联合索引可以应用于需要根据多个列进行查询、排序、范围查询或分组的场景,以提高这些操作的效率。
平时用的 SQL 查询语句一般都有比较多的限制条件,所以为了进一步榨取 MySQL 的效率,就要考虑建立组合索引。在组合索引的创建中,有两种场景,即为单列索引和多列索引。
特点:
遵从最左原则,从左往右依次执行
2.5 全文索引
对于较大的数据集,将资料输入一个没有 FULLTEXT 索引的表中,然后创建索引,其 速度比把资料输入现有 FULLTEXT 索引的速度更快。不过切记对于大容量的数据表,生成全文索引是一个非常消耗时间、非常消耗硬盘空间的做法。
1 | mysql> alter table info2 add fulltext index addr_index(address); ##创建全文索引 |
2.6 覆盖索引
覆盖索引是指一个索引包含了所有需要查询的列,即查询语句中的SELECT字段全部在索引中,通过索引就可以直接获取查询结果,而无需回表查询数据行。这种索引方式可以显著提高查询性能,因为它减少了磁盘I/O操作。需要注意的是,覆盖索引并不是针对某次查询而言的,而是指索引本身包含了查询所需的所有列。
联合索引和覆盖索引的区别
- 区别:覆盖索引关注的是索引是否包含了查询所需的所有列,而联合索引关注的是索引是否同时包含了多个列。一个索引可以是覆盖索引但不一定是联合索引(如只包含一个列的索引且该列满足查询需求),也可以是联合索引但不一定是覆盖索引(如包含多个列但查询还需要其他列的数据)。
- 联系:在某些情况下,一个联合索引也可以是覆盖索引,即当查询语句中的SELECT字段全部包含在联合索引中时。此时,联合索引不仅提高了查询效率(因为可以同时利用多个列进行索引),还因为包含了查询所需的所有列而实现了覆盖索引的效果。
三、 查看及删除索引
3.1 查看索引
1 | 查看索引的两种方法 |
以show keys from tablename为例,两种方法用法相同
1 | mysql> show keys from info2; |
可以使用 mysql> show keys from info2\G;使用显示结果更加直观
1 | mysql> mysql> show keys from info2\G; |
Table:表的名称。
Non_unique:如果索引不能包括重复词,则为 0;如果可以,则为 1。
Key_name:索引的名称。
Seq_in_index:索引中的列序号,从 1 开始。
Column_name:列名称。
Collation:列以什么方式存储在索引中。在 MySQL 中,有值‘A’(升序)或 NULL(无分类)。
Cardinality:索引中唯一值数目的估计值。通过运行 ANALYZETABLE 或 myisamchk-a可以更新。基数根据被存储为整数的统计数据来计数,所以即使对于小型表,该值也没 有必要是精确的。基数越大,当进行联合时,MySQL 使用该索引的机会就越大。
Sub_part:如果列只是被部分地编入索引,则为被编入索引的字符的数目。如果整列 被编入索引,则为 NULL。
Packed:指示关键字如何被压缩。如果没有被压缩,则为 NULL。
Null:如果列含有 NULL,则含有 YES。如果没有,则该列含有 NO。
Index_type:用过的索引方法(BTREE, FULLTEXT,HASH, RTREE)。
Comment:备注。
3.2 删除索引
索引在创建之后,是会占用一定的磁盘空间的,因此表内如果有不再使用的索引,从数据库性能方面考虑,最好是删除无用索引。
1 | 删除索引的两种方式 |
1 | mysql> drop index addr_index on info2; ##删除刚刚创建的全文索引 |
四、 索引的底层原理
4.1 八股:数据结构
Mysql数据库中的常见索引结构有多种,常用Hash,B+树(最常用,多路搜索树)等数据结构来进行数据存储。树的深度加深一层,意味着多一次查询,对于数据库磁盘而言,就是多一次IO操作,导致查询效率低下。
创建一次索引就代表了创建了一个数据结构,例如B+树。那么创建的是联合索引的时候,首先根据第一个字段排序,然后在根据第二个排序。联合索引也是只有一棵b+树。
B+树的特征:
- 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
- 不可能在非叶子结点命中;
- 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
- 每一个叶子节点都包含指向下一个叶子节点的指针,从而方便叶子节点的范围遍历。
- 更适合文件索引系统;
此处讨论B+树,结合案例见4.3。
4.2 八股:存储引擎
常见的有InnoDB、MyASIM(不支持数据库事务)、Memory等。存储引擎和存储方式(磁盘等)见文章:MySQL体系构架、存储引擎和索引结构
此处使用InnoDB来讨论索引的存储结构,见4.3。
4.3 八股:InnoDB B+树存储数据结构
存储数据结构,也是索引分类的一种:物理分类(第二章讲了逻辑分类)。物理分类分为聚簇索引和非聚簇索引。存储数据结构虽然说是索引分类的一种,但是准确的来说,聚簇索引和非聚簇索引是一种数据的存储方式。
聚簇索引(clustered index)不是单独的一种索引类型,而是一种数据存储方式。这种存储方式是依靠B+树来实现的,根据表的主键构造一棵B+树且B+树叶子节点存放的都是表的行记录数据时,方可称该主键索引为聚簇索引。聚簇索引也可理解为将数据存储与索引放到了一块,找到索引也就找到了数据。
非聚簇索引(辅助索引或者二级索引):数据和索引是分开的,非聚簇索引的叶子节点并不存储数据表中的完整数据记录。相反,它们存储的是指向数据表中相应行的指针,这个指针通常是数据表中主键的值。
虽然InnoDB和MyISAM存储引擎都默认使用B+树结构存储索引,但是只有InnoDB的主键索引(主键索引见2.3)才是聚簇索引,InnoDB中的辅助索引以及MyISAM使用的都是非聚簇索引。
使用聚簇索引的优缺点(面试):
优点:
- 数据访问更快,因为聚簇索引将索引和数据保存在同一个B+树中,因此从聚簇索引中获取数据比非聚簇索引更快
- 聚簇索引对于主键的排序查找和范围查找速度非常快
缺点:
插入速度严重依赖于插入顺序,按照主键的顺序插入是最快的方式,否则将会出现页分裂(页分裂见链接和下图),严重影响性能。因此,对于InnoDB表,我们一般都会定义一个自增的ID列为主键(主键列不要选没有意义的自增列,选经常查询的条件列才好,不然无法体现其主键索引性能)
更新主键的代价很高,因为将会导致被更新的行移动。因此,对于InnoDB表,我们一般定义主键为不可更新。
二级索引(非聚簇索引)访问需要两次索引查找,第一次找到主键值,第二次根据主键值找到行数据。
4.4 八股:回表是什么?为什么会有回表?
在4.3的聚簇索引中,我们提到缺点的第三条,非聚簇索引需要两次索引查找,这个过程我们就称为回表。
为什么会有回表?我们刚说到,聚簇索引是将索引和数据存储放在一起的,所以找到索引了就是找到了数据。但是根据实际查询的要求,不一定只会根据主键去查询数据。我们看以下场景:
假如有个表T, 里面三个字段:id k name, id为主键,并且其中对k建立了单独索引。此时有两棵B+树,一个是聚簇索引(主键索引)的B+树,一个是非聚簇索引的B+树。
如果语句是 select * from T where id=500,即主键查询方式(聚簇索引),则只需要搜索 ID 这棵 B+ 树,查询一表即可。
如果语句是 select id, k from T where k=5,即普通索引查询方式(非聚簇索引),则只要搜索 k 索引树,这样的话查询一表即可。
如果语句是 select id, k , name from T where k=5,第一次通过普通索引查询方式得到 id 的值为 500,再到 id 索引树搜索一次(需要回表才能查到name这个数据)。此时这个过程就成为回表了,回表是基于聚簇索引的缺点之一。
所以为了避免回表,那么可以将k和name建成联合索引(在这个情况下的联合索引,在非主键索引就可以查询到数据,也等同于覆盖索引)。
为什么建成联合索引就可以避免回表?
在4.3中提到,非聚簇索引的叶子结点存储的是指向数据表中相应行的指针,这个指针通常是数据表中主键的值。那么查询到K或者name后,自然的指向了对应的id,那么这个行数据自然也就拿到了。
五、八股:什么时候索引会失效?
1. 不合理的查询条件
- 前模糊查询:当使用LIKE操作符进行模糊匹配,并且匹配模式以通配符
%
开头时(如LIKE '%abc'
),索引会失效。因为索引是基于前缀匹配的,前缀不确定时,数据库无法利用索引快速定位数据。 - OR条件中的非索引列:如果查询条件中包含OR,且OR连接的条件列中有的列不是索引列,那么索引可能会失效。尽管在某些情况下,如果OR连接的每个条件列都单独建立了索引,数据库可能会使用索引合并策略,但这并不总是发生。
2. 对索引列使用函数或表达式
- 函数操作:在查询条件中对索引列使用函数(如
UPPER(column_name)
、LENGTH(column_name)
等)会导致索引失效。因为索引是基于列的原始值建立的,而函数操作改变了列的值,使得数据库无法直接利用索引。 - 表达式计算:在索引列上进行表达式计算(如
column_name + 1 = 2
)同样会导致索引失效。原因与对索引列使用函数类似,索引保存的是原始值,而不是计算后的结果。
3. 数据类型不匹配
- 隐式类型转换:当查询条件中的数据类型与索引列的数据类型不匹配,且数据库进行了隐式类型转换时,索引可能会失效。例如,如果索引列是字符串类型,但在查询条件中使用了整型值,而没有显式地进行类型转换,那么数据库可能会进行隐式类型转换,从而导致索引失效。
4. 索引使用不当
- 联合索引非最左匹配:在使用联合索引时,如果查询条件没有遵循最左前缀原则,即没有从联合索引的最左边列开始匹配,那么索引可能会失效。这是因为联合索引是按照索引列的顺序进行排序的,直接跳过前面的列进行匹配会破坏索引的有序性。
- 范围查询后的列:在联合索引中,如果某个列使用了范围查询(如
>
、<
、BETWEEN
等),那么该列之后的所有列都无法使用索引进行快速定位。
5. 其他情况
- 索引列包含大量重复值:如果索引列的值区分度不高,即包含大量重复值,那么数据库可能会选择不使用索引,而是通过全表扫描来查询数据。因为在这种情况下,使用索引可能并不会带来性能上的提升。
- 索引列被用作条件表达式的一部分:在某些情况下,如果索引列被用作条件表达式的一部分(如
column_name IN (SELECT ...)
中的子查询),且数据库无法有效地将表达式转换为对索引的直接引用,那么索引可能会失效。
六、什么时候不推荐使用索引
- 数据量小的表:如果表中的数据量非常小,比如少于1000条记录,那么索引的提速效果可能并不明显,反而会因为索引的维护成本(如存储空间和更新索引的时间)而降低数据库的整体性能。
- 有大量重复数据的列:在这些列上建立索引,由于索引中的值大量重复,查询时索引并不能有效地减少搜索范围,同时还会增加索引的维护成本,因此在这些列上建立索引是不必要的。
- 经常更新的表:对于经常进行插入、删除和更新操作的表,每次数据变动都需要同时更新索引,这会增加额外的写入负担,降低数据库的写入性能。因此,在这类表上应谨慎考虑索引的创建。
- 在查询中很少使用或参考的列:如果列在查询中很少被使用或作为查询条件,那么建立索引并不能提高查询速度,反而会因为索引的维护成本而降低系统性能。
- 定义为大型数据类型(如TEXT、IMAGE等)的列:这些列的数据量通常很大,建立索引会占用大量的存储空间,并且由于索引结构本身的特点,可能导致查询性能提升不明显。
- 修改性能远远大于检索性能的场景:在某些应用中,数据的修改操作(如插入、更新、删除)可能比检索操作更频繁。在这种情况下,过多的索引会降低修改性能,因为每次数据变动都需要更新索引。因此,当修改性能的重要性高于检索性能时,应减少索引的创建。
- 复杂的查询和联合索引的选择:在存在多个字段需要索引的情况下,如果简单地为每个字段都创建单列索引,可能会导致查询优化器在选择索引时变得复杂,增加查询的编译时间。此时,应考虑使用联合索引来优化查询性能。
可以参考博客:mysql数据库哪些情况不适合使用索引_mysql重复值过多的字段适合做索引吗-CSDN博客