分享总结本次在儒猿专栏《从零开始带你成为MySQL实战优化高手》分享Mysql索引的内容。本次将从如何在一个数据页存储和查询数据开始，扩展到在多个数据页查询数据，分析非索引查询效率低下，再过渡到主键目录和索引页相关内容通过分页。见证一棵索引树是如何一步步成长起来的。最后，我们从更高的角度来看一些常用的索引术语，索引的优缺点，以及如何设计更好的索引。在开始分析之前，我们先思考一下以下面试题：1.InnoDB的索引数据是什么结构？为什么要用这个数据结构？2.聚簇索引和普通索引有什么区别？3、什么是退货操作？对指数有影响吗？Mysql索引的B+树的生长过程如下图所示：2、B+索引树是如何生长的？是的，首先我们要弄清楚数据是如何存储的。通过上一篇文章，数据页的结构大致是这样的：数据表中的每一行数据都存储在数据区中，数据区中的每一行数据通过指针以一一的形式连接起来——路链表，如下图：同时将各个数据页以双向链表的形式进行组织和连接，如下图：(1)当没有索引时，数据查询通过上面对数据页的初步分析以及数据页内部的数据结构，现在我们可以看到如果我们要查询某个表中的某行数据，会经过一个什么样的过程。数据页当然是一开始就存放在磁盘上的。一个表对一般对应多个数据页。查询数据时，数据页依次从磁盘加载到InnoDB缓冲池中，然后缓冲池中的缓存页通过数据页的单向链表逐行查找每一行数据.如果没有找到，就会按照数据页的双向链表数据结构进行遍历，将磁盘中的其他数据页加载到缓冲池中进行遍历查询。可以看到，上面的查询方式有点傻，因为如果你要查询的数据行刚好是这张表最后一个数据页的最后一行，那么所有的数据页都得扫描一次，然后每个数据页也遍历链表。整体效果是遍历O(n)时间复杂度的链表，所以查询性能肯定不好。(2)优化数据页槽中的查询效率我们先将注意力转移到单个数据页中的数据查询上。假设我们已经锁定了某个数据页中的数据，但是我们怎样才能快速的从这个数据页中找到我们想要的那一行数据呢？通过前面的分析可以知道，最笨的方式就是在数据页遍历单向链表查询，一个节点一个节点扫描，对应的查询效率肉眼可见低。但是如果我们能像翻书一样按照目录来缩小我们查询的范围，那查询效率不就相应的提高了吗？根据这个思路，InnoDB存储引擎设计了槽来组织数据页。对于多个数据行，槽信息存储在数据页中的数据页目录中。简单来说，slot就是将数据页中的多个数据行进行分组，每个数据行组在本组中寻找主键值最大的数据行的地址作为slot信息，使得在数据页目录页面的槽位不就是目录吗？标记了多个数据行组的位置信息，如下图：现在在数据页目录中有了slot信息，此时需要查询数据中某行数据的答案页面不是很简单。比如我们要查询主键为4的那一行数据，我们直接通过二分法锁定数据页目录中的slot2，时间复杂度为O(logn)，因为slot的位是紧密相连的，你可以通过slot2找到slot1，从slot1的末尾开始，开始遍历group2中的数据，因为每组的数据量都非常小，此时在这么小的范围内简单遍历就可以快速找到主键为4的一行数据，时间复杂度从之前的O(n)降低到O(logn)，效率相当可观。但是如果不通过主键查询，此时slots是不可用的，必须在数据页中逐条遍历单向链表，才能找到想要的那一行数据。2.2索引前夕——分页我们先从一个小插曲开始，简单了解下分页。该内容也是后续索引机制正常运行的基础。我们都知道一个数据页的大小是16KB。当一个数据页中有足够的数据行时，会重新创建一个数据页继续写入数据行。如果我们不用索引还好，但是如果我们要在表中创建索引，那么对多个数据页中的数据就有约束了。如果新创建的数据页中数据行的主键值小于之前数据页的主键值，则不允许出现这种情况，如下图所示：如果出现上图这种情况，多个数据页之间的主键是乱序的，而索引机制的实现是基于多个数据页的主键大小依次递增，所以这时候就会发生分页。其实分页的目的也很明确，就是调整不同数据页的数据顺序，使得依次创建的索引页中，下一个数据页中每个数据行的主键值较大比上一个数据页，当然，一个数据页当然是以单向链表的形式依次递增。分页过程如下图所示：我们可以看到，分页主要是调整下一个数据页之间数据行的数据顺序，从而存储多个每个数据页之间的主键值有序，在这样有序的数据中，高效的查询成为可能。频繁发生页面拆分。毕竟分页涉及到数据的移动，也会造成性能上的损失。这也警示我们，降低页面分裂的概率是非常有必要的。我们在设计表结构的时候可以尽量使用主键的自增长方式，而不是自定义主键的创建方式很难保证主键的顺序，使用主键的自增长方式主键可以大大避免数据页之间主键大小乱序的问题，减少页分裂的发生概率。2.2查询从主键目录到索引页的一行数据，在物理层面，就是定位哪一行数据在哪个数据页。在数据页中定位数据的问题，之前我们通过slot优化了查询效率，现在要解决的是如何在大量的数据页中定位数据页，这就是索引的目标。(1)主键目录InnoDB存储引擎一开始就使用主键目录，以数据页号和数据页的最小主键值作为记录，如下图所示：这样，我们不需要扫描我们要检查的数据，一个数据页中的所有数据将被扫描到下一个。直接通过id去主键目录下看，通过二分查找定位到具体的数据页，然后通过数据页内部的定位槽遍历那个槽对应的数据行分组，找到具体的一行数据.(2)索引页的问题是每个表对应的数据页很多，主键目录会有大量的数据，可能放不下。这时候InnoDB的设计者既要存放目录数据又要存放数据啊，为什么我们不能用数据页来放呢，所以把主键目录的信息移到了数据页中，而这些数据页就是称为索引页，如下图所示：从这里我们可以知道，数据页绝对不是简单的存放数据表中的数据。那么，既然主键目录的容量有限，我们就把主键目录的信息移到数据页中，形成索引页，但是还是出现同样的问题，一个数据页的大小只有16KB，而且索引页本身的容量也是容量不够怎么办？为了解决索引页容量不足的问题，将重新创建和升级索引页。首先将超出容量的数据放入一个新的索引页，然后再添加一层索引页，如下图所示：从上图我们可以看出，新的一层indexpage35不存储最小主键对应的数据页目录，而是最小主键对应的index页目录，以此类推。如果这里indexpage35的容量还不够，那么继续往上层扩展，最后的效果是这样的：看到了吗，indexpages一层层组成的结构不是我们常说的索引树，而这棵树在mysql中称之为B+索引树。树的数据结构自然可以用二分法查询，所以现在我们要查询一段数据，从树的根节点开始通过二分法查找，锁定数据页O(logn)时间复杂度，然后在数据页中也用二分法锁槽，简单遍历槽找数据。与没有索引的场景相比，速度是相当快的。3、聚簇索引、普通索引和覆盖索引关于索引有一些常见的名词我们需要区分一下。首先，聚簇索引就像我们上面看到的树。它的叶节点是数据页。这些数据页存储了数据表中每一行的完整数据，所以如果B+树是以完整数据的数据页为叶子节点，我们称这种索引树为聚簇索引；如果一个索引的索引树不以数据页为叶节点，则称为二级索引或普通索引。聚簇索引与普通索引最大的区别在于，聚簇索引的叶子节点存放的是数据行的完整数据，而二级索引的叶子节点只存放数据的部分字段。覆盖索引本身不是索引，而是一种查询数据的方式。比如我们对table表中的字段name进行索引，然后执行查询如：selectnamefromtablewherenamelike'Zhang%'，这时候我们可以直接查询对应的一批name值从name字段对应的B+树种中提取，然后直接返回。也就是说，我们要的字段名已经在索引上了，我们直接使用二分法来高效检索，直接从树上摘下来就可以了，这种查询方式称为覆盖索引。当然，相对于覆盖索引的方式，如果查询改为：select*fromtablewherenamelike'Zhang%'，这就不是覆盖索引了，因为这时候你不仅仅需要从索引树，还可以使用返回表的id值来查询所有的字段。4.索引的优缺点分析索引的优点当然是高效的查询数据。索引将遍历链表的O(n)查询时间复杂度优化为O(logn)时间复杂度。但是，索引的缺点也很明显。首先，从时间上来说，肯定要求主键是有序增长的。主键无序会导致频繁分页，影响效率；在对数据库表进行增删改查的同时，还需要维护索引，这也是性能损失的一个点；从空间上看：索引相关的数据和实际数据占用相同的内存空间。因此，索引虽然可以提高查询效率，但也不得不承担它给我们系统带来的性能损失。从这个角度来看，并不是建的索引越多越好。5.三个维度设计索引接下来我们从以下三个维度优化索引的设计(1)首先从时间上来说，尽可能多的使用主键自增长等方式尽可能保证新的增量数据页中数据行的主键自增，避免不必要的分页造成性能损失，降低查询效率。另外，选择一个合适的字段作为索引字段也很重要。需要选择基数大的字段，也就是一个字段可能有更多的值，这样我们在B+树中查询的时候，使用二分查询的效率最高。Power，如果索引字段的基数比较小，二分查找可能会退化为时间复杂度为O(n)的线性查询。(2)从空间的角度来看，因为索引数据本身也占空间，所以可以选择长度较小的字段作为索引字段，这样整个B+树就不会占用那么多的空间。但是如果非要用长字段作为索引，可以使用字段的前缀作为索引作为折衷。这样的索引也称为前缀索引，但只能用于模糊查询。在groupby中使用，不适合orderby。(3)在作用范围上，当然我们设计索引的目的是为了更好的利用索引。在设计索引时，尽量让where、groupby、orderby语句使用索引。本文由博客多发平台OpenWrite发布！
