MySQL（二） 索引

2022-10-08 23:07:51

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学习之创建和使用类