一口气搞懂MySQL索引的所有知识点看了看笔记，决定搞一个完整版的索引。老规矩可能不像我正常的文章风格那么跳脱，但是干货一定会让你有所收获。索引介绍什么是索引？正式来说，索引是一种帮助MySQL高效获取数据的数据结构。更通俗地说，数据库索引就像一本书前面的目录，可以加快数据库的查询速度。一般来说，索引本身也很大，不可能全部存储在内存中，所以索引往往是存储在磁盘上的一个文件中（可能存储在单独的索引文件中，也可能存储在一起与数据文件中的数据）。我们平时所指的索引，包括聚簇索引、覆盖索引、组合索引、前缀索引、唯一索引等，没有具体说明，默认都是使用B+树结构组织（多向搜索树，不是必然是二进制）的索引。索引的优缺点优点：可以提高数据检索的效率，降低数据库的IO成本，类似于书籍的目录。通过索引列对数据进行排序，降低了数据排序的成本，降低了CPU消耗。索引的列会自动排序，包括[单列索引]和[组合索引]，但组合索引的排序比较复杂。如果按照索引列的顺序排序，对应orderby语句，效率会大大提高。缺点：索引占用磁盘空间。索引虽然会提高查询效率，但是会降低更新表的效率。例如，每对一张表进行增删改查，MySQL不仅保存数据，还会保存或更新相应的索引文件。IndexTypePrimaryKeyIndex索引列中的值必须是唯一的，不允许空值。普通索引MySQL中的基本索引类型，没有限制，允许在定义索引的列中插入重复值和空值。唯一索引被索引的列中的值必须是唯一的，但允许空值。全文索引只能在CHAR、VARCHAR、TEXT的文本类型字段上创建。当字段长度比较大的时候，如果创建一个普通的索引，在进行类似模糊查询的时候效率是比较低的。这时候就可以创建全文索引了。全文索引在MyISAM和InnoDB中都可用。空间索引MySQL5.7之后的版本支持空间索引，并且支持OpenGIS几何数据模型。MySQL遵循空间索引的OpenGIS几何数据模型规则。前缀索引对CHAR、VARCHAR、TEXT等文本类型的列创建索引时，可以指定索引列的长度，但不能指定值类型。其他（按索引列数分类）单列索引复合索引复合索引的使用需要遵循最左前缀匹配原则（leftmostmatchingprinciple）。一般在条件允许的情况下，使用复合索引代替多个单列索引。索引数据结构Hash表Hash表，Java中的HashMap，TreeMap就是Hash表结构，以键值对的形式存储数据。我们使用哈希表来存储表数据。Key可以存放索引列，Value可以存放行记录或行磁盘地址。Hash表在等值查询时效率很高，时间复杂度为O(1)；但是，它不支持快速范围搜索，范围搜索只能通过扫描整个表来完成。显然这不适合用作经常需要搜索和范围搜索的数据库索引。二叉搜索树Binarytree，想必大家脑海中都会有一个画面。二叉树特点：每个节点最多有2个叉子，左子树和右子树的数据顺序是左边小右边大。这个特性是为了保证每次查找都能减半，减少IO次数，但是二叉树是比较考验第一个根节点的值的，因为在这个特性下很容易出现“树不分叉”.感觉很难，而且很不稳定。显然，如果这种情况不稳定，我们会选择平衡二叉树，在设计上必然会避免这种情况。树的层级最多相差1，在插入和删除数据时，采用左手/右手操作来维持二叉树的平衡，不会出现左子树很高而右子树很高的情况子树很短。使用平衡二叉搜索树查询的性能接近二分查找法，时间复杂度为O(log2n)。查询id=6，只需要两个IO。从这个特性来看，你可能会觉得这样很好，可以达到二叉树的理想情况。但是，仍然存在一些问题：时间复杂度与树高有关。树的高度取决于需要检索多少次，每个节点的读取对应一次磁盘IO操作。树的高度等于每次查询数据的磁盘IO操作数。每次磁盘寻道时间为10ms。当表数据量很大时，查询性能会很差。（100万条数据量，log2n约等于20次磁盘IO，时间为20*10=0.2s）平衡二叉树不支持范围查询的快速搜索。范围查询需要从根节点开始多次遍历，查询效率不高。B-Tree：二叉树的转换MySQL数据存储在磁盘文件中。在查询和处理数据时，需要先将磁盘中的数据加载到内存中。磁盘IO操作是非常耗时的，所以我们优化的重点是尽量减少磁盘IO操作。访问二叉树的每个节点时都会发生一次IO。如果要减少磁盘IO操作，就需要尽可能的降低树的高度。那么如何降低树的高度呢？如果key为bigint=8字节，则每个节点有两个指针，每个指针为4字节，一个节点占用的空间为16字节（8+4*2=16）。因为MySQL的InnoDB存储引擎一次IO可以读取一页的数据量（默认16K），但是二叉树中一次IO的有效数据量只有16字节，空间利用率极低。为了最大限度地利用一个IO空间，一个简单的想法是在每个节点中存储多个元素，并在每个节点中存储尽可能多的数据。每个节点可以存储1000个索引（16k/16=1000），从而将二叉树转化为多叉树，通过增加树的叉树，将树由高瘦变为矮胖。构造100万条数据，树的高度只需要2层（1000*1000=100万），也就是说查询数据只需要2次磁盘IO。减少了磁盘IO次数，同时也提高了查询数据的效率。这种数据结构称为B树。B树是一种多叉平衡搜索树。主要特点如下图所示：B-tree的节点中存储了多个元素，每个内部节点有多个fork。节点中的元素包含键值和数据，节点中的键值从大到小排列。即数据存储在所有节点上。父节点中的元素不会出现在子节点中。所有叶子节点都位于同一层次，叶子节点深度相同，叶子节点之间没有指针连接。比如查询b-tree中数据的情况：假设我们查询的是value等于10的数据查询路径diskblock1->diskblock2->diskblock5第一个diskIO：loaddiskblock1入内存，在内存中从头开始遍历比较，10<15，向左走，寻址磁盘块2到磁盘。第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头开始遍历比较，7<10，在磁盘中寻址定位到磁盘块5。第三次磁盘IO：将磁盘块5加载到内存中，在内存中从头开始遍历比较，10=10，找到10，取出数据，如果数据中存储的是行记录，则取出数据,查询结束。如果存储的是磁盘地址，则需要根据磁盘地址从磁盘中取出数据，并终止查询。与二叉平衡搜索树相比，虽然整个搜索过程中数据比较的次数并没有明显减少，但是磁盘IO次数会大大减少。同时，由于我们的比较是在内存中进行的，所以比较的时间消耗可以忽略不计。B树的高度一般为2到3层，可以满足大部分应用场景，所以使用B树建立索引可以大大提高查询效率。流程如图：B-tree索引查询流程看到这里，你肯定觉得B-tree很理想，但是前辈会告诉你还有可以优化的地方：B-tree不支持fast搜索范围查询。想想这样一种情况如果我们要查找10到35之间的数据，找到15之后还需要回到根节点重新查找，需要从根节点开始多次遍历，查询效率需要改进。如果数据存储行记录，则行的大小将随着列数的增加而增加。这时候一个page能存放的数据量会减少，树会相应增加，磁盘IO次数会增加。B+树：改造B树B+树，作为B树的升级版，在B树的基础上，MySQL在B树的基础上继续改造，使用B+树建立索引。B+树和B树的主要区别在于非叶子节点是否存储数据的问题。B树：非叶子节点和叶子节点都存储数据。B+树：只有叶子节点存储数据，非叶子节点存储键值。叶子节点之间通过双向指针相连，最底层的叶子节点组成一个双向有序链表。B+树数据结构B+树的底部叶子节点包含所有索引项。从图中可以看出，B+树在查找数据时，由于数据存储在最底层的叶子节点上，所以每次查找时都需要检索叶子节点来查询数据。因此，在查询数据的情况下，每个磁盘的IO与树高直接相关，但另一方面，由于数据是放在叶子节点中的，磁盘块锁中存储的索引个数index会随之增加。与B-tree相比，B+树的树高理论上比B-tree矮。还有一种情况是索引覆盖了查询。索引中的数据满足当前查询语句需要的所有数据。这时候只需要找到索引就可以立即返回，不需要去检索最底下的叶子节点。举个例子：等值查询如果我们查询的数据等于9查询路径磁盘块1->磁盘块2->磁盘块6第一次磁盘IO：将磁盘块1加载到内存中，从中遍历比较内存中的开头，9<15，向左走，将磁盘块2寻址到磁盘。第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头开始遍历比较，7<9<12，在磁盘中寻址定位到磁盘块6。第三次磁盘IO：将磁盘块6加载到内存中，在内存中从头开始遍历比较，在第三次索引中找到9，取出数据。如果数据中存有行记录，取出数据，查询结束。如果存储的是磁盘地址，则需要根据磁盘地址从磁盘中取出数据，并终止查询。（这里需要区分的是，在InnoDB中，Data存储的是行数据，而MyIsam存储的是磁盘地址。）流程如图：范围查询：如果我们要查找9到26之间的数据，查找路径为diskblock1->diskblock2->diskblock6->diskblock7，先找到value等于9的数据，将value等于9的数据缓存到结果集中。这一步和前面的等效查询过程一样，发生了3次磁盘IO。找到15后，底层叶子节点是一个有序列表。我们从磁盘块6，键值9开始，向后遍历，过滤所有满足过滤条件的数据。第四次磁盘IO：根据磁盘6的后继指针寻址定位磁盘块7，将磁盘7加载到内存中，在内存中从头开始遍历比较，9<25<26，9<26<=26，缓存数据到结果集。主键唯一（以后不会有<=26的数据），不需要向后查找，查询终止。将结果集返回给用户。可见B+树可以保证等价查询和范围查询的快速查找，MySQL索引采用了B+树的数据结构。Mysql的索引实现已经引入了索引数据结构，所以必须要带入Mysql才能看到真正的使用场景，所以这里分析一下Mysql的两个存储引擎：MyISAM索引和InnoDB索引的索引实现。MyIsam索引使用一个简单的以用户表为例。user表有两个索引，id列为主键索引，age列为普通索引PRIMARYKEY(`id`)USINGBTREE,KEY`idx_age`(`age`)USINGBTREE)ENGINE=MyISAMAUTO_INCREMENT=1DEFAULTCHARSET=utf8;MyISAM_user查询数据MyISAM数据文件和索引文件分开存放。当MyISAM使用B+树构建索引树时，叶子节点中存储的键值为索引列的值，数据为索引所在行的磁盘地址。主键索引MyIsam主键索引表user的索引存放在索引文件user.MYI中，数据文件存放在数据文件user.MYD中。简单分析一下查询时的磁盘IO情况：根据主键的等值查询数据：select*fromuserwhereid=28；先在主键树中从根节点开始查找，将根节点加载到内存中，比较28<75，向左走。(1磁盘IO)将左子树节点加载到内存中，比较16<28<47，向下查找。(1磁盘IO)检索叶子节点，将节点加载到内存中进行遍历，比较16<28,18<28,28=28。找到一个值为30的索引条目。(1磁盘IO)从索引项中获取磁盘地址，然后从数据文件user.MYD中获取对应的整行记录。(1diskIO)将记录返回给客户端。磁盘IO次数：3次索引检索+记录数据检索。根据主键范围查询数据：select*fromuserwhereidbetween28and47；1、先在主键树中从根节点开始查找，将根节点加载到内存中，比较28<75，向左走。(1个磁盘IO)2.将左子树节点加载到内存中，比较16<28<47，向下查找。（1个磁盘IO）3、取出叶子节点，将节点加载到内存中，遍历比较16<28,18<28,28=28<47。找到一个值为28的索引条目。根据磁盘地址，从数据文件中获取行记录缓存，存入结果集中。(1diskIO)我们的查询语句是范围搜索，需要向后遍历底层叶子列表，直到最后一个不满足过滤条件的。4、向后遍历底层叶子链表，将下一个节点加载到内存中，遍历比较，28<47=47，根据磁盘地址从数据文件中获取行记录缓存到结果集中。（1个磁盘IO）5、最后得到满足过滤条件的两项，将查询结果集返回给客户端。磁盘IO次数：4次索引检索+记录数据检索。备注：以上分析仅供参考。MyISAM在查询时，会将索引节点缓存在MySQL缓存中，而数据缓存依赖于操作系统本身的缓存，所以不会每次都去磁盘。这里只是分析索引的使用过程。辅助索引在MyISAM中，辅助索引的结构和主键索引是一样的，没有区别。叶子节点的数据存储在行记录的磁盘地址中。只有主键索引的键值是唯一的，而二级索引的键值可以重复。在查询数据时，由于辅助索引的键值不唯一，可能会有多条记录具有相同的值，所以即使是等价查询，也需要通过范围查询的方式在辅助索引树中检索数据。InnoDB索引主键索引（聚集索引）每个InnoDB表都有一个聚集索引。聚簇索引是使用B+树构建的，叶子节点中存储的数据就是整行记录。一般来说，聚簇索引相当于主键索引。当一张表没有创建主键索引时，InnoDB会自动创建一个ROWID字段来构建聚集索引。InnoDB创建索引的具体规则如下：在表上定义主键PRIMARYKEY，InnoDB使用主键索引作为聚簇索引。如果表没有定义主键，InnoDB会选择第一个非NULL的唯一索引列作为聚集索引。如果以上两者都不可用，InnoDB将使用一个6字节长的整数隐式字段ROWID字段来构建聚集索引。插入新行时，ROWID字段会自动递增。除聚簇索引外的所有索引都称为二级索引。在InnoDB中，辅助索引的叶子节点中存储的数据就是该行的主键值。检索时，InnoDB使用这个主键值在聚簇索引中搜索行记录。这里以user_innodb为例。user_innodb的id列是主键，age列是普通索引。创建表`user_innodb`(`id`int(11)NOTNULLAUTO_INCREMENT,`username`varchar(20)DEFAULTNULL,`age`int(11)DEFAULTNULL,PRIMARYKEY(`id`)USINGBTREE,KEY`idx_age`(`age`)USINGBTREE)ENGINE=InnoDB;用户数据InnoDB数据和索引存储在文件t_user_innodb.ibd中。InnoDB的数据组织方式是聚集索引。主键索引的叶子节点会存放数据行，二级索引只会存放主键值。InnoDB主键索引等效查询数据：select*fromuser_innodbwhereid=28;1、先在主键树中从根节点开始查找，将根节点加载到内存中，比较28<75，向左走。(1磁盘IO)将左子树节点加载到内存中，比较16<28<47，向下查找。(1diskIO)取出叶子节点，将节点加载到内存中进行遍历，比较16<28,18<28,28=28。找到值等于28的索引项，可以直接得到整行数据。将修改后的记录返回给客户端。(1diskIO)磁盘IO次数：3次。辅助索引除聚簇索引外的所有索引都称为辅助索引。InnoDB的辅助索引只会存储主键值而不是磁盘地址。以表user_innodb的age列为例，age索引的索引结果如下图所示。InnoDB辅助索引底层的叶子节点按照(age,id)的顺序排序。首先，按照年龄栏从小到大排序。如果age列相同，则按照id列从小到大排序。使用辅助索引需要两次索引检索：先检索辅助索引获取主键，然后使用主键检索主索引中的记录。画图分析等价查询的情况：select*fromt_user_innodbwhereage=19;InnoDB辅助索引查询根据在辅助索引树中得到的主键id，从主键索引树中检索数据的过程称为回表查询。磁盘IO次数：辅助索引3次+获取记录回表3次组合索引或者以自己创建的表为例：表abc_innodb，id为主键索引，联合索引idx_abc(a,b,c)被创建。创建表`abc_innodb`（`id`int（11）NOTNULLAUTO_INCREMENT，`a`int（11）DEFAULTNULL，`b`int（11）DEFAULTNULL，`c`varchar（10）DEFAULTNULL，`d`varchar（10）DEFAULTNULL,PRIMARYKEY(`id`)USINGBTREE,KEY`idx_abc`(`a`,`b`,`c`))ENGINE=InnoDB;复合索引的数据结构：复合索引结构1复合索引的查询过程：select*fromabc_innodbwherea=13andb=16andc=4;联合索引查询过程中的最左匹配原则：最左前缀匹配原则与联合索引的索引存储结构和检索方式有关。在组合索引树中，底部叶子节点按照第一列a从左到右升序排列，但b列和c列是无序的，b列只在a列的值时小范围递增是相等排序的，当a和b两列相等时，c列只能在小范围内递增排序。就像上面的查询一样，B+树会先比较a列，来决定接下来应该搜索的方向，是左还是右。如果a列相同，则比较b列。但是如果查询条件没有列，B+树不知道第一步应该查哪个节点。可以说创建的idx_abc(a,b,c)索引相当于创建了三个索引(a),(a,b)(a,b,c)。,复合索引的最左前缀匹配原则：在使用复合索引查询时，mysql会一直向右匹配，直到遇到范围查询（>,<,between,like）停止匹配。覆盖索引并不是说覆盖索引就是一种索引结构。覆盖索引是一种非常常见的优化方法。因为在使用辅助索引的时候，我们只能获取到主键值，也就是说要获取数据，需要根据主键查询主键索引，然后获取数据。但是试想这样一种情况，如果我在上面的abc_innodb表中查询组合索引的时候只需要abc字段，是不是意味着我们可以直接返回组合索引的叶子节点而不返回surface。这种情况是覆盖索引。可以看一下执行计划：覆盖索引的情况：使用了覆盖索引但没有使用覆盖索引：总结看到这里，是不是对你的sql语句中的索引有更多的优化思路？例如：避免返回InnoDB存储引擎中的表，在使用辅助索引查询时，因为辅助索引的叶子节点保存的数据不是当前记录的数据，而是当前记录的主键索引，如果索引需要获取当前记录的完整数据，则必须根据主键值从主键索引继续查询。在这个过程中，我们形成了一个位回表。回想表必然会消耗性能，影响性能。那么如何避免呢？使用索引覆盖，例如：某场景下已有的User表（id(PK),name(key),sex,address,hobby...），selectid,name,sexfromuserwherename='zhangsan';这条语句在业务中使用频率很高，user表的其他字段使用频率远低于它。在这种情况下，如果我们建立name字段的索引，而不是使用单一的索引，使用联合索引(name,sex)的情况下，然后执行这条查询语句，是否可以得到当前语句的完整数据根据辅助索引查询的结果得到。这样可以有效避免回表获取性别数据。下面是一个使用覆盖索引优化策略减少回表的典型案例。联合索引使用联合索引。在建索引的时候，尽量判断联合索引是否可以用在多个单列索引上。使用联合索引不仅可以节省空间，还可以更方便地使用索引覆盖。试想一下，你索引的字段越多，就越容易满足查询返回的数据。比如联合索引（a_b_c）是否相当于有一个索引：a,a_b,a_b_c三个索引，这样是不是节省空间？当然，节省的空间不是(a,a_b,a_b_c)三个索引的三倍，因为索引树的数据没有变化，但是确实保存了索引数据字段的数据。创建联合索引的原则是，在创建联合索引时，应将使用频率高的列和区分度高的列放在最前面。频繁使用意味着索引利用率高，高区分度意味着过滤粒度大。这些都是在索引创建时需要考虑的优化场景，也可以在经常需要作为查询返回的字段上加入联合索引。如果在联合索引中加入了一个字段，并且使用了覆盖索引，那么我推荐这种情况下使用联合索引。联合索引的使用考虑是否有多个单列索引可以合并，如果有则创建多个当前单列索引作为联合索引。当前索引具有经常用作返回字段的列。这时可以考虑是否可以将当前列添加到已有索引中，使查询语句使用覆盖索引。好了，以上是我自己索引的一些小总结，有点冗长乏味，适合收藏慢慢看。我是敖丙，知道的越多，不知道的越多，下期见。
