一文说清楚Mysql Innodb的B+树索引原理及其推理过程

为什么要写这篇文章

网上找了很多关于Innodb B+树索引原理的文章，但都不尽如意。基本都是列出了最后的结果，没有说清楚B+树的推理过程，让人看的云里雾里。本文会由浅入深的讲解B+树的推理过程，毕竟，知其然才能知其所以然。

在这里插入图片描述

正文：B+树索引原理及其推理过程

我们先来看一张t表表结构，其中字段a为主键

create table t
(
    a int         not null
        primary key,
    b int         null,
    c int         null,
    d int         null,
    e varchar(20) null
);

插入一些数据

insert into t values (1,1,1,1,'a');
insert into t values (2,1,1,2,'b');
insert into t values (5,1,2,2,'e');
insert into t values (6,1,2,1,'f');
insert into t values (3,1,2,1,'c');
insert into t values (7,2,1,2,'g');
insert into t values (9,2,2,2,'i');
insert into t values (8,2,2,1,'h');
insert into t values (4,2,1,1,'d');

查询

在这里插入图片描述

注意看查询出来表的数据，数据的顺序居然不是按照我插入的顺序来的，而是按照主键的顺序进行了排序。

问题一：我们知道排序肯定会影响插入的性能，为什么mysql要排序插入？

估计你猜到答案了，排序虽然影响插入的性能，但会增加查询的性能，我们来思考一下，当我们执行如下的SQL时，Mysql的执行过程是怎样的呢？

select * from t where a = 5

对于这样一条sql，mysql的执行过程是怎样的呢？我们先来猜测

1. 从磁盘取出表第1条数据判断a是否等于5
2. 从磁盘取出表第2条数据判断a是否等于5
3. .....
4. 从磁盘取出表第5条数据判断a是否等于5
5. 从磁盘取出表第6条数据判断a是否等于5

由于数据库数据是已经排序好的，那么当mysql知道了第6条数据是a是6时，第6条数据a的值比a大，说明第6条以后的所有的值都比a大，就不需要需要往下找了，增加了查询性能。

问题二：对于上诉查询语句一共有几次IO，有没有什么优化的办法？

可以算出来总共去磁盘取数据取了6次，所以有6次IO，有没有什么优化的办法呢？

是否可以一次取的时候多取几条数据，比如我一次取把t表的9条数据全部取到内存中，然后从内存中取出来数据判断，这样只用一次IO就解决问题了。事实上，Mysql确实是这么做的，Mysql取数据的时候并不会以单条数据为单位从磁盘读取，而是以页（Page）为单位。在操作系统中页的定义如下，而在Mysql中也类似，只是操作系统中的一页为4KB，而Mysql中一页为16KB。

页的概念

考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。

问题三：是否还能再优化一下吗？

现在，我们解决了多次磁盘IO的问题，但是我们取9条数据到内存里面去，我还是要对内存中这9条数据进行最少6次是否等于5的判断，我才能找到a=5的那条数据，那么有没有什么更好的优化的办法呢？你肯定猜到了，用二叉树或者红黑树嘛~，篇幅所限，二叉树这部分知识点不过多介绍了，可以看我的Java数据结构-TreeMap这篇文章。

问题四：数据量太大了怎办？

现在，我们通过页解决了磁盘IO的问题，通过二叉树解决了每一页中的数据查询性能低下的问题。但你有没有想过，一页只有16kb，我们上诉表只有9条数据，所以一页就可以全部取出来，但是假设我这张表有一千条数据呢？一万条数据呢？十万条呢？我们假设10条数据的大小为16kb，也就是说10条数据刚好组成一页，那么1000条数据就会被分成100页

1. 第1页：a 1-10
2. 第2页：a 11-20
3. .......
4. 第100页：a 991-1000

这个时候如果我要找a=759这条数据，想想我们要进行多少次IO？每一页一次，759应该是76次，第76次IO，我们终于找到a为751-760这页数据，然后找到了759这条数据。

是不是太累了？还有没有什么办法优化一下呢？我们来想象一下，给你一本1000页的书，需要你找到第759页，你会怎么找？

1. 先随手一翻，看看这一页是多少页，如果这一页小于759，那么接着往后翻，如果大于759，那么往前翻
2. 我们可以把书每100页插入一个书签，那么现在比如我要找759页，很明显，我只要找到第七个书签，然后往后找很快就能找到759页。

很明显，对于程序来说，更适合采用书签的方式，因为程序并不知道我们的随手一翻到底是什么意思。给定书签，程序就能遍历书签，然后用当前书签页的值与我们的759比较，如果小于就继续找下一个书签比较，直到找到大于759的书签，那么说明759就在前面这100页里面。用数据结构表示如下

在这里插入图片描述

上层中存储了书签的页码值和当前书签所对应的书中的位置（指针）

当我们要找759这条数据的时候，我们直接找到上层结构中的701即可找到下层中701所在页的磁盘地址，通过这个地址就可以找到759，我们不需要去看701以前的页，那些页里面不可能存在我们要的759这条数据，所以可以加快检索效率。

其实这就是B+tree的原理

什么是聚簇索引和非聚簇索引

聚簇索引：将数据存储与索引放到了一块，索引结构的叶子节点保存了行数据

非聚簇索引：将数据与索引分开存储，索引结构的叶子节点指向了数据对应的位置

那么对于上诉的主键索引，由于叶子节点保存的是行的数据，所以很明显是属于聚簇索引。

而如果存储引擎不是Innodb而是MyISAM的话，他的叶子节点存储的不是表数据，而是所在行的指针。

在这里插入图片描述

所以MyISAM的主键索引数是非聚簇索引。

什么是二级索引？

我们上诉讲的都是主键索引，但其实还可以创建联合索引。

对t表我们创建一个bcd联合索引

create index t1_lh on t(b,c,d);

在这里插入图片描述

那么这个时候我们的索引结构是怎样的呢？

在这里插入图片描述

这个结构对于如下查询语句是可以走索引查询的

select * from t where b=1 and c=2 and d=1 

在这里插入图片描述

而对于如下是需要走全表扫描的

select * from t where and c=2 and d=1 

在这里插入图片描述

这也就是所说的最左前缀原则。

在Innodb中，联合索引与主键索引不同的是，叶子节点存储的不是表中的所有数据，而是索引列的数据和主键的值。为什么要存储主键值呢？

对于上诉例子，我们是select *而非select b,c,d，但我们的索引中只是存储了联合索引列的值，也就是b,c,d的值，我们如和找到这一行所有列的值呢？这个时候主键就派上用场了，找到这个叶子节点的值之后，会拿对应的主键值去走主键索引再查询一遍，这也就是所说的回表。

为了区别于主键索引，人们把这种叶子节点不存储表数据的索引叫做二级索引或辅助索引，由于这种索引叶子节点存储的也是主键的值而非指针，所以Innodb中的二级索引也是聚簇索引，MyISAM的二级索引与主键索引类似，都是存储行指针，所以也是非聚簇索引。

写在最后

上诉只是为了便于理解列出了B+索引的基本原理，但其实B+索引的实现会比这个要复杂一点，比如真正的B+树页与页之间是存在prev，next指针的。好像又有人叫B*索引把，我也没搞懂，欢迎补充。