MySQL(二) 索引

1、索引的定义

1.1、概念

数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询,更新数据库表中数据。
在索引中会存储磁盘地址和作为索引的值,这样在查询的时候就无须遍历数据,只要在索引内查到数值,然后根据磁盘地址去取出即可。

1.2、类型

MySQL(二) 索引
第一列是索引名称,第二个是添加索引的字段,第三个是索引类型,
在InnoDB中,索引共有三种,普通索引,唯一索引和全文索引。

  1. 普通索引(normal):也叫非唯一索引,最普通的索引,没有任何限制。
  2. 唯一索引(unique):唯一索引要求键值不可以重复。主键索引是一种特殊的唯一索引,要求键值不能为空,主键索引用primary key创建
  3. 全文索引(fulltext):针对比较大的数据,如果要解决like查询在全文匹配的时候效率低的问题,可以创建全文索引,只有文本类型才能创建全文索引,如char,varchar,text。创建语法关键字为FULLTEXT KEY。它的用法较为特殊:select * from table_name where match(field_name) against('select_key' IN NATURAL LANGUAGE MODE)

1.3、数据结构

为了满足查找方便,同时又要插入速度快,单独使用有序数组或者链表都不足以满足需要,因此选择二叉查找树。

1.3.1、二叉查找树

二叉查找树是一种树形结构,左子树的节点比父节点小,右子树的节点比父节点大,经过这样的排序,树形结构映射到屏幕,连上之后就已经变成有序数组。
MySQL(二) 索引
但是这样的数据结构是有缺陷的,如果二叉树插入的数据恰好是一个有序的数组,那么所有的数据都会集中在这个二叉树的某一侧,这样它就退化为一个链表,无法二分查找,因为二分查找需要的是一个左右平衡的树形结构。

1.3.2、平衡二叉树(AVL Tree)

平衡二叉树的左右子树深度差绝对值不超过1。
MySQL(二) 索引
假如出现了有序数组的插入,出现左-左或者右-右形状,就会使用左旋或右旋改变树的结构以维持平衡。
MySQL(二) 索引
正如前文说所,索引的数据结构至少要存储字段值和磁盘地址,加上树形结构就还需要左右节点,因此一个平衡二叉树的数据节点大致为这样。
MySQL(二) 索引
这样一来,就可以实现当时索引数据结构的全部要求。但是这样就足够了吗?buffer pool一次从磁盘上读取到内存的数据页有16K,一个平衡二叉树的节点能保存的大小肯定远远小于这个数值,这就意味着,有更多的空间被浪费掉,所以想要一次性加载更多的数据到内存,减少IO读取消耗,就要减少树的深度,增加树的路数(即子树的数量)

1.3.3、多路平衡查找树(Balanced Tree B树)

多路平衡查找树一定是平衡的,每一个节点上可以有N个键值和N+1度数,依旧遵循左边比父节点小,右边比父节点大的规律,在缩小整个树的深度之后,所需要查找的次数也就大大缩短。
MySQL(二) 索引
为了保持平衡,在有序数组插入时,会进行合并与分裂,定义最大度数max degree=3,当有三个子节点时会发生一次分裂,反之,删除一个子节点时会发生合并,因此不建议作为索引的值发生频繁的修改,因为会不断发生分裂与合并
MySQL(二) 索引
B树的分裂与合并,其实就可以看作是页的分裂与合并,当作为索引的数据是有序的时候,数据页可以依次将数据顺序写入,不会浪费空间。如果索引的数据是无序的话,就会造成数据页的不连续,导致磁盘存储碎片化,经常性的发生分裂与合并,因此不建议作为索引的值是无序数据
MySQL(二) 索引

1.3.4、加强版多路平衡查找树(B+树)

实际上,MySQL使用的是B+树。
B+树是B树的增强版本,有以下不同之处

  • 字的数量和度数是相等的。
  • 叶子结点才存储数据,每一个内节点存储的不再是数据,而是指向下一个节点的地址,查找任何一个数据都要查询到叶子节点。
  • 叶子结点组成一个有序链表。

MySQL(二) 索引
B+树的优势

  1. 扫库扫表的能力更强:全表扫描只需要扫描叶子结点,无需从树开始扫描。
  2. 磁盘读写能力更强:树的深度更小,IO次数更少
  3. 排序能力更强:叶子结点的双向指针可以加快排序
  4. 效率更加稳定

1.3.5、红黑树

那么为什么不用红黑树?
红黑树的约束条件:

  • 节点分为红色或黑色
  • 根节点必须因为黑色
  • 叶子结点都是黑色的null节点
  • 红色节点的两个子节点都是黑色(不允许两个相邻的红色节点)
  • 从任意节点出发,到达其每个叶子节点的路径中包含相同数量的黑色节点。

也就是说,红黑树的目的是为了让最长查找路径不超过最短查找路径的两倍,但AVL Tree就可以保证平衡,降低查找次数,所以红黑树实际上更加适合在内存中使用,如redis分片中的客户端jedis就运用了红黑树分片。

