阅读 166

【MySQL】索引进阶(B+树,前缀索引,聚簇索引等)

执行计划

执行计划就是一条SQL的执行过程,当然我们所能观察到的并不是具体的执行过程,而是一条SQL在执行的过程中用到了哪些关键的信息,我们需要根据这些信息来做出判断。

比如说如何判断一条SQL究竟有没有使用索引呢?这时就需要通过执行计划来进行判断。

执行计划的实现需要在SQL前加上explain关键字。例如:

explain select * from emp where name = 'john'; 复制代码

该条SQL执行结束后会输出n多个字段,我们需要知道一些关键字段的含义:

idselect_typetablepartitionstypepossible_keyskeykey_lenrefrowsfilteredExtra
1SIMPLEemp(Null)ALL(Null)(Null)(Null)(Null)12100.00(Null)
  • type:查询类型。

    主要有system、const、ref、range、index、all,从左往右查询效率由高到底。

    如果是all代表着MySQL要进行全表扫描。

    建议最差也要将SQL的type保持在range的级别。

  • key:在执行本条SQL的时候有没有使用到索引。

  • Extra:额外的可选信息。通过这些信息可以帮助我们判断当前SQL的执行效率。

    主要有:Using index(使用索引覆盖)、Using index condition(使用索引下推)、Using filesort(使用临时空间进行排序)。

索引种类

索引是在MySQL的存储引擎层中实现的,而不是在服务器层实现的。所以每种存储引擎的索引都不一定完全相同,也不是任何一个存储引擎都支持所有的索引类型的。

MySQL目前提供了以下4种索引∶

  • B-Tree索引:最常见的索引类型,大部分存储引擎都支持B-Tree索引。

  • Hash索引:只有MEMORY引擎支持,使用场景简单。

  • R-Tree索引:又称"空间索引",是MylSAM引擎的一个特殊索引类型,主要用于地理空间数据类型,通常使用较少,不做特别介绍。

  • Full-Text索引:又称"全文索引",也是MylSAM引擎的一个特殊索引类型,主要用于全文检索,InnoDB从Mysql 5.6开始支持全文索引。

不同存储引擎对于4种索引的支持:

索引类型InnoDBMyISAMMEMOERY
B-Tree索引支持支持支持
Hash索引不支持不支持支持
R-Tree索引不支持支持不支持
Full-Text索引5.6 之后支持支持不支持

我们平常所说的索引,如果没有特别指明,都是指B-Tree索引。B-Tree索引是由B+树(平衡搜索多叉树)结构组织的索引。其中聚集索引、复合索引、前缀索引、唯一索引默认都是使用B+树结构组织的索引。

索引结构

1. 分块读取

首先要知道索引中存储的是Key-Value格式的数据,能够存储Key-Value格式数据的数据结构有很多,比如说:HashMap,树等。而MySQL最终选择了B+树来存储索引,为什么是B+树?

如果当表数据量非常庞大的时候,索引也会与之而变大,如果索引变得足够大之后无法直接加载到内存中怎么办?

假设当前内存8G,而MySQL索引文件达到了16G,最好的解决方案就是分块读取,比如说内存每次只读取1G的索引文件。这种解决方案就映射出来一个思想,就是分而治之

同时我们还要尽可能多的提高IO效率,比如将机械硬盘换成固态硬盘。但是这是硬件解决的问题,我们从软件层面是无法处理的。但是我们可以使用一些辅助手段来提高IO效率:

  • 减少IO量,读10M和读100M的效率一定是不一样的。

  • 减少IO次数,读1次和读10次的性能消耗也一定是不一样的。

这里会涉及到操作系统的两个知识:

  • 局部性原理

    • 时间局部性:之前访问过的数据很有可能再次被访问,至少比陌生数据的概率大很多。

    • 空间局部性:数据和程序都有聚集成群的倾向。

  • 磁盘预读:内存和磁盘在进行交互时有一个最小的逻辑单位,这个单位叫:页,或者叫datapage。一般是4KB或者8KB,由操作系统决定。在内存进行数据读取时,一般会读取页的整数倍,比方说4KB、8KB和16KB等。

InnoDB引擎在进行数据加载时读取的就是16KB的数据,这就是分块读取的集中体现

为什么不用HashMap来存储索引?

  • 利用hash存储需要将所有的数据文件添加到内存,比较消耗内存空间。

  • 需要比较好的Hash算法,如果Hash算法不好,那么会导致Hash碰撞(Hash冲突),会导致数据散列不均匀,影响存储空间造成浪费。

  • 哈希表存储的Key-Value无序,如果要进行范围查找,那么只能遍历哈希表中存储的所有数据了,代价很大。

