SQL极简教程 · MySQL · MyBatis · JPA 技术笔记 教程 总结MySQLIT狗工作室

mysql索引原理，看这篇就够啦

2019-12-12  本文已影响0人  程序员小饭

前言

网上已经有了很多相关mysql索引原理的文章，但是都存在一些问题，有的是直接复制别人的比较老的文章，有的直接开篇讲B+Tree的原理，过程不是很清楚，即使原理讲清楚了，没有各种数据结构的对比也很难体现出B+Tree的优越性，其实我觉得从一些问题来看，然后根据发现问题解决问题的思路来看，这样可能学习效果会更好，所以写了这篇文章，希望你能喜欢

问题列表

1:数据库中最常见的优化方式是什么？
加索引(相信这个大家都知道)
2:为什么加索引能优化慢查询？
。。。。。
3:哪些数据结构可以优化查询速度？
。。。。。
4:这些数据结构都可以优化查询速度，为何mysql会选择B+Tree
。。。。。
\color{#FF0000}{5:数据库能存多少数据？大概数据达到多少会到达峰值？计算依据是什么？}
\color{#FF0000}{。。。。。}

数据库查询过程

对于一般字段而言，mysql查询都是采用的全表扫描的方式来进行数据查询

WechatIMG111007.png
比如查找
select id from Test where age =1;
扫描第一次就能找到，如果查找
select id from Test where age =7;
可能扫描到第八次才能找到，如果数据非常多，多达几千万行，查找数据最极端的情况下可能需要查找到最后一次才能找到业务所需数据，所以是非常耗时的，我们就需要对数据查找过程进行优化，其实mysql索引就是一种数据结构，来优化查询速度的。方便我们查找数据(包括范围查找和指定查找)

索引的几种数据结构

在这里先给大家介绍一个网站
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
这个网站可以模拟各种数据结构的插入和查找的动画过程，这样更容易理解

二叉树

二叉树其实就是遵循了一个规律来排列，左小右大


二叉树.png

这样的话比比如我们查询9 通过两次比对就可以查询到

但是二叉树这种数据结构存在一些问题，比如数据是递增或者递减的顺序插入，二叉树就很容易形成单路链表


单路链表

如果遇到这种情况那么查找数据就普通的没有加索引的情况没什么区别了

红黑树

红黑树是一种自平衡二叉查找树，平衡二叉树的目的是为了减少二叉查找树层次，提高查找速度
比如依次插入 1到9，二叉树可能就和上图所展示的单路链表一样，红黑树可以自动旋转，减少层数

红黑树.png
具体过程可以在下面链接中插入看演示
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
散列表(hash)

散列表也为哈希表，又直接寻址改进而来。在哈希的方式下，一个元素k处于h(k)中，即利用哈希函数h，根据关键字k计算出槽的位置。函数h将关键字域映射到哈希表T[0...m-1]的槽位上


散列表

散列表的缺点
1）Hash 索引仅仅能满足”=”,”IN”和”<=>”查询，不能使用范围查询。
2）Hash 索引无法被用来避免数据的排序操作。
3）Hash 索引不能利用部分索引键查询。
4）Hash 索引在任何时候都不能避免表扫描。
5）Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。

B树

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：

另外，由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质，而且B-Tree也是不支持范围查找的，所以一般不采用

B+树

B+Tree其实和BTree类似，但是也有很多区别，我们先看图

image
B+Tree的特征
1:每一个父节点的元素都出现在了子节点中，是节点的最大或者最小元素
比如上面事例图中的元素8和15
image
需要注意的是，根结点的最大元素（这里是15），也是整个B+Tree的最大元素
2:由于父节点的元素都出现在了叶子节点，因此所有的叶子节点包含了全部元素信息，并且每一个叶子节点都带有指向下一个叶子节点的指针，形成了一个有序链表
B+Tree的叶子节点
3:在BTree中，每一个节点都包含了数据，但是在B+Tree中，只有叶子节点包含了数据，中间节点仅仅是索引，没有任何数据关联
image

注意：聚簇索引(Innodb)的叶子节点包含了整行数据和索引

\color{red}{注意:对于聚簇索引来说，}
\color{red}{仅仅是主键的索引最终节点包含了数据本身，}
\color{red}{而非主键的叶子节点保存的是主键的值，}
\color{red}{然后再根据主键索引的值走B+树来查找数据本身，}
\color{red}{这么做的目的是为了一致性和节省存储空间}

innodb的索引如图所示


innodb索引.png

而非聚簇索引(myisam)的叶子节点只包含了索引，而不包含数据行本身
其实从数据库保存文件也能看出来，对于非聚簇索引(myisam)的表来说，数据库保存了三个文件
user_m.frm 表结构定义数据
user_m.MYD 表数据
user_m.MYI 索引文件
myisam索引如图所示


mysiam索引.png

而非聚簇索引(Innodb)，数据库只保存了一个文件user_i.frm 所以说他的索引和数据是在一起的。
有一个非常形象的例子大家可以理解一下
非聚簇索引(myisam)相当于是一本书前面的目录，咱们可以根据目录去找到对应的内容
而聚簇索引(Innodb)相当于是书每一页下面的页码，页码和书本的内容是在一起的
B+Tree的优势

  1. 在单元素查询的时候，B+Tree会从根节点，逐层向下查找，最终找到要匹配的叶子节点，只需要三次磁盘IO就能找到，这个流程看起来和BTree差不多，其实并不是这样

  1. 对于范围查询来说B-Tree非常麻烦，如下图


    image

    比如我想查找大于3的数据
    中序遍历到元素6：
    中序遍历到元素8：
    中序遍历到元素9：
    中序遍历到元素11，遍历结束：


    image
    这种回环运算非常麻烦
    像B+Tree就简单了很多

    直接叶子节点链表指过去就行


    image

最后总结一下B+Tree的特征和优势
B+树的特征：

B+树的优势：

索引下推

符合索引(age,name)
在5.6之前
先根据name把所有数据查询出来，然后在server层进行age所有字段筛选
在5.6 之后
从存储引擎拉取数据的时候，会根据age 和name两个字段做筛选，将符合条件的数据拉回

计算数据库能存储多少数据的方法(大概计算)

首先每个索引页可以存储的大小是16kb，这个值可以查到

show global status like 'innodb_page_size'

计算方法如图


innodb索引.png

辅助索引

上面我们说的其实都是基于主键索引，如果非主键索引(辅助索引)查询数据是什么样的呢？
① 在辅助索引上检索name(这个name是例子，意思是代表非主键索引)，到达其叶子节点获取对应的主键；
② 使用主键在主索引上再进行对应的检索操作
这个过程也被称为回表


覆盖索引.png

之所以这么做的原因是 保证数据一致性和节省存储空间，可以这么理解：商城系统订单表会存储一个用户ID作为关联外键，而不推荐存储完整的用户信息，因为当我们用户表中的信息（真实名称、手机号、地址）修改后，不需要再次维护订单表的用户数据，同时也节省了存储空间

select * from table where name = ‘123’；
select id from table where name = ‘123’；
两个表查询的过程是不一样的 select * 需要回表
覆盖索引：在查询普通索引的时候，如果叶子节点保存的刚好是要查询的字段，此时叫覆盖索引

上一篇 下一篇

猜你喜欢

热点阅读