深入理解Mysql索引底层数据结构与算法

前言

索引(index)是帮助MySQL高效获取数据的一种有序数据结构。在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法,这种数据结构就是索引。

优势:

  • 提高数据检索的效率,降低数据库的成本,减少io交互
    通过索引列对数据进行排序,降低数据排序的成本,降低CPU的消耗。

劣势:

  • 索引列也是要占用空间的。
    索引大大提高了查询效率,同时却也降低更新表的速度,如对表进行INSERT、UPDATE、DELETE时,效率降低。

一、索引数据结构

数据结构学习网址

MSQL的索引是在存储引擎层实现的,不同的存储引擎有不同的结构,主要包含以下几种:

索引结构描述
B+Tree索最常见的索引类型,大部分引擎都支持B+树索引
Hash索引底层数据结构是用哈希表实现的,只有精确匹配索引列的查询才有效不支持范围查询,只支持in和=
R-tree(空间索引 )空间索引是MyISAM引擎的一个特殊索引类型,主要用于地理空间数据类型,通常使用较少
Full-text(全文索引)是一种通过建立倒排索引,快速匹配文档的方式。类似于Lucene,Solr,ES
索引InnoDBMyISAMMemory
B+Tree索引支持支持支持
Hash索引不支持不支持支持
R-tree(空间索引 )不支持支持不支持
Full-text(全文索引)5.6版本之后支持支持不支持
索引为什么不使用二叉树作为索引结构?

二叉树缺点:顺序插入时,会形成一个链表,查询性能大大降低。大数据量情况下,层级较深,检索速度慢。如下图
在这里插入图片描述
我们如果查询5这个值时,其查询了4次,这个还是数据比较少,如果数据比较多,那么就会形成很深的层级,查询性能大大降低。

那红黑树呢?

在这里插入图片描述
看起来,层级变少了,查询5这个值只用了2步,但是红黑树也是一种二叉树,在数据比较多,也会形成很深的层级,查询性能也会较低,只是比二叉树好点

看来层级越少,查询性能越好,那有没有什么数据结构,在大数据情况下,层次也很少呢。有,下面开始介绍B-Tree


BTree又称多路平衡查找树,叶节点具有相同的深度,叶节点的指针为空所有索引元素不重复,节点中的数据索引从左到右递增排列

以一颗最大度数为5的b-tree为例(每个节点最多存储4个key,5个指针),树的度数指的是一个节点的子节点个数。
在这里插入图片描述

B+Tree,非叶子节点不存储data,只存储索引(冗余),可以放更多的索引叶子节点包含所有索引字段,叶子节点用指针连接,提高区间访问的性能

以一颗最大度数(max-degree)为4(4阶)的b+tree为例:
在这里插入图片描述

为什么 MySQL 的索引要使用 B+ 树而不是其他树形结构?比如 B 树?

因为 B 树不管叶子节点还是非叶子节点,都会保存数据,这样导致在非叶子节点中能保存的指针数量变少(有些资料也称为扇出)。
指针少的情况下要保存大量数据,只能增加树的高度,导致 IO 操作变多,查询性能变低

为什么推荐使用整型的自增主键?

聚簇索引的数据的物理存放顺序与索引顺序是一致的,即:只要索引是相邻的,那么对应的数据一定也是相邻地存放在磁盘上的。
聚簇索引的顺序和磁盘中数据的存储顺序是一致的,如果主键不是自增id,那么可以想 象,它会干些什么,不断地调整数据的物理地址、分页,当然也有其他一些措施来减少这些操作,但却无法彻底避免。但,如果是自增的,那就简单了,它只需要一 页一页地写,索引结构相对紧凑,磁盘碎片少,效率也高。

Hash
哈希索引就是采用一定的hash算法,将键值换算成新的hash值,映射到对应的槽位上,然后存储在hash表中。
如果两个(或多个)键值,映射到一个相同的槽位上,他们就产生了hash冲突(也称为hash碰撞),可以通过链表来解决。

Hash索引特点
1.Hash索引只能用于对等比较(=,in),不支持范围查询(between,>,<,…)
2.无法利用索引完成排序操作
3.查询效率高,通常只需要一次检索就可以了,效率通常要高于B+tree索引

存储引擎支持
在MySQL中,支持hash索引的是Memoryi引擎,而InnoDB中具有自适应hash内能,hash索引是存储引擎根据B+Tree索引在指定条件下自动构建的。

为什么InnoDB存储引擎选择使用B+tree索引结构?

相对于二叉树,层级更少,搜索效率高;
对于B-tree,无论是叶子节点还是非叶子节点,都会保存数据,这样导致一页中存储的键值减少,指针跟着减少,要同样保存大量数据,只能增加树的高度,导致性能降低;
相对Hash索引,B+tree支持范围匹配及排序操作;

二、索引分类

