MySQL:从B树到B+树到索引再到存储引擎

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

MySQL:从B树到B+树到索引再到存储引擎

来源:blog.csdn.net/that_is_cool/article/details/81069945

索引其实是一种数据结构,在数据库中,读写的比例是在10:1,所以如果每一次查找都全表查找的话,效率将会变的十分的低下。所以,本文将会按照题目,按部就班地讲解MySql的索引。

##B树和B+树 B树和B+树算是数据结构中出现频率十分高的模型了,在笔者之前的几篇博客,有对二叉查找树和二叉平衡树进行过讲解和代码分析,但是那些都是在程序中使用比较多的树,在数据库中,数据量相对较大,多路查找树显然更加适合数据库的应用场景,接下来我们就介绍这两类多路查找树,毕竟作为程序员,心里没点B树怎么能行呢?

B树:B树就是B-树,他有着如下的特性:

  • B树不同于二叉树,他们的一个节点可以存储多个关键字和多个子树指针,这也是B+树的特点;
  • 一个m阶的B树要求除了根节点以外,所有的非叶子子节点必须要有[m/2,m]个子树;
  • 根节点必须只能有两个子树,当然,如果只有根节点一个节点的情况存在;
  • B树是一个查找二叉树,这点和二叉查找树很像,他都是越靠前的子树越小,并且,同一个节点内,关键字按照大小排序;
  • B树的一个节点要求子树的个数等于关键字的个数+1;

好了,话不多说,看看B树的模型吧:

MySQL:从B树到B+树到索引再到存储引擎
一个五阶的B树

由于B树将所有的查找关键字都放在节点中,所以查找方式和二叉查找十分相像,比如说查找E:

先通过根节点找到了左子树,再顺序地遍历左子树,发现E在F和J的中间,于是查找叶子节点,顺序遍历关键字以后就可以返回E了,如果未能查到E,则表示没有找到。

B+树

人人都喜欢plus,B+树就是这么一个plus,后头所讲解的索引,就是用的B+树,我们先来看看他的特性吧:

  • B+树将所有的查找结果放在叶子节点中,这也就意味着查找B+树,就必须到叶子节点才能返回结果;
  • B+树每一个节点的关键字个数和子树指针个数相同;
  • B+树的非叶子节点的每一个关键字对应一个指针,而关键字则是子树的最大,或者最小值;

看看模型吧:

MySQL:从B树到B+树到索引再到存储引擎
一个3阶的B+树

他的查找方式也是简单粗暴的,和B树十分像,只不过他会在叶子节点中找到目标,比如我们找兔:

第一步比马小,就会查找他的子树,第二部比龙小,就会查找他的子树,最后在叶子节点中的关键字命中目标。

那么MySql是如何利用这数据结构的呢?

MySql中的两种常见存储引擎

MySql当然不止两种搜索引擎了,但是本次我们说的B+树索引,为接下来这两种存储引擎所用,一个是Innodb,一个Myisam。搜索公众号Java知音,回复“2021”,送你一份Java面试题宝典)

Innodb存储引擎

Innodb使用的是B+树,他存在有一个主键索引和辅助索引两种索引,主键索引是在生成主键时就有的索引,他的叶子节点中存放的就是数据行,所以又称之为聚集索引。

而另一类索引,辅助索引,就是我们人为新建的索引,他的叶子节点中存放的是主键,当我们通过辅助索引查找到主键之后,再通过查找的主键去查找主键索引,我们看看两种索引的结构吧:

MySQL:从B树到B+树到索引再到存储引擎
innodb主索引,其中叶子中存放的就是数据行
MySQL:从B树到B+树到索引再到存储引擎
innodb辅助索引,其中叶子存放的是主键

MyIsam存储引擎

很显然,MyIsam不可能再会用聚集索引了,虽然他用的是B+树,但是他的主键索引和辅助索引没有任何区别,都是在叶子中存储数据行的物理地址,这也使得他的读性能更高,我们来看他的模型吧:

MySQL:从B树到B+树到索引再到存储引擎
MyIsam存储引擎的主键索引
MySQL:从B树到B+树到索引再到存储引擎
MyIsam存储引擎的辅助索引,存放的同样是物理地址

区别

1、innodb支持事务,且默认是Autocommit,所以每一条SQL语句都会封装成一个事务,如果执行多条事务,最好加上begin和commit。MyIsam不支持事务,也就无法回滚;

2、另外Innodb支持行锁,MyIsam进行写操作会全表上锁,所以MyIsam的写操作性能会差些;

3、所以,在查询较多的表中,使用MyIsam较优,写比较多的表,使用Innodb;

拓展--复合索引

我们都知道我们可以对一个列创建一个索引,但是什么是复合索引呢?

创建:

create table test(
int,
int,
int,
KEY a(a,b,c)
);

通过以上代码我们就可以创建一个a、b、c三个字段的复合索引了,相对于维护三个索引,维护一个复合索引的开销肯定是更低的。

但是复合索引需要满足一个最左匹配原则,也就是他会依次查找a、b、c三个字段,当左边的字段未作为判断条件时,就不会再去执行接下来的索引了,测试如下:

EXPLAIN DELETE from test
where  a=1 and c= 3 and b =2 
MySQL:从B树到B+树到索引再到存储引擎
当a、b、c都有的时候,他会继续去匹配右边的字段
EXPLAIN DELETE from test
where  a=1 and c= 3 
MySQL:从B树到B+树到索引再到存储引擎
当去除b时,发现复合索引只匹配到a就结束了,并不会匹配c

推荐好文

强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

分享一套基于SpringBoot和Vue的企业级中后台开源项目,代码很规范!

能挣钱的,开源 SpringBoot 商城系统,功能超全,超漂亮MySQL:从B树到B+树到索引再到存储引擎

原文始发于微信公众号(Java笔记虾):MySQL:从B树到B+树到索引再到存储引擎