MySql教程

MySQL丨理论丨(二)索引模块

本文主要是介绍MySQL丨理论丨(二)索引模块,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

同步发布:Hedon丨MySQL丨理论丨(二)索引模块(排版更佳!)

  • 为什么要使用索引?
  • 什么样的信息能成为索引?
  • 索引的数据结构?
  • 密集索引和稀疏索引的区别?

1. 为什么要使用索引

索引是数据库中用来提高查询效率的技术,类似于目录。如果不使用索引,数据会零散的保存在磁盘块中,查询数据需要挨个遍历每一个磁盘块,直到找到数据为止,使用索引后会将磁盘块以树状结构保存,查询数据时会大大降低磁盘块的访问数量,从而提高查询效率。当然,如果表中的数据很少,使用索引反而会降低查询效率。

使用索引的核心目的非常简单,其实就是为了提高数据的查询速度。具体体现在以下几点:

  1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性;
  2. 添加索引后,可以大大加快数据的检索速度,这也是创建索引的最主要的原因;
  3. 索引可以加速表和表之间的连接,这样可以加快我们做联合查询时的速度;
  4. 在使用分组和排序子句进行数据检索时,同样可以显著减少查询中分组和排序的时间;
  5. 通过使用索引,可以在查询的过程中,使用优化隐藏器,提高系统的性能。

2. 索引的副作用

  1. 索引是有大量数据的时候才建立的,没有大量数据反而会浪费时间,因为索引是使用二叉树建立.

  2. 当一个系统查询比较频繁,而新建,修改等操作比较少时,可以创建索引,这样查询的速度会比以前快很多。但同时这也会带来弊端,就是新建或修改等操作时,比没有索引或没有建立覆盖索引时的要慢。

  3. 索引并不是越多越好,太多索引会占用很多的索引表空间,甚至比存储一条记录更多。
    对于需要频繁新增记录的表,最好不要创建索引,没有索引的表,执行 insert、append 都很快,有了索引以后,会多一个维护索引的操作,一些大表可能导致 insert 速度非常慢。

3. 平衡二叉树

img

性质

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

4. B 树

参考:https://zhuanlan.zhihu.com/p/27700617

img

性质

一棵 m 阶 B 树(balanced tree of order m)是一棵平衡的 m 路搜索树。它或者是空树,或者是满足下列性质的树:

1、每个结点至多有 m 个分支(子树),而最少分支要看是否为根结点:

  • 是根非叶结点:至少 2 个分支
  • 非根非叶结点:至少有 ⎡m/2⎤个分支

2、有 n(k≤n≤m)个分支的结点有 n-1 个关键字,它们按照递增顺序排序。k = 2(根结点)或 ⎡m/2⎤(非根结点)。

3、结点内各关键字互不相等。

4、叶子结点处于同一层,可以用空指针表示,是查找失败到达的位置。

查找

简单:相等停,大往右小往左。

插入

定义一个 5 阶树(平衡 5 路查找树;),现在我们要把 3、8、31、11、23、29、50、28 这些数字构建出一个 5 阶树出来;

遵循规则:

(1)节点拆分规则:当前是要组成一个 5 路查找树,那么此时 m = 5,关键字数必须 <= 5-1(这里关键字数 >4 就要进行节点拆分);

(2)排序规则:满足节点本身比左边节点大,比右边节点小的排序规则了;

  • 先插入 3、8、31、11

    image-20210112085051252
  • 再插入 23、29

    image-20210112085117494
  • 再插入 50、28

    image-20210112085147205

删除

(1)节点合并规则:当前是要组成一个 5 路查找树,那么此时 m=5,关键字数必须大于等于 ceil(5/2)(这里关键字数 <2 就要进行节点合并);

(2)满足节点本身比左边节点大,比右边节点小的排序规则;

(3)关键字数小于二时先从子节点取,子节点没有符合条件时就向向父节点取,取中间值往父节点放;

image-20210112085234255

特点