1.4、索引方式

在Navicat工具中,创建索引的方式有两种

1.4.1、HASH

以KV的形式检索数据,也就是说,它会根据索引字段生成哈希码和指针,指针指向数据,特点如下。

  1. 它的时间复杂度是O(1),查询速度比较快,因为哈希索引里面的数据不是按照顺序排列的,所以不能用于排序。
  2. 查询时要根据键值计算哈希码,所以只支持等值查询(=,in),不支持范围查询(<,>,>=,<=,between,and)
  3. 如果字段重复值较多,会造成大量的哈希冲突,降低效率。
  4. InnoDB无法显式地创造一个hash索引,它支持的hash索引是指AHI,自适应哈希,是为buffer pool中热点页创建的索引。
  5. memory可以使用hash索引。

1.4.2、B+ Tree

与上文描述方式相同,不再赘述。

2、具体实现

在MySQL中对不同的存储引擎,具有不同的索引实现。在最常用的两种存储引擎中,InnoDB和MyISAM有各自的实现方式。
InnoDB表有两个文件,.FIR、.IDB,MyISAM表有三个文件,.FIR、.MYD、.MYI,其中.FRM是MySQL里面表结构定义的文件,不管建表的时候选用哪一个存储引擎都会生成,所以主要看其他文件。

2.1、MyISAM

MyISAM有两个不同的文件,其中.MYD文件代表Data,是MyISAM的数据文件,存放数据记录,.MYI文件代表Index,是MyISAM的索引文件,存放索引,比如在ID字段上创建一个主键索引,那么这个主键索引就在这个文件里,一个索引就有一颗B+Tree,所有的B+Tree都在这个MYI文件里面。
也就是说,在MyISAM中,索引和数据是两个独立的文件。
MyISAM的B+Tree中,叶子结点存储的是数据文件对应的磁盘地址,从索引文件.MYI中找到键值后,回到数据文件.MYD中获取相应的数据记录。
MySQL(二) 索引
在MyISAM里面,其他的索引也在这个.MYI文件里面。
非主键索引和主键索引存储和检索数据的方式是没有任何区别的,一样是在索引文件里面找到磁盘地址,然后到数据文件里面获取数据。

2.2、InnoDB(聚集索引)

在InnoDB的某个索引的叶子节点上,它直接存储了表中数据。
所以在InnoDB中,数据即索引,索引即数据。
但是这样就会产生一个问题,一张InnoDB的表可能会有很多个索引,数据肯定只有一份,那么这个数据在哪个索引的叶子节点上?
MySQL(二) 索引
在这里,它用到的是聚集索引。
聚集索引,即索引键值的逻辑顺序和表数据行的物理存储顺序是一致的。
InnoDB组织数据的方式就是聚集索引组织表(clustered index organize table)。如果说一张表创建了主键索引,那么这个主键索引就是聚集索引,决定数据行的物理存储顺序。
主键之外的索引,不会把完整记录存放在叶子节点上。
InnoDB中,主键索引和辅助索引是有一个主次之分,如果有主键索引,那么主键索引就是聚集索引,其他的索引统一叫做二级索引。
二级索引存储的是二级索引的键值,例如在某一字段上建立索引,节点上存的是该字段的值和对应的主键值,所以说二级索引检索数据的流程是这样的:
用某一字段索引查询一条记录,它会在二级索引的叶子节点找到该字段的值,然后拿到对应数据行的主键值,再去主键索引的叶子节点拿到数据,之所以不存储地址而是键值,是因为地址会产生变化。
主键索引的查询速度会比二级索引更快,因为少查询了一个B+Tree。
如果一张表没有主键,InnoDB会选择第一个不包含NULL值的唯一索引作为主键索引。
如果也没有这样的唯一索引,InnoDB会选择内置6字节长的rowid作为隐藏的聚集索引,它会随着行记录的写入逐渐递增。

3、索引使用原则

3.1、列的离散度

列的离散度计算公式:count(distinct(column_name)):count(*),列的全部不同值和所有数据行的比例,数据行数相同的情况下,分子越大,列的离散度越高。也就是说,列的重复值越多,离散度就越低,重复值越少,离散度就越高。
因此不建议离散度低的字段上建立索引。

3.2、联合索引最左匹配

在需要多条件查询的时候,就建立联合索引,单列索引可以看成是特殊的联合索引。
联合索引在B+Tree中是符合的数据结构,它是按照从左到右的顺序来建立搜索树的,左边的字段有序,右边的字段在左边字段相同时才有序,否则无序。举一个例子,user表包含name和phone两个字段,若是创建联合索引,则name是有序的,phone是无序的。当name相等,phone才有序。也就是说,当查询name和phone时,会先查询name,然后查询phone,如果没有name,就无法查询索引。
下面再举几个例子:

  1. select * from user where name = 'miaomiao' and phone = '18955555':可以用到索引
  2. select * from user where phone = '18955555' and name = 'miaomiao':优化器可以优化SQL,所以次序对联合索引没有影响
  3. select * from user where name = 'miaomiao' ':可以用到索引
  4. select * from user where phone = '18955555':无法用到索引

