【聊聊MySQL】四.MySQL-InnoDB表索引和B+树
一.InnoDB表数据
上面聊了这么多这个结构,那个结构的。现在是不是有点好奇,InnoDB
是把数据存在哪里的。答案也很简单,存在一颗 B+
树种。
在 InnoDB
中,数据所在的位置没有其他地方,就只有一颗 B+
树。而我们自己建立的索引,也是一颗 B+
树。存储完整数据的 B+
树也叫 聚簇索引
,而我们自定义的列索引的 B+
树,则称为 非聚簇索引
。
OK,大概明白了这两个东西以后,我们一个一个拆开来说说。
二.B+树是什么
关乎数据结构的东西了,如果觉得很简单,或者说已经学过脑袋有印象,可以跳过这段一个非计算机老男人写的废话。
说 B+
树,一切要从一个最简单的例子开始,就是二分查找法。
2.1 二分查找法
我们在聚合的时候,估计都玩过一个游戏,叫做大冒险。确定谁来大冒险,有个方式就是猜数字:由上一轮中的倒霉鬼,来确定一个数字,然后围成一圈的小伙伴们来猜。猜中了,就是下一个倒霉鬼。
那怎么猜的呢,这个倒霉鬼在手机上输入一个数字,盖在地上防止修改。然后从一圈中某个人开始,说一个数字,那么那个站在台上的倒霉蛋就会缩小范围,让下一个人继续猜:
比如数字是69。
那么就有下面的对话:
1 | A: 50 |
这个过程咧,有没有很熟悉,对,就是 二分查找法
。
那为啥使用二分查找法呢,肯定是因为性能好啊。
那比如我有个 有序 数组:[18, 53, 55, 147, 151, 495, 551, 606, 638, 728]
。
我一次查询每一个数字,平均次数是 (1+2+3+4+5+6+7+8+9+10)/10 = 5.5次
,而使用二分查找法则是 4+3+2+4+3+1+4+3+2+3)/10 = 2.9次
。顺序查找最坏的情况也要 10
次,而二分查找最坏是 4
次。这么好的查找效率没有理由不用他。
2.2 二叉查找树
那二分查找和树什么关系,这里就要说到 二叉查找树
,根据百度百科的定义:
一棵空树,或者是具有下列性质的二叉树:
(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉排序树;
(4)没有键值相等的结点。
那么我现在把上面的数组转换成 二叉查找树
,并且给予一个查找的动图:
查询看起来是很方便,但是对数据的增删查改就不是这样的了。有时候,数据插入多了,如果不调整可能会所有都放在了左边或者右边,这样性能就会越来越接近顺序查找。那么,数学家就提出了 平衡二叉树
和 最优二叉树
的定义。
2.3 平衡二叉树
平衡二叉树:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。这样子就可以让树变得矮胖矮胖的好身材,至于为啥矮胖矮胖才是好身材,因为这样子的话,查询效率才高啊。
比如下面这颗,查找大于 495
的时候,简直就是线性查找的效率了。
那长得丑怎么办,整容(旋转跳跃我闭着眼)啊,不过需要钱(性能)。
那我现在就按照 二叉查找树
那一颗,来插入一个 999
,平衡二叉树是在增删改的时候通过旋转来平衡树。
那么有长得帅的读者就要问了,这个跟 B+树
是什么关系。
2.4 B+树
因为 B+树
跟上面的思想差不多,所以,现在就来说说 B+树
。
B+树
她不是二叉树,但是查询跟 二叉树
差不多,我先放一颗 B+树
。
这是一颗高度为 2
扇出为 5
的 B+树
。
那这个怎么实现查找的呢,现在比方说我要查找 606
这条数据:
那么 B+树
是怎么实现新增,然后平衡的呢,跟上面一样发生旋转。旋转的规则如下:
叶子节点是第二层的数据,索引节点是第一层查找时用到的数据。那旋转的情况就是节点页有没有满了:
叶子节点 | 索引节点 | 操作 |
---|---|---|
× | × | 直接插入 |
√ | × | 1. 拆分叶子节点; 2. 中间节点值存入索引节点; 3. 小于中间节点的数据放左叶子,大于或等于放入右叶子。 |
√ | √ | 1. 按照上面情况拆分叶子节点; 2. 然后根据相同的操作再拆分索引节点 |
第一种就不用演示了,比如新增 1000
直接存入最后边的叶子节点就好了。
接下来我演示第二种,那我就插入 645
这个数字吧。
可以从图中看到,拆分页是多么耗性能的一个东西了,所以我们经常说顺序插入是最好的性能,也要求主键一般呈递增的状态。
但是当左右兄弟节点可能没有满的时候,InnoDB不会急着去拆分数据页,而是会通过旋转的方式来让树达到平衡。这里就不说了。
那如果是第三种情况呢,拆分索引页跟拆分数据页是同样的道理,我就不画出来了,只要知道如果是第三种,性能还要比第二种低一倍,因为不仅拆分数据页,还拆分索引页了。
那如果页中有记录被删除呢,怎么去平衡,这时候就有一个东西叫做 计算因子
,如果删除后的页的记录数量小于 计算因子*总页数
的时候,B+
树会去做 合并操作
。那我就继续用这一组数据来做示例。
删除 606
638
以后,B+
树就会变成下面这个样子:
所以说,B+
树在发生了修改以后,为了保证查询效率,会对某个一部分的节点进行整容。
三.InnoDB是怎么用B+树
好,结合上一篇的 InnoDB表结构
中的页和数据行的结构,以及刚刚所说的 B+树
,现在我们就可以来看看一个表中的数据,是怎样被存储以及怎样被查询的。
从之前我们知道,数据是按照数据页的方式进行存放的,而数据页里面除了记录我们的用户记录行意外,还有一些额外的属性用来表示这一页的类型(所以数据页不仅仅是存放数据的页,也可能是 undo页
等等),而数据行里面也有一些额外的属性来辅助查找。
3.1 查找数据所在的页
之前已经系统的列举过 数据页
和 数据行
的所有属性,现在我就挑在索引中需要用到的属性放在图中就可以了,放上其他的没什么用处,也占用地方。
那我现在就假设,上一节中的叶子节点中的数据(如下图),就是我们一条记录的主键 id
,因为我们的记录肯定不止有主键这么简单,所以应该还有其他数据,我暂时使用一些占位的方框做代替。
那么这时候上面在数据在 MySQL
数据页中的结构,应该是这样子的:
叶子节点之间的关系,记录类型中:2
表示最小记录,3
表示最大记录,0
表示用户记录。那如果这棵树没有非叶子节点的话,搜索就是线性的需要一个一个遍历,这时候怎么办咧,B+树
的结构就出现了。
这个结构,就是上面 B+树
在 InnoDB
中数据页的结构了。
3.2 查找真实数据
那么,上面我演示的一个页有三个记录,但其实不止三个记录,我就假设一个页有 16
条记录(其实不止,根据数据的大小)吧。那通过索引只能找到这一页呀,难道要一个一个遍历查询相对应的数据,这时候使用遍历还是有点早了(毕竟遍历并没有那么高效),所以在每个数据页中,又使用了一个槽进行分区。
那现在把镜头切换到一个页中来:
InnoDB
会把一个页中的所有数据根据一个很小的基数,比如 4
个记录为一组,去划分分组。那么每个组在数据页中都有对应的槽来记录分组的最大值。
那按照上面的数据,比如我要查询 55
。
槽0
= 18,槽1
= 54,槽2
= 64,槽3
= 77。
怎么找呢,类似于上面那个二分查找的游戏,槽0
说 18
,老大说 18-77
之间,槽1
说 54
,老大说 54-77
,直到最后,确定数字是在 槽1
和 槽2
之间,因为 槽2 = 64
大于 55
,而 槽1 = 54
小于 55
。所以从 槽1
的最大值 54
开始寻找下一条记录,遍历分组里面的数据行(因为这时候需要遍历的长度已经被切到很小了,所以是时候用遍历来做了,因为用其他算法的次数跟遍历差不多),取出 55
这条数据。
那整个查询过程中,需要跟硬盘交互的并不多,我们知道,InnoDB
是通过数据页来进行硬盘与内存的沟通的,查找效率高就意味着,我需要从硬盘取数据的次数越少。
3.3 删除记录
删除记录时,InnoDB
是怎么做的,就是在之前提到的数据行的头信息的 delete_flag
设置为 1
,这条记录就会被放入 垃圾链表
,当又需要插入新数据的时候,会判断是否合适放在这个位置,再把原来的数据给覆盖掉。
为什么这么做无非就是减少 硬盘IO
。如果真的删除的话,需要去同步硬盘,这个过程并不是很重要,所以先标记就好了。
然后这条记录的上一条记录的 next_record
字段将被重新指向当前删除记录的下一条记录。
四.聚簇索引
那聚簇索引是什么,其实看了上面的图,加点料就可以了:
其实上面的例子我使用的是 id
来做例子,但是每条记录还带有其他所有列的信息(非 NULL
)的,如果有 NULL
则会被记录在记录头信息,然后节省了存储数据的空间。
而这种索引,叫做 聚簇索引
,意思是什么咧,就是一条记录保存了完整的数据信息,非聚簇则不是。而每条数据都会有一个 primary key
,如果没有,InnoDB
会自动加上这个隐藏的列。这也是 MySQL_InnoDB
结构的库保存数据的方式。
所以可以这么说,InnoDB
就是 B+树
构成的。而根节点从建立表开始将会被记录,之后每次查询都会从这个根节点开始查询。
五.非聚簇索引
5.1 简单非聚簇索引
那 非聚簇索引
和 聚簇索引
有什么区别,区别在于 非聚簇索引
并没有存放整条记录的所有数据,只是存放了 索引列
和 主键
而已。所以当我们通过 非聚簇索引
查询一条数据行的所有列的时候,就需要 回表
去查询其他列的信息了,也就是说需要 两次查询
才完成这个需求。
比方一个表:
1 | CREATE TABLE trbac_user ( |
那我使用 name
来做非聚簇索引,这时候 InnoDB
就有一颗以 name
来查询的 B+树
:
那我们可以看到,数据行并没有覆盖所有数据,只有 name
+ id
。那比如我们只是查询 name
或者 id
列,就可以直接在这里返回去了。
但是如果我还想要知道 mobile
列的话,这时候就需要在上面那棵树拿到 id
,然后再去 id
那棵树查询其他的列信息。
需要从下面的主键的数据页来查询其他数据。
那这里有个什么经验呢…就是我们可以根据经常使用常用的列来建立索引,先拿到 id
,然后再去缓存命中,再走数据库~
单列聚簇索引还有个需要注意的点,就是这个列的辨识度要搞,如果这个列只有 MAN
和 WOMAN
的话,为这个列建立索引根本就没有什么用处,因为跟全表扫描一样的效率,优化器更偏向于全表扫描,所以切记不要给列值只有寥寥几个的列建立索引,纯属浪费。
5.2 多列非聚簇索引
如果是 name
+ mobile
联合索引的话,需要注意的点就有点多了:
每个数据页的排序就会变成,先按照 name
进行排序,然后再按照 mobile
进行排序。
5.4 什么时候不会使用索引
1.不满足最左匹配
我想大家都听过 最左匹配原则
,就是这个意思,因为我的索引是先根据 name
排序再根据 mobile
进行排序的。那么查询的时候,如果加上 order by
的话,这个排序同样也是派上用场的。
但是如果说查询条件只是写了 WHERE mobile = '13800x1'
,那上面的索引就完全派不上用场。
怎么说,因为我这个索引是结合了 name
先做排序然后索引的,你只是查询 mobile
的话,就需要遍历整个索引,拿到 id
后还需要回表,这个过程跟直接扫描 聚簇索引
相比,耗费的资源更多,所以,如果一个 name
+ mobile
的索引,只应用于带有 name
开始的查询条件。因为 name
在前面。这就是 最左匹配原则
。
2.排序一个列使用升序一个使用降序
比如 WHERE name like 'xxx%' ORDER BY name DESC,mobile ASC
,这样的情况只能用到 name
列的索引(也就是所有 mobile
失去了效果),然后再把所有列重新整理,依据 mobile
重新排序。
如果两个都是同一个方向的排序就不会出现这种情况。
3.VARCHAR
匹配前缀查询
WHERE name like '%狗蛋'
这种情况为什么不能使用索引呢,因为你前面未知啊,根据 name
排序的索引查询跟全表扫描有什么区别,还少了 回表
的操作,所以只能全表扫描,取出满足 xxx狗蛋
的数据了。
4.排序用到索引中没有的列
这个理解了 区别在于 非聚簇索引
并没有存放整条记录的所有数据,只是存放了 索引列
和 主键
而已 这句话,就知道为什么了,因为索引中的排序并不适合 SQL
指定的顺序。
5.使用函数修饰值的时候
比如 WHERE LOWER(name) = 'aa'
,每个列都需要通过函数调用,那就跟全表扫描没什么区别了。
那如果 SQL
语句中,条件出现的顺序没有和多列索引的顺序一致的话,会怎么样:
完全不必担心这个问题,因为 SQL
在执行之前还会交给一个叫做 优化器
的东西进行整理,下面会说到,现在就只要知道他会把 SQL
条件整理成跟索引一样的顺序就好了。
既然多列索引可以帮忙查询条件中满足最左匹配的 SQL
语句,是不是越多越好,答案并不是,我觉得应该根据权重来区分,因为 非聚簇索引
他的索引列并不会像自增 ID
的索引树一样,顺序的插入数据(历史原因导致我们项目使用 UUID
做主键的哭晕在厕所),而是经常的造成 页拆分
(也就是上面拆分的动图),所以 非聚簇索引
多了,增删改
需要维护这棵树平衡所做的 整容
就越多,严重的话会影响 增删改
的效率。
5.5 什么时候命中索引
那什么时候用到了索引,自然就是避免上面的情况就可以了,就有这些情况,包括但不局限于:
- 条件覆盖了索引的最左列;
- 常量查询,
WHERE name = 'xxx'
; - 范围查询,满足
1
的情况下,比如name > 'AA'
或者name = 'AA' AND mobile > '13800'
; - 排序,但是需要用到的排序列是同一个方向进行排序的。
- 分组,依然需要满足
1
条件,如果用到了group by name
,InnoDB
会先将相同的name
放在一起,然后再继续根据其他条件进行运算。
5.6 回表代价
可以这么说,如果回表的代价过高,InnoDB解析器
可能直接决定,不要使用索引,直接全表扫描。
怎么回事,就是 非聚簇
索引他的值都是连在一起的,查询的时候,称为 顺序I/O
,而 非聚簇索引
查询出来的 id
并不会连在一起,所以回表去查询 id
数据的时候,称为 随机I/O
。而 随机I/O
的效率是很低的,所以当命中索引的数据行总是较多的时候,不如 全表扫描
来的快,所以可能出现 SQL
已经完全命中这个索引但是解析器他就是不使用。
怎么防止这种情况发生,就是让查询索引返回的数量少,比如我们可以 LIMIT 100
去限定只查询 100
条数据,或者我们只要查询索引中出现的列,比如 id
然后再在程序中,根据 id
列表去命中缓存,名不中的再一次性批量查库就可以了。
5.7 文件排序
有时候我们去解析 EXPLAIN
我们的 SQL
语句的时候,会出现 File Sort
类型,这个类型指的是,查询出来的结果不是按照我们 SQL
指定的顺序来的,所以需要在内存中(必要时借助硬盘)来重新对数据进行排序,这个过程就是 File Sort
,那如何避免这个类型出现,那就是防止上面不命中索引的情况。
5.8 索引合并
使用等值且命中两个索引的列
比方说我的用户表有 name
索引 和 mobile
索引,那这个条件 WHERE name = 'Weidan' AND mobile = '18588777777'
就可以使用两个索引,然后取 id
的 交集,然后回表查询。但是如果 name > 'Weidan'
这种条件,就不会使用到合并。
但是但是,如果是主键列是范围的话,是可以的,因为他们合并的时候也会操作主键嘛。
不过有没有使用到,还要看成本,如果一个索引命中的数据太多,依然不会使用合并索引。
合并两个索引的列
依然需要满足 列都是等值查询 这个条件,比如 WHERE name = 'Weidan' OR mobile = '18588777777'
,会合并两个主键再统一回表查询。
范围搜索合并查询
不过如果我们是范围查询,又想使用两个索引怎么办,我们可以把 name > 'Weidan'
以及 monile > '18588777777'
先查询出来 id
然后 union
在一起,再通过 id
去寻找我们想要的数据。
但是还是建议把需要合并的列作为一个 非聚簇
索引来覆盖,效率要高。
七.表连接查询
首先就以最经典的学生、成绩来做示例吧:
1 | CREATE TABLE `student` ( |
7.1 连表查询
那么先列举一个连表很普通的例子:
1 | SELECT * |
可以看到,如果我们不加任何条件,直接就连接两张表的话,取出来的结果就是第一张表所有的数据,去搭配第二张表所有的数据,也就是第一张表有 3
条数据,第二张表有 4
条记录,结果就有 3 ✖ 4 = 12
条记录。这个过程也称为 笛卡尔积
。这种情况在日常编程中应该也没人会这么写的吧,仔细想想,如果两张表都是百万级别的数据,笛卡尔积是多恐怖的一件事情。
7.2 内连接
就是由于上面的结果集一般我们都不需要,所以我们会加上一些条件加以限制:
1 | SELECT stu.*, scp.* |
这就是我们想要的结果集,所有参考学生的考试成绩。
而 InnoDB
是怎样的实现两个表连接的呢,这时候,优化器会根据查询成本确定 驱动表
和 被驱动表
。
驱动表:先查询的那个表,这里假设是
student
表,所以执行的时候,第一步执行SELECT * FROM student;
;被驱动表:查询出来驱动表所有的数据以后,就会根据驱动表中每一条数据,去执行被驱动表。
- 比如我现在
student
有三条记录,分别id
是1
2
3
; - 然后对三条记录分别执行
SELECT * FROM scope WHERE stu_id = ?
; - 因为
scope
表中不存在翠花
的成绩,所以SELECT * FROM scope WHERE stu_id = 3
并没有展示出来,因为这个语句相当于SELECT * FROM scope WHERE stu_id NOT NULL AND stu_id = 3
- 比如我现在
那如果上面的语句加上其他条件会怎么样,比如:
1 | # 查询成绩 90 分以上的学生成绩信息 |
那在访问驱动表 student
的时候同上面一样,但是针对驱动表中每一条数据执行被驱动表的时候,就会变成:
SELECT * FROM scope WHERE stu_id NOT NULL AND stu_id = ? AND scope > 90;
一句话就是说,这些条件针对哪个表,在执行那个表的时候就会带上指定的条件。
内连接推荐写法:
1 | SELECT stu.*, scp.* |
效率没有变高,但是可读性变好,在我看来,特定的限定功能就需要放在特定的位置,连接条件在 ON
后面,而查询条件在 WHERE
后面,也可以很好的跟下面的外连接写法统一。
7.3 外连接
外连接的目的是将连接在一起查询的表中,以某个表为主要目的,查询他在另外一个表的所有信息,包括不存在的信息。比如还是上面的例子,翠花她是个坏学生,一个科目都没有参加考试,但是老师如果通过上面的内连接查询来看的话,可能都不知道还有这个人的存在。这就麻烦大了啊,家长上门投诉,我给你钱了,她没参加考试你都不管管的吗。所以这时候,就需要外连接来做这个事情了:
1 | SELECT * |
这个时候,嗯哼,一抓一个准,没有来考试的,在 scope
表的字段中,显示为 NULL
。
关于 驱动表
和 被驱动表
的含义已经在上面内连接的内容中指定,那么如果说 内连接
是根据成本来指定 驱动表
的,那 外连接
就是我们来指定驱动表。
以 驱动表
所有满足我们条件的数据,来查询 被驱动表
,如果 被驱动表
不存在 驱动表
中某条数据的关联,显示为 NULL
。
那么关键点在哪里,就在这个 ON
后面的条件,ON
后面的条件,是指定 被驱动表
中不满足 ON
条件情况下依然要显示的关键。(在内连接中连接条件放 ON
和放 WHERE
效果一样)
如果外连接有几层,比如说三层:
1 | SELECT * |
那么上面这条查询需要怎么走呢,先查询老师所有的学生,得到一张中间表以后,再以这张中间表作为 驱动表
来查询 scope
。
八.复杂条件查询
MySQL InnoDB
中存在着 SQL解析器
,解析器可谓为了查询正确的数据而费尽心思,目的只有一个,就是较快的查询出来正确的数据。其实这里也可以联想到 jvm编译器
,为了执行效率比较快,会对字节码进行一些顺序的重新编排,什么 happen before
规则都出来了。
而什么东西查询最快呢,那就是查询常量的时候了。
8.1 整理查询语句
首先就是去除不必要的括号,因为括号如果没有意义存在,那移除了就更有利于优化器的解析了。
比如 WHERE (id = 1)
会被优化成 WHERE id = 1
。这个好像也没什么好说的。
复杂一点的 WHERE (id = 1 AND name = 'WEIDAN') AND age = 20
则会被优化成 WHERE id = 1 AND name = 'WEIDAN' AND age = 20
。
8.2 简化查询条件
WHERE age > 18 AND real_age > age
则直接变成 WHERE age > 18 AND real_age > 18
8.3 删除废话条件
像我之前老师教的,在写 MyBatis Mapper.xml
的时候,因为 WHERE
总是需要动态的条件,所以前面会加一个 WHERE 1 = 1
(为啥不用标签,因为标签可读性其实不怎么高)。
那么,如果我写的是 WHERE 1 = 1 AND name LIKE 'Weidan%'
,那么语句将会被直接优化为 WHERE name LIKE 'Weidan%'
。这么想想好像直接写 WHERE 1 = 1
除了解析器多了点工作,好像也没什么所谓了。
8.4 计算表达式
WHERE age = 9 + 9
那么解析器会直接给你个 WHERE age = 18
。不过如果这些计算方式放在了列名上,比如:
1 | WHERE -age = -18 |
解析器害怕他也优化错了,所以也会放弃优化,一个简单的记忆就是函数发生在等号后面的常量值上,可以优化,但是如果需要依赖列的计算的话,那就放弃优化了。
8.5 必要时转换外连接到内连接
右外连接
会被转换为左外连接
,毕竟 左外连接
更好确定 驱动表
和 被驱动表
。
那如果我们在查询 左外连接
的时候,暗示着我得出的结果中,被驱动表不含 NULL
的值,聪明的暖男解析器将会 GET 到这个信息,把 外连接
优化成 内连接
。
比如上面的例子中:
1 | SELECT * |
那么上面两个语句中是不是就都暗示解析器中,拿到的 scope
中的 id
不能为空。
所以!直接变成这条语句执行:
1 | SELECT * |