分类含义特点关键字
主键索引针对于表中主键创建的索引默认自动创建,只能有一个Primary
唯一索引避免同一个表中某数据列中的值重复可以有多个unique
常规索引快速定位特定数据可以有多个
全文索引全文索引查找的是文本中的关键词,而不是比较索引中的值可以有多个fulltext

在InnoDB存储引擎中,根据索引的存储形式,又可以分为以下两种:

分类含义特点
聚集索引将数据存储与索引放到了一块,索引结构的叶子节点保存了行数据必须有,而且只有一个
非聚集索引将数据与索引分开存储,索引结构的叶子节点关联的是对应的主键可以存在多个

聚集索引选取规则:

  • 如果存在主键,主键索引就是聚集索引。
    如果不存在主键,将使用第一个唯一(unique)索引作为聚集索引。
    如果表没有主键,或没有合适的唯一索引,则nnoDB会自动生成一个rowid作为隐藏的聚集索引。

聚集索引结构图如下
在这里插入图片描述
非聚集索引结构图如下
在这里插入图片描述

思考:以下SQL语句,那个执行效率高?为什么?备注:id为主键,name字段创建的有索引,age普通字段
select *  from user where id =10;
select * from user where name ='Arm';
select id,name from user where name ='Arm';
select id,name,age from user where name ='Arm';

第一个SQL:id是聚集索引,他查到10这个节点时,就可以直接获取他的row
第二个SQL:name是非聚集索引,他查到Arm这个节点时,他不会直接获取他的row,而是获取他的聚集索引,如10,然后通过其聚集索引值获取他的row

那他们呢?

select id,name from user where name ='Arm';
select id,name,age from user where name ='Arm';

第一个SQL:因为name是非聚集索引,他查到Arm这个叶子节点时,可以直接获取id,不会去继续回表查询
第二个SQL:当查到Arm这个叶子节点时,可以直接获取id,但是获取不到age的值,所以他需要通过id,继续回表查询

一张表,有四个字段(id,username,password,status)由于数据量大,需要对以下SQL语句进行优化,该如何进行才是最优方案:
select id,username,password from tb user where username ='itcast';

对username和password创建联合索引,如果只对username创建索引,那么会产生回表查询
在业务场景中,如果存在多个查询条件,考虑针对于查询字段建立索引时,建议建立联合索引,而非单列索引。

思考:InnoDB主键索引的B+tree高度为多高呢?

在这里插入图片描述
在计算机中磁盘存储数据最小单元是扇区,一个扇区的大小是512字节,而文件系统(例如XFS/EXT4)他的最小单元是块,一个块的大小是4k,而对于我们的InnoDB存储引擎也有自己的最小储存单元——页(Page),一个页的大小是16K

假设:一行数据大小为1k,一页中可以存储16行这样的数据。InnoDB的指针占用6个字节的空间,主键即使为oigint,占用字节数为8。

高度为2:

  • n*8+(n+1)6=161024,算出n约为1170
  • 1171*16=18736

高度为3:

  • 1171117116=21939856 (约 2 千万)

三、索引语法

3.1 创建索引

如果只关联一个字段,那么就是单列索引,如果关联多个字段,那么就是组合索引

create unique index 索引名 on 表名(字段名,字段名,字段名)//创建唯一索引  

create fulltext index 索引名 on 表名(字段名,字段名,字段名)//创建全文索引 

create  index 索引名 on 表名(字段名,字段名,字段名)//创建普通索引 

当字段类型为字符串(varchar,text等)时,有时候需要索引很长的字符串,这会让索引变得很大,查询时,浪费大量的磁盘io,影响查
询效率。此时可以只将字符串的一部分前缀,建立索引,这样可以大大节约索引空间,从而提高索引效率。


create index 索引名 on 表名(字段名(n); //创建前缀索引

前缀长度n,可以根据索引的选择性来决定,而选择性是指杯重复的索引值(基数)和数据表的记录总数的比值,索引选择性越高则查询效率越高,最高为1,这是最好的索引选择性,性能也是最好的。下面以字段email为例

select count(distinct substring(email,1,5))/count(*)from tb_user
3.2 查看和删除索引
show index from 表名 #查看索引

drop index  索引名 on 表名 #删除索引
3.3 索引提示

索引提示,是优化数据库的一个重要手段,简单来说,就是在SQL语句中加入一些人为的提示来达到优化操作的目的。

在Mysql如果一个字段上存在1个以上的索引,那么Mysql会自己选一个索引生效

create index school_home_index on person(school,home)

create index school_index on person(school)

explain select * from person where  school = '海'

在这里插入图片描述
如果我们自己想指定索引生效,那么可以使用下面的语法

#建议使用索引school_index,所以有可能不用
select  *from person use index(school_index)where school = '海'

#忽略索引school_index
select * from person user ignore index(school_index)where  school = '海'

#强制使用索引school_index
select * from person user force index(school_index)where  school = '海'

版权声明:本文为qq_41071876原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。