本文主要是介绍MySQL为什么要使用B+树来实现数据库索引，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

本文讲解：MySQL为什么要用B+树来实现数据库索引？

1、二叉查找树

2、平衡二叉树

3、B树

4、B+树

5、聚簇索引 VS 非聚簇索引

5.1 聚簇索引

5.2 非聚簇索引

5.3 利用聚簇索引和非聚簇索引查找数据

5.3.1 利用聚簇索引查找数据

下面看下聚簇索引具体的查找流程图：

5.3.2 利用非聚簇索引查找数据

下面看下非聚簇索引具体的查找流程图：

6、总结

99、参考

本文讲解：MySQL为什么要用B+树来实现数据库索引？

索引这个词，相信大多数人已经相当熟悉了，很多人都知道MySQL数据库的索引主要以B+树为主，但是，要问到为什么要使用B+树来实现数据库索引，恐怕很少有人能够把前因后果完整的讲述出来。本文就从头到尾介绍一下MySQL数据库的索引。

索引，是一种数据结构，它的目的是帮助我们在大量数据中快速定位到我们想要查找的数据。 索引最形象的比喻就是图书的目录了。注意 这里的大量，数据量大了索引才显得有意义，如果我想要在[1,2,3,4] 中找到4这个数据，直接对全数据检索也很快，没有必要费力气构建索引再去查找。

索引在MySQL数据库中分为三类：B+树索引、Hash索引、全文索引。我们今天要介绍的是工作中最常接触到的InnoDB存储引擎中的的B+树索引。要介绍B+树索引，就不得不提 二叉查找树、平衡二叉树、B树 这三种数据结构，因为B+树就是从他们仨演化来的。请参考博客：https://blog.csdn.net/cmm0401/article/details/115715634

1、二叉查找树

首先，让我们先看一张图。

从图中可以看到：我们为user表（用户信息表）建立了一个二叉查找树的索引。图中的圆为二叉查找树的节点，节点中存储了键(key)和数据(data)。

在编程中我们使用SQL语句：alter table table_name add index index_name(column1, column2); 来创建数据库索引。

键对应user表中的id，数据对应user表中的行数据。二叉查找树的特点就是：任何节点的左孩子节点的键值都小于当前节点的键值，右孩子节点的键值都大于当前节点的键值。 顶端的节点我们称为根节点，没有子节点的节点我们称之为叶子节点，其余的节点称之为非叶子节点。

如果我们需要查找id=12的用户信息，利用我们创建的二叉查找树索引，查找流程大致如下：

（1）将根节点作为当前节点，把12与当前节点的键值10比较，12大于10，接下来我们把当前节点的右孩子节点作为当前节点。

（2）继续把12和当前节点的键值13作比较，发现12小于13，所在再把当前节点的左孩子节点作为当前节点。 

（3）把12和当前节点的键值12对比，12等于12，满足条件，所以，我们从当前节点中取出data，即id=12,name=xm 并且返回给客户端。

从上述中可以看到：利用二叉查找树这个数据结构，我们只需要进行 3次 查找即可找到目标数据。如果在表中一条一条的查找匹配的话，我们需要 6次 才能找到。

2、平衡二叉树

上面我们讲解了利用二叉查找树可以快速的找到目标数据。但是，如果上面的二叉查找树是一些这样的构造：

这个时候，可以看到我们的二叉查找树退化成了一个链表。如果我们需要查找 id=17 的用户信息，我们需要查找7次，也就相当于全表扫描了。 导致这个现象的原因其实是 二叉查找树变得不平衡了，也就是树的高度太高了，从而导致查找效率的大幅度下降，查找效率变得不稳定了。

为了解决这个问题，我们需要 保证二叉查找树一直保持平衡，此时就需要用到平衡二叉树了。注：平衡的意思，是指树的叶子节点都差不多深，有平衡之意。平衡二叉树，又称AVL树，在满足二叉查找树特性的基础上，要求 每个节点的左右子树的高度差不能超过1。

下面是平衡二叉树和非平衡二叉树的对比：

由平衡二叉树的构造，我们可以发现第一张图中的二叉树其实就是一棵平衡二叉树。平衡二叉树保证了树的构造是平衡的，当我们插入一个节点数据或者删除一个节点数据而导致不满足平衡二叉树的条件时，平衡二叉树就会进行调整树上的节点来保持平衡。具体的调整方式这里就不介绍了。相比于二叉查找树来说，平衡二叉树的查找效率更稳定，总体的查找速度也更快。

3、B树

因为内存的易失性，一般情况下，我们都会选择将user表中的数据和索引存储在磁盘这种外围设备中。但是，和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量 减少从磁盘中读取数据的次数。 另外，从磁盘中读取数据时，都是按照磁盘块来进行读取的，并不是采用一次IO 读取一条数据这样的读取策略。

