再有人问你为什么MySQL用B+树做索引，就把这篇文章发给她

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

利用聚集索引查找数据

还是这张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。

        从磁盘中读取页3后将页3放入内存中，然后进行查找，我们可以找到键值18，然后再拿到页3中的指针p1，定位到页8。

• 3. 同样的页8页不在内存中，我们需要再去磁盘中将页8读取到内存中。

        将页8读取到内存中后。

        因为页中的数据是链表进行连接的，而且键值是按照顺序存放的，此时可以根据二分查找法定位到键值18。

        此时因为已经到数据页了，此时我们已经找到一条满足条件的数据了，就是键值18对应的数据。

        因为是范围查找，而且此时所有的数据又都存在叶子节点，并且是有序排列的，那么我们就可以对页8中的键值依次进行遍历查找并匹配满足条件的数据。

        我们可以一直找到键值为22的数据，然后页8中就没有数据了，此时我们需要拿着页8中的p指针去读取页9中的数据。

• 4. 因为页9不在内存中，就又会加载页9到内存中，并通过和页8中一样的方式进行数据的查找，直到将页12加载到内存中，发现41大于40，此时不满足条件。

        那么查找到此终止。

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

(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条记录。

下面看下具体的查找流程图：

利用非聚集索引查找数据

读者看到这张图的时候可能会蒙，这是啥东西啊?怎么都是数字。

如果有这种感觉，请仔细看下图中红字的解释。什么?还看不懂?那我再来解释下吧。首先，这个非聚集索引表示的是用户幸运数字的索引(为什么是幸运数字?一时兴起想起来的:-))，此时表结构是这样的。

在叶子节点中，不在存储所有的数据了，存储的是键值和主键。

对于叶子节点中的x-y，比如1-1。左边的1表示的是索引的键值，右边的1表示的是主键值。如果我们要找到幸运数字为33的用户信息，对应的sql语句为select * from user where luckNum=33。

查找的流程跟聚集索引一样，这里就不详细介绍了。我们最终会找到主键值47，找到主键后我们需要再到聚集索引中查找具体对应的数据信息，此时又回到了聚集索引的查找流程。

下面看下具体的查找流程图：

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

总结

本篇文从二叉查找树，详细说明了为什么mysql用B+树作为数据的索引，以及在innodb中数据库如何通过B+树索引来存储数据以及查找数据。我们一定要记住这就话：数据即索引，索引即数据。

（编辑：西安站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!