由此可以看出,假如对a,b,c,三个字段创建创建索引,实际上生成的索引是a,ab,abc,这三个索引,因此想要联合索引生效,就一定要连续的查询,即从a开始,不能从b或c开始,中间不能跳过,即ac,不然都无法让联合索引生效。

3.3、覆盖索引

非主键索引,需要先通过索引找到主键,然后根据主键索引找到数据,比直接查询主键索引要多扫描一个B+Tree,整个过程被称为回表。
在二级索引中,无论是单列索引还是联合索引,如果查询的数据列只用从索引中就能够取得,不必从数据区取,这个时候使用的索引就叫做覆盖索引,能有效避免回表。
下面再举几个例子,user表包含name和phone两个字段,这两个字段为联合索引,name在左,phone在右:

  1. select name,phone from user where name = 'miaomiao':可以用到覆盖索引,因为这两个字段都在联合索引中
  2. select name from user where phone = '18955555' and name = 'miaomiao':可以用覆盖索引
  3. select name from user where phone = '18955555':可以用覆盖索引,就算phone没有让联合索引生效,但是name是联合索引之一,所以可以先查询到name再用phone的条件进行过滤,无序回表,这种情况是条件与显示列都为联合索引时出现。
  4. select * from user where name = 'miaomiao' ':无法用到覆盖索引,因为查询字段显然有不在联合索引中的。

3.4、索引条件下推(ICP)

索引条件下推(Index Condition Pushdown)是5.6推出的新功能,只适用于二级索引,平时默认开启。
ICP的目的是减少访问表的完整好的读数量而减少IO操作。
如上一章所言,数据从存储引擎中取出,然后进入服务层,索引就在服务层,会先根据索引来过滤数据,然后将过滤后的数据传入服务层根据条件进一步过滤,例如:select name,phone from user where name = 'miaomiao' and phone like '%99'
在这里,name在索引中,可以直接在存储引擎中完成初次过滤,但是phone的模糊查询百分号在左边,也就意味着索引无法生效,这样的话,数据必须到服务层在进行一次条件过滤,ICP就是专门为了解决这种情况的新功能。
为了加快速度,在主键索引中获取到全部数据后,会根据phone的查询条件直接进行过滤,送到服务层的数据已经经过筛选,这样就减少了I/O次数,大大提升效率。
MySQL只要能将索引查询条件下推就会下推,无需其他干涉。

4、索引的创建与使用

4.1、索引的创建

  1. 用于在where判断,order排序,join连接,group by分组等字段上创建索引。
  2. 索引的个数不宜过多
  3. 过长的字段,可以建立前缀索引(前缀索引,即规定字段的前几位作为索引值而不是整个字段作为索引值)
  4. 不选取区分度低的字段,因为离散度太低,不适合
  5. 不选取频繁更新的字段:会导致数据页频繁地合并与分裂。
  6. 不选取随机无序的值:不适合索引排序,查找不易
  7. 联合索引把离散度高的值放在左边
  8. 创建联合索引,无需经常创建单列索引

4.2、索引的失效

4.2.1、常见的索引失效

  1. 索引列上使用函数,如replace,sub,str,count,avg,sum,concat,表达式计算+,-,*,/
  2. like条件前面带有%
  3. 负向查询,not like一定不能,!=(<>)和not in有时可以

4.2.2、隐式转换失效

在MySQL官方的规定中,有七种类型转换的规则

  1. 两个参数至少有一个为null时,比较的结果也为null,特殊的情况是使用<=>对两个null做比较时会返回1,这两种情况都不需要做类型转换
  2. 两个参数都是字符串,会按照字符串来比较,不做类型转换。
  3. 两个参数都是整数,会按照整数来比较,不做类型转换
  4. 十六进制的值和非数字作比较时,会被当做二进制串
  5. 一个参数是TIMESTAMP或DATETIME,并且另外一个数值是常量,常量会被转化成TIMSTAMP
  6. 一个参数是decimal类型,如果另外一个参数是decimal或者整数,会将整数转化为decimal后进行比较
  7. 所有其他情况下,两个参数都会被转换为浮点数进行比较

把数字和字符进行比较时,MySQL无法很快地用索引找到对应值,也就是说,当查询一个建立索引的字符型字段时,不输入单引号,该输入数据会被当成数字而非字符,这会导致隐形转换的发生,让索引失效。
按照第7条转换原则:

  1. 不以数字开头的字符串都将转换为0,如‘qwert’,‘qasd111’,都会被转化为0.
  2. 以数字开头的字符串转换石会进行截取,从第一个字符截取至第一个非数字内容为止,比如’0123a’会转化为0123,也就是123,'123ader’会被转化为123,'9.9a2sd34’会被转化为9.9.
上一篇:您的手机变成计算机的麦克风


下一篇:python学习之创建和使用类