B 树相对于平衡二叉树的不同是,每个节点包含的关键字增多了,特别是在 B 树应用到数据库中的时候,数据库充分利用了磁盘块的原理(磁盘数据存储是采用块的形式存储的,每个块的大小为 4K,每次 IO 进行数据读取时,同一个磁盘块的数据可以一次性读取出来)把节点大小限制和充分使用在磁盘快大小范围;把树的节点关键字增多后树的层级比原来的二叉树少了,减少数据查找的次数和复杂度。

5. B+ 树

参考:http://data.biancheng.net/view/61.html

img
(图1)

性质

B+ 树是 B 树的一种变形形式,B+ 树上的叶子结点存储关键字以及相应记录的地址,叶子结点以上各层作为索引使用。

1、在 B+ 树中,具有 n 个关键字的结点含有 n 个分支;而 B 树中,具有 n 个关键字的结点含有 n-1 个分支。

2、B+ 树结点的关键数个数 n 取值:

  • 根结点:2≤n≤m(B 树中是 1≤n≤m-1)
  • 其他: ⎡m/2⎤≤n≤m(B 树中是⎡m/2⎤-1≤n≤m-1)

查找

对B+树可以进行两种查找运算:

  • 从最小关键字开始,进行顺序查找。
  • 从根结点开始,进行树的方式查找

插入

1、 若被插入关键字所在的结点,其含有关键字数目小于阶数 M,则直接插入结束;

例如,在图 1 中插入关键字 13:

img
(图2)

2、 若被插入关键字所在的结点,其含有关键字数目等于阶数 M,则需要将该结点分裂为两个结点,一个结点包含⌊M/2⌋,另一个结点包含⌈M/2⌉。同时,将⌈M/2⌉的关键字上移至其双亲结点。假设其双亲结点中包含的关键字个数小于 M,则插入操作完成。

例如,在图 1 的基础上插入关键字 95:

img
(图3)

3、在第 2 情况中,如果上移操作导致其双亲结点中关键字个数大于 M,则应继续分裂其双亲结点。

例如,在图 1 的 B+ 树中插入关键字 40,则插入后的 B+ 树如图 4 所示:

img
(图4)

删除

1、 找到存储有该关键字所在的结点时,由于该结点中关键字个数大于⌈M/2⌉,做删除操作不会破坏 B+ 树,则可以直接删除。

例如,在图 1 所示的 B+ 树中删除关键字 91,删除后的 B+ 树如图 5 所示:

img
(图5)

2、 当删除某结点中最大或者最小的关键字,就会涉及到更改其双亲结点一直到根结点中所有索引值的更改。

例如,在图 1的 B+ 树中删除关键字 97,删除后的 B+ 树如图 6 所示:

img
(图6)

3、 当删除该关键字,导致当前结点中关键字个数小于⌈M/2⌉,若其兄弟结点中含有多余的关键字,可以从兄弟结点中借关键字完成删除操作。

例如,在图 1 的 B+ 树中删除关键字 51,由于其兄弟结点中含有 3 个关键字,所以可以选择借一个关键字,同时修改双亲结点中的索引值,删除之后的 B+ 树如图 7 所示:

img
(图7)

4、 第 3 种情况中,如果其兄弟结点没有多余的关键字,则需要同其兄弟结点进行合并。

例如,在图 7 的 B+ 树种删除关键字 59,删除后的 B+树为:

img
(图8)

5、 当进行合并时,可能会产生因合并使其双亲结点破坏 B+ 树的结构,需要依照以上规律处理其双亲结点。

例如,在图 6 的 B+ 树中删除关键字 63,当删除后该结点中只剩关键字 72,且其兄弟结点中只有 2 个关键字,无法实现借的操作,只能进行合并。但是合并后,合并后的效果图如图 9 所示:

img
(图9)

如图 9 所示,其双亲结点中只有一个关键字,而其兄弟结点中有 3 个关键字,所以可以通过借的操作,来满足 B+树的性质,最终的 B+ 树如图 10 所示:

img
(图10)

特点

1、B+ 树的层级更少:相较于 B 树 B+ 每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快;

2、B+ 树查询速度更稳定:B+ 所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同所以查询速度要比B树更稳定;

3、B+ 树天然具备排序功能:B+ 树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高;

