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

2021-12-14 22:08:50

Java组件总目录

MySQL 索引数据结构及使用

Java组件总目录
一、索引介绍
二、索引的优缺点
- 1.优势
- 2.劣势
三、索引的数据结构
四、MySQL索引实现
五、索引创建原则
- 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树是一种多叉平衡查找树。

主要特点：

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

B树的缺点：

B树不支持范围查询的快速查找，如果我们想要查找15和26之间的数据，查找到15之后，需要回到根节点
重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。
如果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。

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

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

四、MySQL索引实现

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

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

主键索引

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

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

辅助索引

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

组合索引

1 组合索引的查找方式

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

select * from t_multiple_index where a=13 and b=16 and c=4;

先在索引树中从根节点开始检索，将根节点加载到内存，先比较a列，a=14，14>13,走左路。（1次磁盘IO）
将左子树节点加载到内存中，先比较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 不符合要求，丢弃。查询结束。
最后得到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 组合索引创建原则

频繁出现在where条件中的列，建议创建组合索引。
频繁出现在order by和group by语句中的列，建议按照顺序去创建组合索引。order by a,b 需要组合索引列顺序（a,b）。如果索引的顺序是（b,a），是用不到索引的。
常出现在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时，具体步骤如下：

执行器使用索引(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’过滤，符合要求，缓存到结果集。
执行器调用"下一行"接口，存储引擎遍历向后找到索引项（13,16,5,id=6）,满足筛选条件a=13 and b >15 and c=5，使用id=6回表获得id=6的行记录。返回给MySQL服务层，MySQL服务层使用剩余条件d='pdf’过滤，不符合要求，直接丢弃。
执行器调用"下一行"接口，存储引擎遍历向后找到索引项（ 14,14,14,id=8）不满足筛选条件，执行器终止查询。
最终获取一条记录，返回给客户端。
可以看到，在使用ICP时，回表查询了2次，然后在服务层筛选后（筛选2次），最后返回客户端。

不使用ICP情况

ICP 的优点

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

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

五、索引创建原则

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

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

2、索引优化建议

一个表的索引个数不能过多。
实际查询时，Mysql一般只用一个索引，多个索引效率低。
- （1）空间：浪费空间。每个索引都是一个索引树，占据大量的磁盘空间。
- （2）时间：
  更新（插入/Delete/Update）变慢。需要更新所有的索引树。
  太多的索引也会增加优化器的选择时间。
频繁更新的字段不建议作为索引。
频繁更新的字段引发频繁的页分裂和页合并，性能消耗比较高。
区分度低的字段，不建议建索引。（仅供参考）
比如性别，男，女；比如状态。区分度太低时，会导致扫描行数过多，再加上回表查询的消耗。如果使用索引，比全表扫描的性能还要差。这些字段一般会用在组合索引中。
姓名，手机号就非常适合建索引。
在InnoDB存储引擎中，主键索引建议使用自增的长整型，避免使用很长的字段。
主键索引树一个页节点是16K，主键字段越长，一个页可存储的数据量就会越少，比较臃肿，查询时尤其是区间查询时磁盘IO次数会增多。辅助索引树上叶子节点存储的数据是主键值，主键值越长，一个页可存储的数据量就会越少，查询时磁盘IO次数会增多，查询效率会降低。
不建议用无序的值作为索引。例如身份证、UUID
更新数据时会发生频繁的页分裂，页内数据不紧凑，浪费磁盘空间。
尽量创建组合索引，而不是单列索引。
优点：
（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 = "张三"

码农公寓