但是MySQL中还是提供了Hash索引,MEMORY引擎支持的就是Hash索引,InnoDB引擎支持自适应Hash。自适应Hash指的是,正常情况下,InnoDB使用的是B-Tree索引,但是MySQL会判断InnoDB到底使用Hash索引还是B-Tree索引,这个过程人为是干预不了的。

为什么不用二叉树、平衡搜索二叉树、AVL树和红黑树来存储索引 ?

这四种典型的数据结构的共同点在于:这四种数据结构都是二叉树,每一个分支上最多只有两个节点。因此当要像这四种数据结构中插入大量数据时,无论这四种数据结构是否有序是否平衡,都会让其深度变得非常深。在查找时,还是会有较多次的比较操作,虽然比挨个遍历要少。每比较一次相当于一次磁盘IO操作,这样无疑是加大了IO次数,影响查询效率。

为什么每比较一次相当于一次磁盘IO操作?

因为每一个节点必然占用一个磁盘块,在比较时会将该磁盘中的数据读取到内存中。

如果要改进存储的数据结构,需要实现两点:

  • 增加树单个节点的范围。比如说原本每个节点只存1个值,现在每个节点可以存5个值。

  • 增加树单个节点的孩子树。比如说原本每个节点最多只能有两个孩子,现在每个节点最多能有5个孩子。

这样B树和B+树就应运而生了。

2. B树

2.1 定义

B树也叫B-树,是一棵平衡搜索多叉树。

首先我们需要明确一个概念,表述一棵B树和B+树时,需要指定它的阶数,阶数表示一个节点最多有多少个孩子节点,一般用m表示

B树定义如下:

  • 每个节点都存有Key和Value。

  • 根节点最少有 1 对Key-Value。

  • 非根节点最少有 floor(m/2) 对Key-Value。

  • 每个节点最多有 m-1 对Key-Value。

  • 所有叶子节点都位于同一层。

  • 除了叶子节点外,所有节点的孩子数量都是当前Key-Value的数量 + 1。

  • 每个节点中的Key都按照排序规则从小到大顺序排列,该节点左子树中所有Key都小于它,该节点右子树中所有Key都大于它。

综合上述定义,我们可以总结出:

  • 根节点的Key-Value数量范围是:[ 1,m-1 ]

  • 非根节点的Key-Value数量范围是:[ floor(m/2),m-1 ]

以5阶B树为例,根节点K-V数量范围是:[ 1,4 ],非根节点K-V数量范围是:[ 2,4 ]。

2.2 插入数据

插入规则为:

判断当前节点Key-Value的数量是否 <= m-1,

  • <= m-1,则直接插入。

  • > m-1,则先直接插入,然后通过该节点中间的Key将该节点左右分裂成两个节点,中间的Key插入父节点。

例如,以下以5阶B树为例,由于Value在演示数据结构时不起作用,因此突出Key来代表Key-Value:

插入Key为70,18,40,50,22,23,25,39

20211107162738.png

2.3 删除数据

删除原则:

  • 删除叶子节点中的K-V:

    • 兄弟节点的K-V数量 > floor(m/2):直接删除,然后将父节点中最大的K-V移到自身节点,再将兄弟节点中最大的K-V移到父节点。

    • 兄弟节点的K-V数量 <= floor(m/2):直接删除,然后将父节点中最大的K-V移到自身节点,再和兄节点合并。

    • 删除之后叶子节点的K-V数量 >= floor(m/2) :直接删除

    • 删除之后叶子节点的K-V数量 < floor(m/2)

  • 删除非叶子节点中的K-V:直接删除,然后将后继孩子的最小K-V移到自身节点,查看后继孩子K-V数量是否 < floor(m/2)

    • 兄弟节点的K-V数量 > floor(m/2):将父节点中最大的K-V移到自身节点,再将兄弟节点中最大的K-V移到父节点。

    • 兄弟节点的K-V数量 <= floor(m/2):将父节点中最大的K-V移到自身节点,再和兄节点合并。

    • < floor(m/2)

    • >= floor(m/2):无操作

  1. 初始状态树如下

    20211107173219.png

  2. 删除15

    20211107174109.png

    20211107173718.png

  3. 删除22

    20211107180509.png

    20211107180749.png

  4. 删除28

    20211107181239.png

    20211107181544.png

2.4 查询数据

在将查询数据时,就需要将上面的B树的一些细节表现出来,如下:

20211107212715.png

