MySql教程

第3节 MySQL 索引数据结构及使用 2021-12-28

本文主要是介绍第3节 MySQL 索引数据结构及使用 2021-12-28,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Java组件总目录

MySQL 索引数据结构及使用

  • Java组件总目录
  • 一、索引介绍
  • 二、索引的优缺点
    • 1.优势
    • 2.劣势
  • 三、索引的数据结构
    • 1.索引的要求
    • 2.数据结构的选用
      • 1 Hash表
      • 2 二叉排序树(二叉查找树)
      • 3 平衡二叉查找树
      • 4 B树:改造二叉树
          • 主要特点:
          • B树的缺点:
        • 5 B+树:改造B树
          • 等值查询过程
          • 范围查询过程
  • 四、MySQL索引实现
    • 主键索引
    • 辅助索引
    • 组合索引
      • 1 组合索引的查找方式
      • 2 最左前缀匹配原则
      • 3 覆盖索引
      • 4 组合索引创建原则
      • 5 索引条件下推ICP
        • 使用ICP 具体步骤
        • 不使用ICP情况
        • ICP 的优点
  • 五、 索引创建原则
    • 1、哪些情况需要创建索引
    • 2、索引优化建议
  • 六、索引使用注意内容


一、索引介绍

  • 官方介绍索引是帮助MySQL 高效获取数据的数据结构 。更通俗的说,数据库索引好比是一本书前面的目录,能加快数据库的查询速度 。
  • 一般来说索引本身也很大,不可能全部存储在内存中,因此 索引往往是存储在磁盘上的文件中的 (可能存储在单独的索引文件中,也可能和数据一起存储在数据文件中)。
  • 我们通常所说的索引,包括聚集索引、覆盖索引、组合索引、前缀索引、唯一索引等,没有特别说明,默认都是使 用B+树结构组织(多路搜索树,并不一定是二叉的)的索引。

二、索引的优缺点

1.优势

  • 可以提高数据检索的效率,降低数据库的IO成本 ,类似于书的目录。
  • 通过 索引列对数据进行排序 ,降低数据排序的成本,降低了CPU的消耗。
    • 被索引的列会自动进行排序,包括【单列索引】和【组合索引】,只是组-合索引的排序要复杂一些。
    • 如果按照索引列的顺序进行排序,对应order by语句来说,效率就会提高很多。

2.劣势

  • 索引会占据磁盘空间
  • 索引虽然会提高查询效率,但是会降低更新表的效率 。比如每次对表进行增删改操作,MySQL不仅要保存数据,还有保存或者更新对应的索引文件。

三、索引的数据结构

1.索引的要求

索引的数据结构,至少需要支持两种最常用的查询需求:

  • 等值查询:根据某个值查找数据
  • 范围查询:根据某个范围区间查找数据,
    同时需要考虑时间和空间因素。在执行时间方面,我们希望通过索引,查询数据的时间尽可能小;在存储空间方面,我们希望索引不要消耗太多的内存空间和磁盘空间。

2.数据结构的选用

常用的数据结构:Hash表,二叉树,平衡二叉查找树(红黑树是一个近似平衡二叉树),B树,B+树。数据结构示例网站:可以通过动画看到操作过程,非常好的一个网站。
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

1 Hash表

等值查询效率很高。范围查询效率低。并非一个通用的数据结构。

2 二叉排序树(二叉查找树)

  • 特点:
    所有左子树的数据都小于根节点,所有右子树的数据都大于根节点。
  • 构建方式:
    选择第一个元素作为根节点,以后添加数据时,数据小于根节点向左排,大于等于根节点向右排。
  • 问题:
    当构建一颗排序二叉树时,如果节点选取的不合理二叉树会退化成链表。

3 平衡二叉查找树

  • 特点:
    在二叉排序树基础上,每次添加数据时判断树是否平衡。每个节点的左子树和右子树的高度差不能超过1。
    如果超过1,采用左旋或者右旋的方式达到一个平衡的状态。
    查找数据时可以保证时间复杂度O(log2n)
  • 问题:
    每个节点只有两个子树。在mysql中每次磁盘的读取是以页(16k)为单位。每个数据页中只保存一个节点的数据。
    当数据量大的时候平衡二叉查找树的高度会非常高,查询时产生的磁盘的io会很多。

4 B树:改造二叉树

