MySQL：从B树到B+树到索引再到存储引擎，来说说

> 公众号：[Java小咖秀](https://t.1yb.co/jwkk)，网站：[javaxks.com](https://www.javaxks.com)

> 作者：that_is_cool , 链接: blog.csdn.net/that_is_cool/article/details/81069945

学习 Java 也有一年多了，但是从来没有就数据库做一个完整的总结，心血来潮立了这么一个网文标题，希望不要虎头蛇尾吧，哈哈。

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

B 树和 B + 树

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

B 树：B 树就是 B - 树，他有着如下的特性：

1、B 树不同于二叉树，他们的一个节点可以存储多个关键字和多个子树指针，这也是 B + 树的特点；

2、一个 m 阶的 B 树要求除了根节点以外，所有的非叶子子节点必须要有 [m/2,m] 个子树；

3、根节点必须只能有两个子树，当然，如果只有根节点一个节点的情况存在；

4、B 树是一个查找二叉树，这点和二叉查找树很像，他都是越靠前的子树越小，并且，同一个节点内，关键字按照大小排序；

5、B 树的一个节点要求子树的个数等于关键字的个数 + 1；

好了，话不多说，看看 B 树的模型吧：

img

一个五阶的 B 树

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

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

B + 树

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

1、B + 树将所有的查找结果放在叶子节点中，这也就意味着查找 B + 树，就必须到叶子节点才能返回结果；

2、B + 树每一个节点的关键字个数和子树指针个数相同；

3、B + 树的非叶子节点的每一个关键字对应一个指针，而关键字则是子树的最大，或者最小值；

看看模型吧：

img

一个 3 阶的 B + 树

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

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

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

MySql 中的两种常见存储引擎

MySql 当然不止两种搜索引擎了，但是本次我们说的 B + 树索引，为接下来这两种存储引擎所用，一个是 Innodb，一个 Myisam。

Innodb 存储引擎

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

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

img

innodb 主索引，其中叶子中存放的就是数据行

img

innodb 辅助索引，其中叶子存放的是主键

MyIsam 存储引擎

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

img

MyIsam 存储引擎的主键索引

img

MyIsam 存储引擎的辅助索引，存放的同样是物理地址

区别

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

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

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

拓展 -- 复合索引

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

创建：

create table test(
a int,
b int,
c 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 

img

当 a、b、c 都有的时候，他会继续去匹配右边的字段

EXPLAIN DELETE from test
where  a=1 and c= 3 

img

当去除 b 时，发现复合索引只匹配到 a 就结束了，并不会匹配 c