每个节点占用一个磁盘块,都包含着 k 个关于Key升序排列的K-V和 k + 1 个指向孩子的指针,指针存储的是孩子节点所在的磁盘块的地址。

每两个Key能够划分三个范围,这三个范围对应三个指针指向不同的孩子,每个孩子再存储对应范围的K-V。

以根节点为例,Key为16和34,p1指向的孩子代表的数据范围是 < 16;p2指向的孩子代表的数据范围是 16 ~ 34;p3指向的孩子代表的数据范围是 > 34。

假设查询Key = 28,过程为:

  1. 根据根节点找到磁盘块1,读到内存中。

  2. 比较Key = 28在区间 16 ~ 34,找到磁盘块1的指针p2。

  3. 根据指针p2找到磁盘块3,读到内存中。

  4. 比较Key = 28在区间 25 ~ 31,找到磁盘块3的指针p2。

  5. 根据指针p2找到磁盘块8,读到内存中。

  6. 比较Key = 28找到K-V,结束。

2.5 优劣势

优势

B树大多用在磁盘上用于查找磁盘的地址,因为磁盘存放着大量的数据,可能没有办法一次将所有数据加载到内存中,所以只能逐一加载磁盘页,每一个磁盘页对应一个节点。对于B树来说,B树已经很好的将树的高度降低了,从而减少了IO操作。虽然单次读入内存的数据变多了,但是读入的次数却非常少,以至于能够对AVL树和红黑树产生碾压优势。

劣势

每个节点都有Key,同时包含Value,而每个页的存储空间是有限的,如果Value很大会导致每个节点存储的Key的数量变小。

3. B+树

3.1 定义

20211107213259.png

B+树是在B树的基础上进行优化的数据结构。

B+树有两种不同类型的节点:

  • 索引节点:非叶子节点,只存储Key,不存储Value。

  • 叶子节点:叶子节点,既存储Key,又存储Value。

B+树和B树不同的定义:

  • 每个节点最多有 m 对Key-Value。

  • 父节点存有每一个后继孩子的第 1 个Key。

  • 每个叶子节点都有相邻叶子节点的指针。

  • 除了叶子节点外,所有节点的孩子数量都等于当前Key-Value的数量。

3.2 查询数据

B+树有两种搜索方式:

  • 范围搜索:B+树将所有数据都存在叶子节点中,按照B树的搜索方式,时间复杂度为O(logN)。

  • 链表搜索:B+树可以利用叶子节点构成链表进行搜索,先找到最左下的叶子节点,然后顺序搜索。

3.3 优势

  • 由于B+树索引节点只存储Key,因此每个节点可以比B树存储更多的Key,因此能够更大的降低树的高度和将数据范围分成更多的区间。区间越多,数据检索越快。

  • 由于叶子节点都有相邻叶子节点的指针,因此复符合磁盘预读的特性,顺序查询性能更快。

  • 一般情况下,三到四层的B+树足以支撑千万级别的数据量存储。如果再大,就要分库分表了。

索引设计

在选择给字段添加索引时,我们期望该字段(Key)是什么数据类型?

在上文分析B+树原理的时候,我们发现在B+树中,由于指针占用空间一直保持不变,因此唯独对内存占用造成影响的就是Key,

  • 如果Key的类型是int,那么无论具体是多少都占4个字节;

  • 如果Key的类型是char,那么则根据指定的长度来占用,

    • 如果长度小于4,则占用空间小于int。

    • 如果长度大于4,则占用空间大于int。

因此在进行索引设计时,有一个墨守成规的约:让Key尽可能少的占用存储空间。

前缀索引

1. 索引选择性

索引的选择性 = 基数 / 数据表的总记录数,范围: (1 / 数据表的总记录数) ~ 1。

基数,英文为:Cardinality,表示数据表中不重复的索引值的数量,或唯一的索引值的数量

MySQL中使用HyperLogLog算法来做基数统计,该基数计算出来是一个预估值,不是精确值。我们对于基数只需要查看量级就行了,无需深究精确值。

索引的选择性越高则查询效率越高,因为选择性高的索引可以让MySQL在查找时过滤掉更多的行。

选择性为1的叫唯一索引,这是最好的索引选择性,性能也是最好的。

2. 前缀索引

前缀索引是索引优化的一个重要手段,前缀索引仅仅是选择目标列的部分字符作为索引,减少索引的字符可以节约索引空间,从而提高索引效率,但是这样会降低索引的选择性。

对于blob、text或者很长的varchar类型的字段,必须使用前缀索引,因为MySQL不允许索引这些列的完整长度。