MySQL的数据是存储在磁盘文件中的,查询处理数据时,需要先把磁盘中的数据加载到内存中,磁盘 IO 操作非常耗时,所以我们优化的重点就是尽量减少磁盘 IO 操作。访问二叉树的每个节点就会发生一次IO,如果想要减少磁盘IO操作,就需要尽量降低树的高度。那如何降低树的高度呢?

MySQL的InnoDB存储引擎一次IO会读取的一页16K的数据量, 在每个节点尽可能多的存储数据。每个节点可以存储1000个索引(16k/16=1000),这样就将二叉树改造成了多叉树。这种数据结构我们称为B树,B树是一种多叉平衡查找树。

主要特点:
  1. B树的节点中存储着多个元素,每个内节点有多个分叉。
  2. 节点中的元素包含键值和数据,节点中的键值从大到小排列。也就是说,在所有的节点都储存数据。
  3. 父节点当中的元素不会出现在子节点中。
  4. 所有的叶子结点都位于同一层,叶节点具有相同的深度,叶节点之间没有指针连接。

在这里插入图片描述

B树的缺点:
  1. B树不支持范围查询的快速查找,如果我们想要查找15和26之间的数据,查找到15之后,需要回到根节点
    重新遍历查找,需要从根节点进行多次遍历,查询效率有待提高。
  2. 如果data存储的是行记录,行的大小随着列数的增多,所占空间会变大。这时,一个页中可存储的数据量
    就会变少,树相应就会变高,磁盘IO次数就会变大。

5 B+树:改造B树

在B树基础上,MySQL在B树的基础上继续改造,使用B+树构建索引。B+树和B树最主要的区别在于非叶子节点是否存储数据的问题。

  • B树:非叶子节点和叶子节点都会存储数据。
  • B+树:只有叶子节点才会存储数据,非叶子节点至存储键值。叶子节点之间使用双向指针连接,最底层的叶子节点形成了一个双向有序链表。
    在这里插入图片描述
等值查询过程

假如我们查询值等于15的数据。查询路径磁盘块1 p磁盘块2 p磁盘块5。

  • 第一次磁盘IO:将磁盘块1加载到内存中,在内存中从头遍历比较15<28,走左路,到磁盘寻址磁盘块2。
  • 第二次磁盘IO:将磁盘块2加载到内存中,在内存中从头遍历比较,10<15<17,到磁盘中寻址定位到磁盘块5。
  • 第三次磁盘IO:将磁盘块5加载到内存中,在内存中从头遍历比较,15=15,找到15,取出data,如果data存储的行记录,取出data,查询结束。如果存储的是磁盘地址,还需要根据磁盘地址到磁盘中取出数据,查询终止。
范围查询过程

假如我们想要查找15和26之间的数据。查找路径是磁盘块1 p磁盘块2 p磁盘块5。

  1. 首先查找值等于15的数据,将值等于15的数据缓存到结果集。这一步和前面等值查询流程一样,发生了三次磁盘IO。
  2. 查找到15之后,底层的叶子节点是一个有序列表,我们从磁盘块5,键值15开始向后遍历筛选所有符合筛选条件的数据。
  3. 第四次磁盘IO:根据磁盘5后继指针到磁盘中寻址定位到磁盘块6,将磁盘6加载到内存中,在内存中从头遍历比较,15<17<26,15<26 u26,将data缓存到结果集。
  4. 主键具备唯一性(后面不会有 u26的数据),不需再向后查找,查询终止。将结果集返回给用户。

可以看到B+树可以保证等值和范围查询的快速查找,MySQL的索引就采用了B+树的数据结构。下面我们一起来看看InnoDB和MyISAM中是如何使用B+树构建索引的。

四、MySQL索引实现

InnoDB的数据和索引存储在一个文件table_name.ibd中。

  • 主键索引是聚簇索引,主键和数据行是混合保存在一起的。
  • 辅助索引非聚簇索引,索引和数据没有存储在一起。叶子节点中保存的是对应记录的主键信息。查询时,需要根据辅助索引查询到对应记录的id,然后再走主索引根据id查询对应的记录信息。这个过程叫做“回表”.

主键索引

每个InnoDB表都有一个聚簇索引 ,聚簇索引使用B+树构建,叶子节点存储的数据是整行记录。一般情况下,聚簇索引等同于主键索引,当一个表没有创建主键索引时,InnoDB会自动创建一个ROWID字段来构建聚簇索引。InnoDB创建索引的具体规则如下

  1. 在表上定义主键PRIMARY KEY,InnoDB将主键索引用作聚簇索引。
  2. 如果表没有定义主键,InnoDB会选择第一个不为NULL的唯一索引列用作聚簇索引。
  3. 如果以上两个都没有,InnoDB 会使用一个6 字节长整型的隐式字段 ROWID字段构建聚簇索引。该ROWID字段会在插入新行时自动递增。
    在这里插入图片描述

