指数可能让很多人望而生畏。毕竟每次面试都要问MySQL索引。就算抛开面试，在平时的开发中，SQL优化也是重中之重。毫不夸张的说，系统中SQL的好坏可以直接决定你系统的运行速度。但是在优化之前有没有想过一个问题？即：我们优化的原则是什么？优化SQL的理论依据是什么？虽然实践带来真知，但我认为理论是支撑实践的基础，因为我们不能无目的的盲目实践，因为往往事倍功半。所以说了这么多，我只想告诉大家，在真正开始索引优化之前，我们需要深入了解索引的原理。这样谈优化，你会感觉更顺畅~1.索引的本质索引的本质是一种排序好的数据结构。这个相信大家并不陌生，因为说到索引，很多人自然会想到字典中的目录。是的，这样的比喻很形象，但是如果再深入下去，恐怕很多朋友都会有些无语了。既然你已经知道了索引的本质，那么你已经有了阅读本文的基础，相信看完正文的你一定会对索引的原理有一个全新的认识。2、索引分类在数据库中，索引的种类很多（不要狭隘地认为索引只有B+树，因为我们平时用的是MySQL）。不同的类型显然是针对不同的场合，那么索引有哪些类型呢？下面让我们有个大概的了解。2.1.哈希索引哈希索引是一种比较常见的索引。它对单条记录的查询效率非常高，时间复杂度为1。但是Hash索引并不是最常用的数据库索引类型，尤其是我们常用的MysqlInnodb引擎是不支持hash索引的。主要原因如下：哈希索引适合做精确查找，不适合范围查找*因为存储引擎会为每一行计算一个哈希码，哈希码比较小，不同key的哈希码-值行通常不同，哈希索引中存储的是哈希码，哈希码之间是无规律的，哈希运算不能保证顺序，所以两个值相似的数据，哈希值相差甚远并分为不同的桶。这就是为什么哈希索引只能进行全时匹配查询的原因，因为只有这样哈希码才能匹配到数据。对于哈希索引，朋友们只需要了解这个即可。2.2.二叉树另外，普通索引使用的数据结构是树结构。首先介绍一下最经典的二叉树。先介绍一下二叉树的特点：二叉树的时间复杂度是O(n)一个节点只能有两个子节点。即度数不超过2，左子节点小于本节点，右子节点大于本节点。首先我们看一下二叉树的样子，但是在极端情况下，会出现chaining，即节点总是在一侧增加。在下图所示的二叉树中，有一种特殊的结构——平衡二叉树，平衡二叉树的特点：根节点会随着数据的变化而变化数据越多，遍历的次数越多IO的，越慢（磁盘的IO由树的高度决定）2.4、B树（二三树）了解了二叉树之后，我们可以进一步说说什么是B树。B-tree是这样的：从B-tree的结构图中我们可以看出，每个节点不仅包含数据的键值，还包含数据值。但是，每个页面的存储空间是有限的。如果数据比较大，每个节点的key存储会比较少。当数据量很大时，B-tree也会很深，从而增加磁盘IO次数，从而影响查询效率。好了，说到这里，常用索引的类型也说完了。以上内容只是铺垫。让我们正式开始MySQL的B+树。2.5.B+树MySQL中最常用的索引数据结构是B+树，它有以下特点：nottheleaves节点只存储key信息，这样可以大大减少每个节点存储key的数量，降低B+树的高度。B+树的叶子节点的key按照从小到大的顺序排列，左边末尾的数据会保存右边节点开头的数据。指针。B+树的层次更少：与B树相比，B+在每个非叶子节点中存储的关键字更多，而且树的层次更少，因此查询数据更快。B+树查询速度更稳定：B+所有关键字数据地址都存在于叶子节点上，所以每次查找的次数相同，所以查询速度比B树更稳定；B+树天然具有排序功能：B+树的所有叶子节点数据组成一个有序链表，查询大小范围内的数据查询时更方便，数据紧凑度高，缓存命中率高会比B-tree高。B+树全节点遍历速度更快：B+树遍历整棵树只需要遍历所有叶子节点，而不是像B树那样遍历每一层，有利于数据库做全表扫描。好了，说了这么多B+树的特点，下面我们来上一张图，看看B+树长什么样子。页和数据页通过双向链表连接。好了，到这里我们就快速了解一下各个索引的类型。下面开始正式的B+树的分析。3.主键目录。我们把上图中的数据页拿过来细化一下，就变成了下图。我们都知道MySQL在存储数据时以数据页为最小单位，数据存储在数据页中数据库中的存储是连续的，数据页中的数据是按照主键（无主键按照MySQL自己维护的ROW_ID排序），数据页之间通过双向链表关联。时间通过单向链表关联。也就是说每个数据页中都有一个，他必须有一个最小主键，然后每个数据页的页码和最小主键就组成了一个主键目录（如上图左边部分）)，假设现在我们要查找主键为2的数据，通过二分查找的方式最终确定主键为2的记录在数据页1中。这个时候我们会定位到数据页1，然后定位到主键2的记录。我们先粗略的了解一下，不要深究流程的细节，先从宏观的角度看结构原理，再看微观层面的实施原则。上面刚才说的其实可以理解为主键索引，主键索引也是最简单最基础的索引。这时候大家应该知道为什么可以快速查询主键了吧？4.索引页但是现在假设有很多很多数据页，对应的主键目录会不会很大呢？那么假设有1000万条记录和5000万条记录呢？即使是二分查找，其效率仍然很低，所以为了解决这个问题，MySQL设计了一种新的存储结构——索引页。比如下面这种情况，假设上面的主键目录下有很多条记录，上面的结构演变成了这样，MySQL会把记录拆分到不同的索引页中，也就是下面这样的一个索引page记录了每个数据页的页码和数据页中最小主键的记录，也就是说最小主键和数据页号不是简单的维护在主键目录中，而是演化成了一个索引页面已创建。索引页类似于数据页。如果一页不够存储，它将被拆分到下一页。如果你现在想找到id=20的这条记录，嗯？那我该去哪个索引页找这条记录呢？所以这个时候，维护索引页肯定是很有必要的。没错，MySQL也是这样设计的，也就是说，MySQL也设计了维护索引页的数据结构。其实也叫索引页，只是层次不同，类似下面：也就是说维护索引页的索引页在实际存放记录和数据的索引页的上层页。现在如果要查找id=20的记录，需要从最上面的索引页开始查找，使用方法二分查找，很快找到id=20的记录在索引页2，并且然后在索引页2上查找，然后和之前一样（注意索引页中的记录也是通过单向链表连接），根据最小的主键，id=20可以定位到数据页5，假设数据页5是这样的，你能算出此时数据是怎么定位的吗？5、索引页层次感好。既然已经知道索引页过多会扩散到上层，那么现在假设上层索引页记录过多，怎么办？很简单，继续分裂，然后继续下一关，废话不多说，我画个图帮助大家理解，我明白了，你明白了吗？让我们模拟一个搜索过程。假设你要查找记录37。老实说，我根本不知道这个。记录在哪里。好了，现在我们来模拟一下MySQL的查找过程。首先，从最上面的索引页开始搜索。因为id=37，所以我们定位到index页16，然后在index页16继续查找，这时候我们也可以在index页3定位到id=37，然后继续查找，最后数据就可以了位于数据页8，假设数据页8是这样的，是不是就完美了呢？如果非要我完成上面的图，那....老哥那是必须的（图太大了，索引页中数据的链表结构就画不出来了）这个时候，你有没有发现了什么小秘密？它看起来像二叉树吗？其实这是一个B+树的结构，也是数据实际存放在磁盘上的物理结构。B+树有什么特点？B+树也是一种二叉查找树，但是它的数据只存放在叶子节点（这里是数据页），像这样由B+组成的索引页+数据页树就是聚簇索引（这句话很重要的）。聚集索引是MySQL基于主键索引结构创建的。6.非主键索引但是现在问题又来了。由于这里强调的是主键索引，所以我们在平时的开发中也会用到很多主键索引以外的索引。这个时候怎么办？假设您现在正在索引姓名和年龄。现在回过头来看主键索引，插入数据的时候是否需要按照主键的顺序来维护一个B+树呢？其实非主键索引的原理也是一样的。MySQL维护着一颗B+树。说白了，你建多少个索引，MySQL就帮你维护多少个B+树（是不是突然明白为什么索引太多建不起来了？我之前就知道索引太多建不起来，因为indexes也占空间，其实这是根本原因）如果name+age现在真的被索引了，这个时候是不是存储了？这时候MySQL按照name+age维护了一个单独的B+树结构，数据还是存放在数据页中，只是原来数据中每条记录写id=xx，现在写name=xx，age=xx，id=xx，不管怎样，主键肯定会存的，先上个图吧。MySQL在插入数据时，会先按照姓名排序，如果姓名相同，则按照联合索引中的年龄排序，如果仍然相同，则按照主键排序场地。插入的原理是这样的。这时候每个数据页中的记录实际上都存储在索引字段和主键字段中，而其他字段没有存储（为什么不呢？到处存储相同的数据很浪费空间，也没有必要，所以会有下面的索引优化），至于查找，原理和过程和聚簇索引是一样的，这里就不多说了，但是下面的内容很关键：假设你执行下面的SQL:SELECTnameFROMstudentWHEREname='wx'thenthis当查询完美时，使用了索引，不需要回表。（只要是name、age、id这三个字段）这时候直接就可以得到最终的记录了。也就是说，因为联合索引中的记录只有name、age、id，所以在查询中如果只查询这三个字段，那么就可以在B+树中查询到想要的结果。现在假设查询SQL是这样的（我们假设student中除了name、age、id还有其他字段）SELECT*FROMstudentWHEREname='wx'，那么就结束了，因为虽然你现在是基于name很快就定位到了记录，但是因为name+age不是聚簇索引，所以此时B+树的数据页只存储了它的关联索引和主键索引字段，不存储其他字段，所以其他字段这个时候属性的值是获取不到的，这个时候怎么办呢？在这种情况下，MySQL需要查询回表。这时，MySQL会根据位于的某条记录中的id重新查找聚簇索引，也就是根据id维护id，然后再到B+树中查找。因为聚簇索引中的数据页记录了一条记录的完整记录，所以这个过程被回调回表。再次强调一下下表的意思：基于非主键索引查询的结果没有要查找的字段值。这时候就需要根据主键从聚簇索引的根节点开始重新查找，这样就完成了重新查找记录。.最后看一下MySQL对非主键索引的维护过程：对于非主键索引（一般是联合索引），在维护B+树时，会依次根据联合索引的字段进行判断，假设联合索引为：姓名+地址+年龄，那么MySQL在维护索引的B+树时，会先按照姓名排序。如果名称相同，则按第二个地址排序。如果地址相同，则按年龄排序。如果age同理，那么会按照主键字段值排序，而对于非主键索引，MySQL在维护B+树时，只维护索引字段和主键字段。