例如现在要给一张表中某个varchar(20)类型字段添加索引,这个字段中存储的数据有的只占 4 个字符,有的占 16 个字符。如果在该字段上添加了索引,则有的Key占 4 个字节,有的占 16 个字节。这种情况MySQL是不允许的。

我们可以使用当前字段每一个数据前面固定长度的前缀来充当Key,但是我们在确定前缀长度的时候要保证较高的选择性(接近索引整个列),同时又不能太长。

见如下例子:

假设现在有一张city表,该表中存储16000条城市信息,但是其中城市信息会有重复,现在要给城市名city_name添加索引:

20211108212244.png

  1. 先统计该字段出现重复值最多的前10个,和其出现重复值的次数。

    select count(*) as count, city_name from city group by city_name order by count desc limit 10; 复制代码

  2. 观察该字段前3个字符出现重复值最多的前10个,和其出现重复值的次数。

    select count(*) as count, left(city_name, 3) as prefix from city group by prefix order by count desc limit 10; 复制代码

  3. 观察第2次和第1次查询的结果差距大不大,如果大,向右扩1个字符,检查前4个字符

    select count(*) as count, left(city_name, 4) as prefix from city group by prefix order by count desc limit 10; 复制代码

  4. 观察第3次和第2次查询的结果差距大不大,如果大,再向右扩1个字符,检查前5个字符

    select count(*) as count, left(city_name, 5) as prefix from city group by prefix order by count desc limit 10; 复制代码

  5. 观察第4次和第3次查询的结果差距大不大,如果大,再向右扩1个字符,检查前6个字符

    select count(*) as count, left(city_name, 6) as prefix from city group by prefix order by count desc limit 10; 复制代码

  6. 以此类推,直到观察第7次的结果和第6次的结果差距差不多,停止。第6次的检查前7个字符,那么7就可以作为最终前缀的长度,然后创建前缀索引。

    alter table city add key(city_name(7)); 复制代码

3. 优劣势

优势:使索引更小,大大节约索引空间,提高索引效率。

劣势:

  • 降低索引的选择性。

  • MySQL无法使用其前缀索引所group by和order by,也无法使用前缀索引做覆盖扫描。

聚簇/非聚簇索引

聚簇索引和非聚簇索引并不是一种单独的索引类型,而是一种数据存储方式。具体细节依赖于其实现方式。

B-Tree索引根据存储方式的不同,可以分为聚簇索引和非聚簇索引。

1. 聚簇索引

聚簇索引,英文为:Clustered Index。

聚簇索引就是按照表的主键构造一棵B+树,同时叶子节点中存放的就是该表的行记录数据。通俗来说就是将表中的数据和索引存储到了一起,找到了索引也就找到了数据。

这种存储特性也就决定了每张表只能拥有一个聚簇索引

InnoDB引擎中主键索引使用的就是聚簇索引的存储方式,如果表中没有定义主键,则会选择唯一性索引的字段,如果也没有,则会隐式的定义一个长整型、占6字节的rowid作为主键来作为聚簇索引。

InnoDB引擎中,表数据文件本身就是按照B+树组织的一个索引结构,这棵树的节点的Key是表的主键,叶子节点的Value保存了完整的数据记录。

因此可以说在InnoDB引擎中,索引文件和数据文件是不分离的,表数据本身就是主索引。

2. 非聚簇索引

非聚簇索引,英文为:Non-Clustered Index,也被称为辅助索引或者二级索引。

在聚簇索引之上创建的索引称为非聚簇索引,通俗来说就是将数据与索引分开存储。

复合索引、前缀索引、唯一性索引和MyISAM引擎中的主键索引都是非聚簇索引。

非聚簇索引和聚簇索引一样也是由一棵B+树构造而成,但是叶子节点存储的不再是该表的行记录数据,而是主键或者指定索引字段。

  • 在InnoDB引擎中,非主键索引的B+树的叶子节点存储的是主键。

  • 在MyISAM引擎中,主键索引的B+树的叶子节点存储的是主键。

  • 在MyISAM引擎中,非主键索引的B+树的叶子节点存储的是指定索引字段。

3. 使用场景

假设现在有一张表user,该表的id字段为主键,name字段上添加了一个索引。

现在有两个SQL:

  1. select * from user where id = 7;

  2. select * from user where name = 'Jobs';

在InnoDB引擎和MyISAM引擎中,SQL1和SQL2分别查找过程是什么?

20211109205521.png

使用InnoDB引擎中查找流程

20211110090854.png

SQL1为聚簇索引查找,SQL2为非聚簇索引查找。