4、B+ 树全节点遍历更快:B+ 树遍历整棵树只需要遍历所有的叶子节点即可,而不需要像 B 树一样需要对每一层进行遍历,这有利于数据库做全表扫描。

B 树相对于 B+ 树 的优点是,如果经常访问的数据离根节点很近,而 B 树非叶子节点本身存有关键字其数据的地址,所以这种数据检索的时候会要比 B+ 树 快。

6. Hash 索引

image-20210112092331310
  • 仅仅能满足“=”,“IN”,不能使用范围查询;
  • 无法被用来避免数据的排序操作;
  • 不能利用部分索引键查询;
  • 不能避免表扫描;
  • 遇到大量 Hash 值相等的情况后性能并不一定就会比 B Tree 索引高。

7. Bitmap 索引

image-20210112092604311
  • 很多数据库不支持,Orcle 支持;
  • 当值只有固定的几种情况的时候才可以使用(如性别只有男、女这两种情况);
  • 不适合高并发情景,因为加锁很严格。

8. 稠密索引和稀疏索引

稠密索引

在稠密索引中,文件中的每个搜索码值都对应一个索引值。

image-20210112095741821

稀疏索引

在稀疏索引中,只为搜索码的某些值建立索引项。也就是说,稀疏索引为数据记录文件的每个存储块设一个键-指针对,存储块意味着块内存储单元连续。

image-20210112095826890

区别

  1. 稠密索引文件中的每一个搜索码值都对应一个索引值;稀疏索引文件只为索引码的某些值建立索引项;
  2. 稠密索引查找时间较短,索引存储空间较大;稀疏索引占用的索引存储空间比较小,但是查找时间较长。

8. SQL 调优

  1. 根据慢日志定位慢查询 SQL
  2. 使用 explain 等工具分析 SQL
  3. 修改 SQL 或者尽量让 SQL 走索引

9. 联合索引的最左匹配原则的成因

演示

  1. 创建一个表,其中有一个联合索引为

    ...,
    KEY 'index_area_title' ('area', 'title'),
    ...;
    
  2. 按照 area 和 title 来查 ——> 走了 index_area_title 索引

    image-20210112111511094

  3. 只按照 area 来查 ——> 依旧走了 index_area_title 索引

    image-20210112111548167

  4. 只按照 title 来查 ——> 不走索引

    image-20210112111705043

解释

假设组合索引为:a,b,c 的话;那么当 SQL 中对应有:a 或 a,b 或 a,b,c 的时候,可称为完全满足最左原则;当 SQL 中查询条件对应只有 a,c 的时候,可称为部分满足最左原则;当 SQL 中没有 a 的时候,可称为不满足最左原则。

MySQL5.7 开始,会自动优化,如:会把 c,b,a 优化为 a,b,c 使之完全遵循最左原则;会把 c,a 优化为 a,c 使之部分遵循最左原则。即:SQL 语句中的对应条件的先后顺序无关。

成因

  1. MySQL 创建联合索引是首先会对最左边,也就是第一个索引字段进行排序

  2. 在第一个排序的基础上,再对第二个索引字段进行排序,其实就像是实现了Order by字段1,再Order by 字段2这样一种排序规则。所以第一个字段是绝对有序的,而第二个字段就是无序的了

因此通常情况下,直接使用第二个字段进行条件判断是用不到索引的。这就是为什么 MySQL 要强调最左匹配原则的成因。

10. 如何创建索引

PRIMARY KEY(主键索引)
ALTER TABLE 'table_name' ADD PRIMARY KEY ('column');
UNIQUE KEY(唯一索引)
ALTER TABLE 'table_name' ADD UNIQUE ('column');
INDEX(普通索引)
ALTER TABLE 'table_name' ADD INDEX index_name ('column');
FULLTEXT(全文索引)
ALTER TABLE 'table_name' ADD FULLTEXT ('column');
多列索引
ALTER TABLE 'table_name' ADD INDEX index_name ('column1','column2','column3');

11. 如何删除索引

ALTER TABLE 'table_name' DROP INDEX index_name;
这篇关于MySQL丨理论丨(二)索引模块的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!