如果我们能把尽量多的数据放进磁盘块中，那么，一次磁盘读取操作就会读取更多数据，我们查找数据的时间也会大幅度降低。 如果我们用树这种数据结构作为索引的数据结构，那么，我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块，我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那这能说明什么呢？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量数据呢？可以想象到：平衡二叉树的节点将会非常多，高度也会非常高，我们查找数据时也会进行很多次磁盘IO，我们查找数据的效率将会大幅度降低！

为了解决平衡二叉树的这个弊端，我们应该寻找一种 单个节点就可以存储多个键值和数据的平衡树。也就是我们接下来要说的B树。 B树（Balance Tree），即为平衡树的意思，下图即是一颗B树。

上图中的p节点为指向子节点的指针，二叉查找树和平衡二叉树其实也有，因为图的美观性，被省略了。图中的每个节点称为页，页就是我们上面说的磁盘块，在MySQL中，数据读取的基本单位都是页，所以我们这里叫做页更符合MySQL中索引的底层数据结构。

从上图可以看出：B树相对于平衡二叉树，每个节点存储了更多的键值(key)和数据(data)，并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的B树为3阶B树，高度也会低很多。基于这个特性，B树查找数据读取磁盘的次数将会减少很多，数据的查找效率也会比平衡二叉树高很多。 

假如我们要查找id=28的用户信息，那么我们在上图B树中查找的流程如下：

（1）先找到根节点也就是找到页1，判断28在键值17和35之间，那么我们根据页1中的指针p2找到页3。 

（2）将28和页3中的键值相比较，28在26和30之间，我们根据页3中的指针p2找到页8。 

（3）将28和页8中的键值相比较，发现有匹配的键值28，键值28对应的用户信息为(28,bv)，返回即可。

4、B+树

B+树是对B树的进一步优化。让我们先来看下B+树的结构图：

根据上图，我们来看下B+树和B树有什么不同。 

（1）B+树的非叶子节点上是不存储数据的，仅存储键值；而B树的节点中不仅存储键值，也会存储数据。之所以这么做，是因为在数据库中页的大小是固定的，InnoDB中页的默认大小是16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（即：节点的子节点数）就会更大，整个树就会更矮、更胖，如此一来，我们查找数据进行磁盘IO的次数就会再次减少，数据查找的效率也会更高。

另外，B+树的阶数是等于键值的数量的。如果我们的B+树一个节点可以存储1000个键值，那么3层的B+树就可以存储1000×1000×1000=10亿个数据。一般，根节点是常驻内存的，所以，一般我们查找10亿数据，只需要2次磁盘IO就可以了，效率非常高。 

（2）B+树索引的所有数据均存储在叶子节点，而且数据是按照大小顺序排列的。所以，B+树使得范围查找、排序查找、分组查找、去重查找 等变得非常简单。而B树因为数据分散在各个节点，要实现这一点是很不容易的。  

有心的读者可能还发现上图B+树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。

其实上面的B树我们也可以对各个节点加上链表。其实这些不是它们之前的区别，是因为在mysql的innodb存储引擎中，索引就是这样存储的。也就是说上图中的B+树索引就是innodb中B+树索引真正的实现方式，准确的说应该是聚集索引（聚集索引和非聚集索引下面会讲到）。

通过上图可以看到，在InnoDB中，我们通过数据页之间通过双向链表连接，叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。

MyISAM中的B+树索引实现与InnoDB中的略有不同。在MyISAM中，B+树索引的叶子节点并不存储数据，而是存储数据的文件地址。

5、聚簇索引 VS 非聚簇索引

在上节介绍B+树索引的时候，我们提到了图中的索引其实是聚簇索引的实现方式。那什么是聚簇索引呢？在MySQL中，B+树索引按照存储方式的不同分为聚簇索引和非聚簇索引。这里我们着重介绍InnoDB中的聚簇索引和非聚簇索引。

5.1 聚簇索引

以InnoDB作为存储引擎的表，表中的数据都会有一个主键，即使你不创建主键，系统也会帮你创建一个隐式的主键rowID。这是因为 InnoDB是把数据存放在B+树中的，而B+树的键值就是主键，B+树的叶子节点中存储了表中所有的数据。这种 以主键作为B+树索引的键值而构建的B+树索引，我们称之为聚簇索引。 换言之，在B+树中，叶子节点存储整条记录的数据，这样的索引结构为聚簇索引。

5.2 非聚簇索引

以主键以外的列值作为键值构建的B+树索引，我们称之为非聚簇索引。

