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