Index，相信大多数人都比较熟悉。很多人都知道MySQL的索引主要是基于B+树的，但是问到为什么要用B+树，恐怕很少有人能说清楚前因后果。本文将从头到尾介绍数据库的索引。ImagefromPexelsindex是一种数据结构，用来帮助我们在海量数据中快速定位到我们要查找的数据。索引最生动的比喻是书籍目录。注意这里的量大。当数据量很大时索引才有意义。如果我要在[1,2,3,4]中查找4的数据，直接全量取数据也是非常快的，不用费力建索引。再去找吧。MySQL数据库中的索引分为三种：B+树索引哈希索引全文索引今天要介绍的是工作开发中最常遇到的InnoDB存储引擎中的B+树索引。介绍B+树索引，就不得不提到二叉搜索树，它平衡了二叉树和B树三种数据结构。B+树就是由他们三者演化而来的。二叉搜索树首先我们来看一张图：从图中可以看出，我们为用户表（用户信息表）创建了一个二叉搜索树索引。图中的圆圈是二叉搜索树的节点，节点中存放着键（key）和数据（data）。key对应用户表中的id，data对应用户表中的行数据。二叉搜索树的特点是任意节点的左子节点的键值都小于当前节点的键值，右子节点的键值大于当前节点的键值.顶部的节点称为根节点，没有子节点的节点称为叶节点。如果我们需要查找id=12的用户信息，使用我们创建的二叉查找树索引，查找过程如下：以根节点为当前节点，将12与当前节点的键值10进行比较，12大于10，那么我们将当前节点的右子节点>作为当前节点。继续比较12和当前节点的键值13，发现12小于13，则取当前节点的左子节点为当前节点。比较12和当前节点的键值12，12等于12，满足条件，我们从当前节点中取出数据，即id=12，name=xm。使用二叉搜索树我们只需要3次就可以找到匹配的数据。如果我们在表中一一查找，需要6次才能找到。BalancedBinaryTree上面我们讲解了使用二叉搜索树可以快速找到数据。但是，如果上面的二叉搜索树是这样构造的：这个时候我们可以看到我们的二叉搜索树已经变成了一个链表。如果我们要查找id=17的用户信息，需要查找7次，相当于全表扫描。出现这种现象的原因是二叉搜索树变得不平衡，即高度过高，导致搜索效率不稳定。为了解决这个问题，我们需要保证二叉搜索树始终是平衡的，所以我们需要使用平衡二叉树。平衡二叉树也称为AVL树。在满足二叉搜索树特性的基础上，要求每个节点的左右子树的高度差不能超过1。下面是平衡二叉树和非平衡二叉树的对比：来自平衡二叉树的构建，我们可以发现第一张图中的二叉树其实就是平衡二叉树。平衡二叉树保证了树的结构是平衡的。当我们插入或删除数据导致不平衡二叉树不平衡时，平衡二叉树会调整树上的节点来保持平衡。具体的调整方法这里就不介绍了。与二叉搜索树相比，平衡二叉树的搜索效率更稳定，整体搜索速度更快。B树是因为内存的易失性。一般情况下，我们会选择将user表中的数据和索引存放在磁盘等外围设备中。但是和内存相比，从磁盘读取数据的速度会慢几百倍、几千倍甚至一万倍，所以我们应该尽量减少从磁盘读取数据的次数。另外，从磁盘读取数据时，是按照磁盘块读取的，而不是一个一个的读取。如果我们能把尽可能多的数据放到磁盘块中，那么一次磁盘读操作就会读到更多的数据，我们查找数据的时间也会大大减少。如果我们使用树状数据结构作为索引数据结构，那么每次查找数据都需要从磁盘中读取一个节点，也就是我们所说的磁盘块。我们都知道平衡二叉树每个节点只存储一个键值和数据。这意味着什么？也就是说每个磁盘块只存储一个键值和数据！如果我们要存储海量数据怎么办？可想而知，二叉树的结点会非常多，高度会极高。我们在查找数据的时候，也会进行很多的磁盘IO，那么我们查找数据的效率就会极低！为了解决平衡二叉树的这个缺点，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的B树。B-tree（BalanceTree）的意思是平衡树。下图是B树：图中的p节点是指向子节点的指针。其实还有二叉搜索树和平衡二叉树。因图美，从略。图中的每个节点称为页，页就是我们上面提到的磁盘块。MySQL读取数据的基本单位是页，所以我们这里所说的页更符合MySQL中索引的底层数据结构。从上图可以看出，与平衡二叉树相比，B树的每个节点存储了更多的键值（key）和数据（data），并且每个节点都有更多的子节点，子节点的数量nodes一般被称为order，而上图中的B-tree是3阶B-tree，它的高度会很低。基于这个特点，B树查找数据和读磁盘的次数会非常少，数据查找效率会比平衡二叉树高很多。如果我们要查找id=28的用户信息，那么我们在上面B树中的查找过程是这样的：首先找到根节点，也就是第1页，判断28在键值17和35之间，然后我们根据第1页的指针p2找到第3页。将28与第3页中的键值进行比较，28在26和30之间，根据第3页中的指针p2找到第8页。将28与中的键值进行比较页面8，发现有匹配的键值28，键值28对应的用户信息为(28,bv)。B+树B+树是B树的进一步优化。先来看看B+树的结构图：根据上图，我们看看B+树和B树的区别：①B+树的非叶子节点不存储数据，只存储键值是存储的，而B树的节点不仅存储键值，还存储数据。这样做的原因是数据库中的页面大小是固定的，InnoDB中默认的页面大小是16KB。如果没有存储数据，则存储更多的key值，对应的树（该节点的子节点树）的阶数会更大，树会更短更胖，这样我们就可以搜索数据在磁盘上的IO次数会再次减少，数据查询的效率会更快。另外，B+树的阶数等于键值的个数。如果我们B+树的一个节点可以存储1000个键值，那么3层B+树可以存储1000×1000×1000=10亿个数据。一般根节点常驻内存，所以一般我们只需要2次磁盘IO就可以搜索10亿条数据。②因为B+树索引的所有数据都存放在叶子节点中，而且数据是有序排列的。那么B+树使得范围搜索、排序搜索、分组搜索和去重搜索变得异常简单。但是由于B-tree的数据是分散在各个节点中的，所以实现起来并不容易。有兴趣的读者可能还会发现，上图中B+树中的页面是通过双向链表连接的，而叶子节点中的数据是通过单向链表连接的。其实我们也可以给上面B树的每个节点加上一个链表。这些与以前不同，因为在MySQL的InnoDB存储引擎中，索引是以这种方式存储的。也就是说，上图中的B+树索引是B+树索引在InnoDB中的真正实现。准确的说应该是聚簇索引（聚簇索引和非聚簇索引下面会讲到）。从上图可以看出，在InnoDB中，我们通过双向链表连接数据页，通过单向链表连接叶子节点中的数据，就可以找到表中的所有数据。MyISAM中的B+树索引实现与InnoDB中略有不同。在MyISAM中，B+树索引的叶子节点不存储数据，而是存储数据的文件地址。聚簇索引VS非聚簇索引在上一节介绍B+树索引的时候，我们提到图中的索引其实就是聚簇索引的实现。那么什么是聚簇索引呢？在MySQL中，B+树索引根据存储方式分为聚簇索引和非聚簇索引。这里重点介绍InnoDB中的聚簇索引和非聚簇索引：①聚簇索引（clusteredindex）：对于以InnoDB作为存储引擎的表，表中的数据都会有一个主键。即使您不创建主键，系统也会帮助您创建隐式主键。这是因为InnoDB将数据存储在B+树中，而B+树的键值就是主键。在B+树的叶子节点中，存储了表中的所有数据。这种以主键作为B+树索引的键值构建的B+树索引称为聚簇索引。②非聚集索引（non-clusteredindex）：以主键以外的列值作为键值构造的B+树索引，我们称之为非聚集索引。非聚集索引和聚集索引的区别在于，非聚集索引的叶子节点不存储表中的数据，而是存储列对应的主键。要查找数据，我们需要根据主键在聚簇索引中进行查找。根据聚簇索引查找数据的过程回调到表中。了解了聚簇索引和非聚簇索引的定义后，我们应该明白这句话：数据就是索引，索引就是数据。使用聚簇索引和非聚簇索引查找数据我们在讲解B+树索引的时候，并没有讲到如何在B+树中查找数据，主要是聚簇索引和非聚簇索引的概念还没有弄清楚介绍。下面我们通过讲解如何通过聚簇索引和非聚簇索引在数据表中查找数据，来介绍如何在B+树索引中查找数据。使用聚簇索引查找数据还是这张B+树索引图。现在我们应该知道，这就是聚簇索引，表中的数据就存放在里面。现在假设我们要查找id>=18且id<40的用户数据。对应的sql语句为：select*fromuserwhereid>=18andid<40其中id为主键，具体查找过程如下：①一般情况下，根节点常驻内存，也就是说第1页已经在内存，不需要从磁盘读取数据，直接从内存中读取即可。从内存中读取第1页，要找到这个id>=18和id<40或者范围值，我们首先需要找到id=18的键值。从第1页可以找到键值18，此时需要根据指针p2定位到第3页。②从第3页开始查找数据，需要将p2指针指向磁盘，读取第3页。从磁盘读取第3页后，将第3页放入内存，然后查找，可以找到键值18，并且然后获取page3中的指针p1定位到page8。③同一个page8不在内存中，我们需要去磁盘中将page8读入内存。在第8页被读入内存后。因为页面中的数据是用链表连接的，键值是有序存储的，这时候根据二分查找的方法就可以定位到键值18。这个时候因为已经到了数据页，所以找到了符合条件的数据，就是key值18对应的数据。因为是范围搜索，而这个时候所有的数据都有叶子节点并有序排列，那么我们就可以遍历第8页的key值，找到并匹配满足条件的数据。我们总能找到key值为22的数据，然后第8页就没有数据了，这时候就需要拿第8页的p指针去读取第9页的数据。④因为第9页不在内存，9页再次加载内存，和8页一样查找数据，直到12页加载内存，发现41大于40，此时不满足时间条件。那么搜索到此结束。最后我们找到所有满足条件的数据，一共12条记录：(18,kl),(19,kl),(22,hj),(24,io),(25,vg),(29,jk),(31,jk),(33,rt),(34,ty),(35,yu),(37,rt),(39,rt)。下面看具体的查找流程图：使用非聚集索引查找数据。读者看到这张图可能会一头雾水。这是什么？为什么都是数字。如果你有这种感觉，请仔细阅读下图中红色部分的解释。什么？还是不明白？让我再解释一下。首先，这个非聚集索引代表的是用户幸运数字的索引（为什么是幸运数字呢，心血来潮想起来:-)），表结构是这样的。在叶节点中，不再存储所有数据，而是存储键值和主键。对于叶子节点中的x-y，比如1-1。左边的1代表索引的键值，右边的1代表主键值。如果我们要查找幸运数字为33的用户信息，对应的sql语句为：select*fromuserwhereluckNum=33查找过程与聚簇索引相同，这里不再详细介绍。我们最终会找到主键值47，找到主键后，我们需要在聚簇索引中找到具体对应的数据信息，然后再回到聚簇索引的查找过程。我们来看具体的查找流程图：在MyISAM中，无论是聚簇索引还是非聚簇索引，其叶子节点都会存放数据的文件地址。从二叉搜索树来总结这篇文章，详细解释了为什么MySQL使用B+树作为数据的索引，以及数据库如何使用B+树索引来存储数据和在InnoDB中查找数据。我们一定要记住这句话：数据就是索引，索引就是数据。参考资料：《MySQL 必知必会》《MySQL 技术内幕 InnoDB 存储引擎第2版》https://www.cnblogs.com/vianzhang/p/7922426.htmlhttp://blog.codinglabs.org/articles/theory-of-mysql-index.html