非聚簇索引与聚簇索引的区别在于：非聚簇索引的叶子节点不存储表中的数据，而是存储该列对应的主键，想要查找数据，我们还需要根据主键再去聚簇索引中进行查找，这个再根据聚簇索引查找数据的过程，我们称为回表。

明白了聚簇索引和非聚簇索引的定义，我们应该明白这样一句话：数据即索引，索引即数据。

5.3 利用聚簇索引和非聚簇索引查找数据

前面我们讲解B+树索引的时候，并没有去说怎么在B+树中进行数据的查找，主要就是因为还没有引出聚簇索引和非聚簇索引的概念。下面，我们讲解如何通过聚簇索引以及非聚簇索引来查找数据表中数据的方法。

5.3.1 利用聚簇索引查找数据

还是这张B+树索引图，现在我们应该知道这就是聚簇索引，表中的数据存储在叶子节点中。现在，假设我们要查找 id>=18并且 id<40 的用户数据。对应的SQL语句为：select * from user where id>=18 and id <40，其中id为主键。具体的查找过程如下：

（1）一般，根节点都是常驻内存的，也就是说页1已经在内存中了，此时不需要到磁盘中读取数据，直接从内存中读取即可。    从内存中读取到页1，要查找这个 id>=18 and id <40 或者范围值，我们首先需要找到 id=18 的键值。    从页1中我们可以找到键值18，此时我们需要根据指针p2，定位到页3。

（2）要从页3中查找数据，我们就需要拿着p2指针去磁盘中进行读取页3（此时进行第一次磁盘IO）。    从磁盘中读取页3后，将页3放入内存中，然后再进行查找，我们可以找到键值18，然后再拿到页3中的指针p1，定位到页8。

（3）同样的，页8页不在内存中，我们需要再去磁盘中将页8读取到内存中（此时进行第二次磁盘IO）。    将页8读取到内存中后，因为页中的数据是链表进行连接的，而且键值是按照顺序存放的，此时可以根据二分查找法定位到键值18。    此时，因为已经到数据页了，我们也已经找到一条满足条件的数据了，就是键值18对应的数据。    因为是范围查找，而且此时所有的数据又都存在叶子节点上，并且是有序排列的，那么我们就可以对页8中的键值依次进行遍历，查找出满足条件的数据。    我们可以一直找到键值为22的数据，然后页8中就没有数据了，此时我们需要拿着页8中的p指针去读取页9中的数据。

（4）因为页9不在内存中，就又会加载页9到内存中（此时进行第三次磁盘IO），并通过和页8中一样的方式进行数据的查找，直到将页12加载到内存中（此时进行第六次磁盘IO），发现41大于40，此时不满足条件，那么查找到此终止。

（5）最终，我们找到满足条件的所有数据为：

(18,kl), (19,kl), (22,hj), (24,io), (25,vg), (29,jk), (31,jk), (33,rt), (34,ty), (35,yu), (37,rt), (39,rt)， 总共12条记录。

下面看下聚簇索引具体的查找流程图：

5.3.2 利用非聚簇索引查找数据

看到这张图的时候可能会蒙，这是啥东西啊？怎么都是数字。如果有这种感觉，请仔细看下 图中红字的解释。还看不懂？那我再来解释下吧。首先，这个非聚簇索引表示的是用户幸运数字的索引，此时表结构是这样的。

在叶子节点中，不再存储所有的数据了，存储的是键值和主键。对于叶子节点中的 x-y，比如 1-1，左边的1表示的是索引的键值，右边的1表示的是主键值。如果我们要找到幸运数字为33的用户信息，对应的sql语句为 select * from user where luckNum=33。查找的流程跟聚簇索引一样，这里就不详细介绍了。我们最终会找到主键值47，找到主键后，我们需要根据主键47再到聚簇索引中查找对应的具体的真实数据信息，此时又回到了聚簇索引的查找流程。  

下面看下非聚簇索引具体的查找流程图：

另外：在MyISAM中，聚簇索引和非聚簇索引的叶子节点都会存储数据的文件地址。

6、总结

本文从二叉查找树、平衡二叉树、B树、B+树的结构图和优缺点，详细说明了为什么MySQL中要使用B+树来作为数据的索引，以及在InnoDB中数据库是如何通过B+树索引来存储数据以及查找数据的。我们一定要记住这句话：数据即索引，索引即数据。

99、参考

（1）https://blog.csdn.net/cmm0401/article/details/115715634

（2）https://www.jianshu.com/p/6f69cd528453

（3）https://www.jianshu.com/p/75735c7b2f79

（4）https://www.jianshu.com/p/e916bb755608

这篇关于MySQL为什么要使用B+树来实现数据库索引的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！