辅助索引

除聚簇索引之外的所有索引都称为辅助索引。在中InnoDB,辅助索引中的叶子节点存储的数据是该行的主键值。在检索时,InnoDB使用此主键值在聚簇索引中搜索行记录。
在这里插入图片描述

组合索引

1 组合索引的查找方式

组合索引是我们常用的索引类型。那组合索引是如何构建的,查找的时候又是如何进行查找的呢。

select * from t_multiple_index where a=13 and b=16 and c=4;
  1. 先在索引树中从根节点开始检索,将根节点加载到内存,先比较a列,a=14,14>13,走左路。(1次磁盘IO)
  2. 将左子树节点加载到内存中,先比较a列,a=13,比较b列b=14,14<16,走右路,向下检索。(1次磁盘IO) 3. 达到叶节点,将节点加载到内存中从前往后遍历比较。(1次磁盘IO)
    • 第一项(13,14,3,id=4):先比较a列,a=13,比较b列b=14,b t16不符合要求,丢弃。
    • 第二项(13,14,4,id=1):一样的比较方式,a=13,b=16,c=4 满足筛选条件。取出索引data值即主键id=1,再去主键索引树中检索id=1的数据放入结果集中。(回表:3次磁盘IO)
    • 第三项(13,14,5,id=3):a=13,b=16,c t4 不符合要求,丢弃。查询结束。
  3. 最后得到1条符合筛选条件,将查询结果集返给客户端。
    在这里插入图片描述

2 最左前缀匹配原则

原则和联合索引的 索引存储结构和检索方式是有关系的。

  • 最底层的叶子节点按照第一列a列从左到右递增排列,但是b列和c列是无序的。
  • b列只有在a列值相等的情况下小范围内递增有序
  • c列只能在a,b两列相等的情况下小范围内递增有序。

提示:这里对文章进行总结:
例如:以上就是今天要讲的内容,本文仅仅简单介绍了pandas的使用,而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。

3 覆盖索引

前面我们提到,根据在辅助索引树查询数据时,首先通过辅助索引找到主键值,然后需要再根据主键值到主键索引中找到主键对应的数据。这个过程称为回表。

使用辅助索引查询比基于主键索引的查询多检索了一棵索引树,那是不是所有使用辅助索引的查询都需要回表查询呢?

表t_multiple_index,组合索引idx_abc(a,b,c)的叶子节点中包含(a,b,c,id)四列的值,对于以下查询语句, 可以直接在辅助索引树上全部获取。使用explain工具查看执行计划,可以看到extra中“Using index”,代表使用了覆盖索引。

select a from t_multiple_index where a=13 and b=16; 
select a,b from t_multiple_index where a=13 and b=16; 
select a,b,c from t_multiple_index where a=13 and b=16; 
select a,b,c,id from t_multiple_index where a=13 and b=16;

4 组合索引创建原则

  1. 频繁出现在where条件中的列,建议创建组合索引。
  2. 频繁出现在order by和group by语句中的列,建议按照顺序去创建组合索引。order by a,b 需要组合索引列顺序(a,b)。如果索引的顺序是(b,a),是用不到索引的。
  3. 常出现在select语句中的列,也建议创建组合索引。(覆盖索引不用回表)

5 索引条件下推ICP

索引条件下推: Index Condition Pushdown,简称ICP。是MySQL5.6对使用索引从表中检索行的一种优化。可以通过参数optimizer_switch控制ICP的开始和关闭。默认开启。

组合索引idx_abc(a,b,c)。用explain工具,查看执行计划,extra列中的“Using index condition”执行器表示使用了索引条件下推ICP。

select * from t_multiple_index where a=13 and b>15 and c='5' and d='pdf';

使用ICP 具体步骤