SQL1:InnoDB主键索引是聚簇索引,将主键组织到一个B+树中,行数据存储在叶子节点上。使用"where id = 7"这样的条件在主键索引的B+树中查找主键,按照B+树的检索算法即可找到对应的叶子节点,之后访问行数据。

SQL2:InnoDB除了主键索引之外都是非聚簇索引,在InnoDB中所有非聚簇访问行数据都需要进行二次查找。使用"where name = 'jobs'"这样的条件查找name字段需要两步:

  1. 在name索引的B+树中通过 'jobs' 获取行数据对应的主键。

  2. 在主键索引的B+树的中通过获取的主键访问行数据。

使用MyISAM引擎中查找流程

20211110102143.png

SQL1和SQL2都为非聚簇索引查找。

MyISAM引擎中无论是主键索引还是非主键索引都是非聚簇索引,因此主键索引和非主键索引的B+树节点结构完全一致,只是主键索引的B+树的叶子节点存储的是主键,而非主键索引的B+树的叶子节点存储的是非主键字段。

MyISAM引擎中,表数据独立存储,无论是主键索引还是非主键索引的B+树的叶子节点还都会另外存储一个地址,该地址指向表数据中的某一行。因此,每个索引B+树都是完全独立的,不需要进行相互访问(区别于InnoDB)。

SQL1:使用"where id = 7"这样的条件在主键索引的B+树中查找主键,按照B+树的检索算法即可找到对应的叶子节点,之后通过地址引用访问行数据。

SQL2:使用"where name = 'jobs'"这样的条件在name索引的B+树中查找name字段,按照B+树的检索算法即可找到对应的叶子节点,之后通过地址引用访问行数据。

4. 聚簇索引优劣势

优势

  • 聚簇索引的查找速度比非聚簇索引更快,因为在InnoDB引擎中聚簇索引无需二次查找,在MyISAM引擎中聚簇索引无需寻址。

  • 由于聚簇索引的行数据和叶子节点存储在一起,因此同一个数据页中会有多条行数据。访问同一个数据页中不同行数据时,页中的全部行数据已经加载进入内存,再次访问该页某个行数据的时候会直接在内存中完成访问,不必访问磁盘,减少IO操作。

  • 在InnoDB引擎中,如果按照主键来组织数据,那么主键会和行数据一起被载入内存,找到叶子节点后就可以立即将数据返回,获取速度更快。

  • InnoDB引擎中非聚簇索引使用主键值作为"指针"而不是使用地址值作为指针的好处是:减少了当出现行移动或者数据页分裂时非聚簇索引的维护工作。在实际情况中,行的位置会随着表里数据的修改而发生变化,体现在B+树中就是节点的分裂。虽然主键值会比地址值占用更多的空间,但是在出现行移动时无需更新索引中的"指针"。之所以InnoDB的主键索引是聚簇索引,就是为了保证无论主键索引的B+树如何变化,非主键索引的B+树都不受任何影响。

劣势

  • 一张表中可以有多个非聚簇索引,而只能有一个聚簇索引。

  • 维护聚簇索引很昂贵,因为行移动可能会造成碎片。

  • 如果使用UUID作为主键,那么由于UUID本身的特性会导致数据稀疏,这样就会出现使用聚簇索引查询速度可能比全字典扫描更慢,因此建议使用自增id作为主键。

    建议使用自增id作为主键的原因是:聚簇索引的数据的物理存放顺序和索引顺序是一致的,只要索引是相邻的,那么对应的数据也是相邻存放在磁盘上的。如果主键不是自增id,那么存储引擎会不断调整数据的物理地址、不断分页。虽然有一些措施可以减少这些操作,但是无法彻底规避。如果id是自增的,那么只需要一页一页写入数据,索引结构也相对紧凑,磁盘碎片少,效率也高。

  • InnoDB引擎中,如果主键占用空间比较大,那么非聚簇索引会占用更多的物理空间,因为非聚簇索引的叶子节点存储着主键值。

5. 选择

  • 聚簇索引适合用在排序的场合,非聚簇索引不适合。

  • 取出一定范围的数据时,使用聚簇索引。

  • 可以将相关数据保存在一起,然后使用聚簇索引来聚集数据,这样只需要从磁盘读取少数的数据页就可以得到所需的全部数据,减少磁盘IO。

  • 如果涉及到大量数据的排序、全表扫描、count之类的操作的话,建议使用MyISAM引擎。因为所有占用空间小,这些操作是需要在内存中完成的。


作者:ricochet
链接:https://juejin.cn/post/7028851379078692895


文章分类
代码人生
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