概念B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别
规则（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；（2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；（）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。（4）非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql的B+树是用第一种方式实现）;
B+树是对B树的进一步优化。让我们先来看下B+树的结构图：
根据上图我们来看下B+树和B树有什么不同：
①B+树非叶子节点上是不存储数据的，仅存储键值，而B树节点中不仅存储键值，也会存储数据。
之所以这么做是因为在数据库中页的大小是固定的，InnoDB中页的默认大小是16KB。
如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数又会再次减少，数据查询的效率也会更快。
另外，B+树的阶数是等于键值的数量的，如果我们的B+树一个节点可以存储个键值，那么层B+树可以存储××=10亿个数据。
一般根节点是常驻内存的，所以一般我们查找10亿数据，只需要2次磁盘IO。
②因为B+树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。
那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点，要实现这一点是很不容易的。
有心的读者可能还发现上图B+树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。
其实上面的B树我们也可以对各个节点加上链表。这些不是它们之前的区别，是因为在MySQL的InnoDB存储引擎中，索引就是这样存储的。
也就是说上图中的B+树索引就是InnoDB中B+树索引真正的实现方式，准确的说应该是聚集索引（聚集索引和非聚集索引下面会讲到）。
通过上图可以看到，在InnoDB中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。
MyISAM中的B+树索引实现与InnoDB中的略有不同。在MyISAM中，B+树索引的叶子节点并不存储数据，而是存储数据的文件地址。
聚集索引VS非聚集索引在上节介绍B+树索引的时候，我们提到了图中的索引其实是聚集索引的实现方式。
那什么是聚集索引呢？在MySQL中，B+树索引按照存储方式的不同分为聚集索引和非聚集索引。
这里我们着重介绍InnoDB中的聚集索引和非聚集索引：
①聚集索引（聚簇索引）：以InnoDB作为存储引擎的表，表中的数据都会有一个主键，即使你不创建主键，系统也会帮你创建一个隐式的主键。
这是因为InnoDB是把数据存放在B+树中的，而B+树的键值就是主键，在B+树的叶子节点中，存储了表中所有的数据。
这种以主键作为B+树索引的键值而构建的B+树索引，我们称之为聚集索引。
②非聚集索引（非聚簇索引）：以主键以外的列值作为键值构建的B+树索引，我们称之为非聚集索引。
非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。
明白了聚集索引和非聚集索引的定义，我们应该明白这样一句话：数据即索引，索引即数据。
利用聚集索引和非聚集索引查找数据前面我们讲解B+树索引的时候并没有去说怎么在B+树中进行数据的查找，主要就是因为还没有引出聚集索引和非聚集索引的概念。
下面我们通过讲解如何通过聚集索引以及非聚集索引查找数据表中数据的方式介绍一下B+树索引查找数据方法。
利用聚集索引查找数据还是这张B+树索引图，现在我们应该知道这就是聚集索引，表中的数据存储在其中。现在假设我们要查找id=18并且id40的用户数据。对应的sql语句为：
MySQL
1
select*fromuserwhereid=18andid40
其中id为主键，具体的查找过程如下：
①一般根节点都是常驻内存的，也就是说页1已经在内存中了，此时不需要到磁盘中读取数据，直接从内存中读取即可。
从内存中读取到页1，要查找这个id=18andid40或者范围值，我们首先需要找到id=18的键值。
从页1中我们可以找到键值18，此时我们需要根据指针p2，定位到页。
②要从页中查找数据，我们就需要拿着p2指针去磁盘中进行读取页。
从磁盘中读取页后将页放入内存中，然后进行查找，我们可以找到键值18，然后再拿到页中的指针p1，定位到页8。
③同样的页8页不在内存中，我们需要再去磁盘中将页8读取到内存中。
将页8读取到内存中后。因为页中的数据是链表进行连接的，而且键值是按照顺序存放的，此时可以根据二分查找法定位到键值18。
此时因为已经到数据页了，此时我们已经找到一条满足条件的数据了，就是键值18对应的数据。
因为是范围查找，而且此时所有的数据又都存在叶子节点，并且是有序排列的，那么我们就可以对页8中的键值依次进行遍历查找并匹配满足条件的数据。
我们可以一直找到键值为22的数据，然后页8中就没有数据了，此时我们需要拿着页8中的p指针去读取页9中的数据。
④因为页9不在内存中，就又会加载页9到内存中，并通过和页8中一样的方式进行数据的查找，直到将页12加载到内存中，发现41大于40，此时不满足条件。那么查找到此终止。
最终我们找到满足条件的所有数据，总共12条记录：
(18,kl),(19,kl),(22,hj),(24,io),(25,vg),(29,jk),(1,jk),(,rt),(4,ty),(5,yu),(7,rt),(9,rt)。
下面看下具体的查找流程图
利用非聚集索引查找数据读者看到这张图的时候可能会蒙，这是啥东西啊？怎么都是数字。如果有这种感觉，请仔细看下图中红字的解释。什么？还看不懂？那我再来解释下吧。首先，这个非聚集索引表示的是用户幸运数字的索引（为什么是幸运数字？一时兴起想起来的:-)），此时表结构是这样的。
在叶子节点中，不再存储所有的数据了，存储的是键值和主键。对于叶子节点中的x-y，比如1-1。左边的1表示的是索引的键值，右边的1表示的是主键值。
如果我们要找到幸运数字为的用户信息，对应的sql语句为：
MySQL
1
select*fromuserwhereluckNum=
查找的流程跟聚集索引一样，这里就不详细介绍了。我们最终会找到主键值47，找到主键后我们需要再到聚集索引中查找具体对应的数据信息，此时又回到了聚集索引的查找流程。
下面看下具体的查找流程图：
在MyISAM中，聚集索引和非聚集索引的叶子节点都会存储数据的文件地址。
总结本篇文章从二叉查找树，详细说明了为什么MySQL用B+树作为数据的索引，以及在InnoDB中数据库如何通过B+树索引来存储数据以及查找数据。我们一定要记住这句话：数据即索引，索引即数据。一起写程序，每天都有收获，谢谢