在这里插入图片描述
使用ICP时,具体步骤如下:

  1. 执行器使用索引(a,b,c),筛选条件a=13 and b >15 and c=5,调用存储引擎"下一行"接口。根据最左前缀原则联合索引检索定位到索引项(13,16,4,id=1),然后使用ICP下推条件c=5判断,不满足条件,直接丢弃。

    向后遍历判断索引项(13,16,5,id=3),满足筛选条件a=13 and b v15 and c=5,使用id=3回表。 获得id=3的行记录。返回给MySQL服务层,MySQL服务层使用剩余条件d='pdf’过滤,符合要求,缓存到 结果集。

  2. 执行器调用"下一行"接口,存储引擎遍历向后找到索引项(13,16,5,id=6),满足筛选条件a=13 and b >15 and c=5,使用id=6回表获得id=6的行记录。返回给MySQL服务层,MySQL服务层使用剩余条件d='pdf’过滤,不符合要求,直接丢弃。

  3. 执行器调用"下一行"接口,存储引擎遍历向后找到索引项( 14,14,14,id=8)不满足筛选条件,执行器终止查询。

  4. 最终获取一条记录,返回给客户端。
    可以看到,在使用ICP时,回表查询了2次,然后在服务层筛选后(筛选2次),最后返回客户端。

不使用ICP情况

ICP 的优点

  • 不使用ICP,不满足最左前缀的索引条件的比较是在Server层进行的,非索引条件的比较是在Server层进行的。
  • 使用ICP,所有的索引条件的比较是在存储引擎层进行的,非索引条件的比较是在Server层进行的。

对比使用ICP和不使用ICP,可以看到使用ICP可以有效减少回表查询次数和返回给服务层的记录数,从而减少了磁盘IO次数和服务层与存储引擎的交互次数。

五、 索引创建原则

1、哪些情况需要创建索引

  1. 频繁出现在where 条件字段,order排序,group by分组字段
  2. select 频繁查询的列,考虑是否需要创建联合索引(覆盖索引,不回表)
  3. 多表join关联查询,on字段两边的字段都要创建索引

2、索引优化建议

  1. 一个表的索引个数不能过多。
    实际查询时,Mysql一般只用一个索引,多个索引效率低。

    • (1)空间:浪费空间。每个索引都是一个索引树,占据大量的磁盘空间。
    • (2)时间:
      更新(插入/Delete/Update)变慢。需要更新所有的索引树。
      太多的索引也会增加优化器的选择时间。
  2. 频繁更新的字段不建议作为索引。
    频繁更新的字段引发频繁的页分裂和页合并,性能消耗比较高。

  3. 区分度低的字段,不建议建索引。(仅供参考)
    比如性别,男,女;比如状态。区分度太低时,会导致扫描行数过多,再加上回表查询的消耗。如果使用索引,比全表扫描的性能还要差。这些字段一般会用在组合索引中。
    姓名,手机号就非常适合建索引。

  4. 在InnoDB存储引擎中,主键索引建议使用自增的长整型,避免使用很长的字段。
    主键索引树一个页节点是16K,主键字段越长,一个页可存储的数据量就会越少,比较臃肿,查询时尤其是区间查询时磁盘IO次数会增多。辅助索引树上叶子节点存储的数据是主键值,主键值越长,一个页可存储的数据量就会越少,查询时磁盘IO次数会增多,查询效率会降低。

  5. 不建议用无序的值作为索引。例如身份证、UUID
    更新数据时会发生频繁的页分裂,页内数据不紧凑,浪费磁盘空间。

  6. 尽量创建组合索引,而不是单列索引。
    优点:
    (1)1个组合索引等同于多个索引效果,节省空间。
    (2)可以使用覆盖索引
    创建原则:组合索引应该把把频繁的列,区分度高的值放在前面。频繁使用代表索引的利用率高,区分度高代表筛选粒度大,可以尽量缩小筛选范围。

六、索引使用注意内容

  • 全值匹配我最爱
  • 最佳左前缀法则 (带头索引不能死,中间索引不能断)
  • 在索引上做计算失效: 计算、函数、自动/手动类型转换,不然会导致索引失效而转向全表扫描。(字符串数字条件是字符串,数字会导致索引失效)
  • 范围条件右边的列失效:不能继续使用索引中范围条件(bettween、<、>、in等)右边的列。
  • 索引字段上使用不等, 会导致索引失效而转向全表扫描。(索引字段上不要判断null)
  • 索引字段使用like以通配符开头。 (‘%字符串’)时,会导致索引失效而转向全表扫描, (“字符串%”)使用索引
  • or使用 ,注意:要想使用or,又想让索引生效,只能将or条件中的每个列都加上索引。
select * from table where id = 1 
# name 无索引,使id 的索引失效,查询不走索引
# name 字段有索引 则会走索引
select * from table where id = 1 or name = "张三"

这篇关于第3节 MySQL 索引数据结构及使用 2021-12-28的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!