MySQL索引篇

索引的分类

聚集索引

  1. 聚集索引其实就是主键索引，在查询流程中。如果查询的数据命中索引，就直接把数据返回了。

非聚集索引

  1. 非聚集索引就是非主键索引的其它索引，在查询流程中。如果查询的数据命中索引，会再过一遍主键索引，通过数据的ID来找出这些数据然后再返回。

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

索引的数据结构

在来了解Mysql的索引数据结构之前，我们先来分析几种常见的数据结构，为什么Mysql选择了B+树而不是其它的数据结构作为索引的数据结构。

Hash

  1. 哈希算法：也叫散列算法，就是把key通过哈希就是把任意值(key)通过哈希函数变换为固定长度的 key 地址，通过这个地址进行具体数据的数据结构。
  3. 数据结构为 Key - Value形式，特点适用于指定值查询。在不产生Hash碰撞的情况下时间复杂度是O(1)，速度是相当的快，如果是以下等值查询的SQL，则一次能就找到要查询的数据
  1. select * from user where id=1
  1. 那么现在有这个一个场景，需要查询出年纪大于18用户。
  1. select * from user where age > 18
  1. 很显然，Hash结构实现不了这种范围查询需求，所以它不适合作为关系型数据库的索引数据结构。

二分查找法

  1. 数据结构如下图：

MySQL索引篇 - 图1

  1. 又名二叉查找树，二叉查找树的时间复杂度是 O(log n)，比如针对上面这个二叉树结构，我们需要计算比较 3 次就可以检索到 id=99 的数据，相对于直接遍历查询省了一半的时间，从检索效率上看来是能做到高速检索的。
  3. 此外二叉树的结构能解决哈希索引不能提供的范围查找功能，因为二叉树的叶子节点是有序的，从左到右依次排序的，如果我们查找 id=99 的数据，只需要取出右边id=86 的节点就可以了。
  5. 如果将id列构建二叉树，可以看到二叉树退化为一个单向链表，查询id=6的数据，也就意味着将进行全表扫描，全表扫描也就意味着需要遍历整张表去找数据，性能不理想。所以二叉查找树也不适合作为索引的数据结构。

MySQL索引篇 - 图2

平衡二分查找法

  1. 平衡二叉树是采用二分法思维，平衡二叉查找树除了具备二叉树的特点，最主要的特征是树的左右两个子树的层级最多相差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，不会出现左子树很高、右子树很矮的情况。
  3. 使用平衡二叉查找树查询的性能接近于二分查找法，时间复杂度是 O(log2n)。查询id=6，只需要两次IO。

MySQL索引篇 - 图3

  1.  时间复杂度和树高相关。树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数，在表数据量大时，查询性能就会很差。假设有如下场景：

MySQL索引篇 - 图4

  1. 顺序插入 1~16 个节点，查找 id=16 需要比较的节点数为 4。则需要经历4次磁盘IO才能找到想要的数据，而在存储着海量数据的数据库中，最主要的性能瓶颈就是出现在磁盘IO上，如果此时树的高度为100，有就是说要经历100次磁盘IO才能找到想要的数据。磁盘IO的次数取决与树的高度，树的高度越高则IO的次数就越多，从而性能也越慢。

总结：

  1. 平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高。

B树

  1. MySQL的数据是存储在磁盘文件中的，查询处理数据时，需要先把磁盘中的数据加载到内存中，磁盘IO 操作非常耗时，所以我们优化的重点就是尽量减少磁盘 IO 操作。访问二叉树的每个节点就会发生一次IO，如果想要减少磁盘IO操作，就需要尽量降低树的高度。
  3. 假如key为bigint=8字节，每个节点有两个指针，每个指针为4个字节，一个节点占用的空间16个字节（8+4_2=16）。我们知道，MySQL的InnoDB存储引擎一次IO会读取的一页16K的数据量，而二叉树一次IO有效数据量只有16字节，空间利用率极低。为了最大化利用一次IO空间，一个朴素的想法是在每个节点存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储1000个索引（16k/16=1000），这样就将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖。构建1百万条数据，树的高度只需要2层就可以（1000_1000=1百万），也就是说只需要2次磁盘IO就可以查询到数据。磁盘IO次数变少了，查询数据的效率也就提高了。
  1. B树的节点中存储着多个元素，每个内节点有多个分叉
  2. 节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点都储存数据。
  3. 父节点当中的元素不会出现在子节点中。
  4. 所有的叶子结点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接。

对于一个主键索引，主键值bigint=8字节，data为记录的磁盘地址为4个字节，一个元素占用空间12字节。 一个磁盘块大小为16k。磁盘块中的分叉数=元素树+1，假设可以存储x个元素，12x+(x+1)*4=16k,约等于 1000，也就是说一页中可以最多可以存储1000个元素。

  1. 二层B树结构可以存储的数量1000_1000=1百万，三层树结构可以存储的数量1000_1000*1000=1百 亿。
  2. B树的高度一般都是在2-4这个高度，树的高度直接决定IO读写的次数以及查询时间复杂度 （O(log2n)）。

MySQL索引篇 - 图5

  1. B树不支持范围查询的快速查找，如果我们想要查找15和26之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。

  2. 如果data存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。

B+树

  1. B树：非叶子节点和叶子节点都会存储数据。 
  2. B+树：只有叶子节点才会存储数据，非叶子节点存储键值。叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表。

B+树的最底层叶子节点包含所有索引项。

B+树查找数据，由于数据都存放在叶子节点，所以每次查找都需要检索到叶子节点，才能查询到数据。

B树查找数据时，如果在内节点中查找到数据，可以立即返回，比如查找值等于17的数据，在根节点中直接就可以找到，不需要再向下查找，具备中路返回的特点。

MySQL索引篇 - 图6

关于B+树的思考，既然Mysql的索引数据结构是B+树，那么一颗B+树究竟能存储多少数据呢？

  1. B+树一个节点的大小设为一页或页的倍数最为合适。因为如果一个节点的大小 < 1页，那么读取这个节点的时候其实读取的还是一页，这样就造成了资源的浪费。
  3. 在 MySQL 中 B+ 树的一个节点大小为“1页”，也就是16k。之所以设置为一页，是因为对于大部分业务，一页就足够了：首先InnoDB的B+树中，非叶子节点存的是key + 指针；叶子节点存的是数据行。
  5. 对于叶子节点，如果一行数据大小为1k，那么一页就能存16条数据；对于非叶子节点，如果key使用的是bigint，则为8字节，指针在mysql中为6字节，一共是14字节，则16k能存放 16 * 1024 / 14 = 1170 个索引指针。于是可以算出，对于一颗高度为2的B+树，那么它有1170个叶子节点存储数据，每个叶子节点可以存储16条数据，一共 1170 x 16 = 18720 条数据。
  7. 而对于高度为3的B+树，就可以存放 1170 x 1170 x 16 = 21902400 条数据（两千多万条数据），也就是对于两千多万条的数据，我们只需要高度为3的B+树就可以完成，通过主键查询只需要3次IO操作就能查到对应数据。所以在 InnoDB 中B+树高度一般为3层时，就能满足千万级的数据存储，所以一个节点为1页，也就是16k是比较合理的。

MySQL索引的实现

MyISAM
  1. MyISAM中的主键索引和辅助索引存储的结构是一样的，因为MyISAM中数据和索引是分两个文件存储的（.myd数据文件）（.myi索引文件），它叶子节点上存储的是数据的磁盘地址。

MySQL索引篇 - 图7

InnoDB
  1. InnoDB中的主键索引树叶子节点上存储的是数据，这些数据实际上是一个双向链表，每一个节点上都有一个双向指针。
  3. 而辅助索引树上其实存储的是数据的主键，如果查询命中的是辅助索引，那么在没有使用联合索引的情况下，找到数据后，会拿着数据的主键去主键索引树上找数据，这种现象又叫回表现象。

聚集索引

聚集索引树上存储的是数据

MySQL索引篇 - 图8

辅助索引

辅助索引树上存储的是数据的主键

MySQL索引篇 - 图9

MySQL索引篇 - 图10

索引创建原则

创建索引的场景

  1. 当表的数据量比较大的时候。换句话说就是查询性能比较差的时候。
  2. 读大于写，或者读写差不多的时候。也可以根据实际业务场景权衡有一些写多读少的表是否真的需要创建索引。
  3. 查询条件频繁出现在Where条件中，或者Order By ，Gourp By中

索引带来的问题

  1. 创建索引就会有索引文件，有索引文件就意味着每一次的写都需要对这个索引文件进行维护，因为索引的本质它就是一颗树的数据结构，当发生写操作的时候它要不断的根据数据来调整这颗树上存储的数据结构。也就是说表的写操作会受到影响。
  2. 过多的创建索引会占用过多的磁盘空间。

EXPLAIN SQL执行计划

MySQL索引篇 - 图11

id

  1. 查询的序号，包含一组数字，表示查询中执行select子句或操作表的顺序

select_type

  1. 查询类型，主要用于区别普通查询，联合查询，子查询等的复杂查询
  3. 1. simple：简单的select查询，查询中不包含子查询或者UNION
  4. 2. primary：查询中若包含任何复杂的子部分，最外层查询被标记
  5. 3. subquery：在select或where列表中包含了子查询
  6. 4. derived：在from列表中包含的子查询被标记为derived（衍生），MySQL会递归执行这些子查询，把结果放到临时表中
  7. 5. union：如果第二个select出现在UNION之后，则被标记为UNION，如果union包含在from子句的子查询中，外层select被标记为derived
  8. 6. union result：UNION 的结果

table

  1. 当前所用到的表

type

  1. 1、system：表中仅有一行（=系统表）这是const联结类型的一个特例。
  2. 2、const：表示通过索引一次就找到，const用于比较primary key或者unique索引。因为只匹配一行数据，所以如果将主键置于where列表中，mysql能将该查询转换为一个常量
  3. 3、eq_ref:唯一性索引扫描，对于每个索引键，表中只有一条记录与之匹配。常见于唯一索引或者主键扫描
  4. 4、ref:非唯一性索引扫描，返回匹配某个单独值的所有行，本质上也是一种索引访问，它返回所有匹配某个单独值的行，可能会找多个符合条件的行，属于查找和扫描的混合体
  5. 5、range:只检索给定范围的行，使用一个索引来选择行。key列显示使用了哪个索引，一般就是where语句中出现了between,in等范围的查询。这种范围扫描索引扫描比全表扫描要好，因为它开始于索引的某一个点，而结束另一个点，不用全表扫描
  6. 6、index:index 与all区别为index类型只遍历索引树。通常比all快，因为索引文件比数据文件小很多。
  7. 7、all：遍历全表以找到匹配的行

possible_keys

  1. 代表使用了那些索引找到当前数据

key

  1. 当前使用到的索引

key_len

  1. 表示索引中使用的字节数长度

ref

  1. 列与索引的比较，表示上述表的连接匹配条件，即哪些列或常量被用于查找索引列上的值

rows

  1. 扫描的行

Extra

  1. 包含不适合在其他列中显示，但是十分重要的额外信息
  2. 1、Using filesort：说明mysql会对数据适用一个外部的索引排序。而不是按照表内的索引顺序进行读取。MySQL中无法利用索引完成排序操作称为“文件排序”
  3. 2、Using temporary:使用了临时表保存中间结果，mysql在查询结果排序时使用临时表。常见于排序order by和分组查询group by。
  4. 3、Using index:表示相应的select操作用使用覆盖索引，避免访问了表的数据行。如果同时出现using where，表名索引被用来执行索引键值的查找；如果没有同时出现using where，表名索引用来读取数据而非执行查询动作。
  5. 4、Using where :表明使用where过滤
  6. 5、using join buffer:使用了连接缓存
  7. 6、impossible where:where子句的值总是false，不能用来获取任何元组
  8. 7、select tables optimized away：在没有group by子句的情况下，基于索引优化Min、max操作或者对于MyISAM存储引擎优化count（*），不必等到执行阶段再进行计算，查询执行计划生成的阶段即完成优化。
  9. 8、distinct：优化distinct操作，在找到第一匹配的元组后即停止找同样值的动作。

SQL执行顺序

假设一条SQL语句时这样

  1. select distinct 
  2.         <select_list>
  3. from
  4.     <left_table><join_type>
  5. join <right_table> on <join_condition>
  6. where
  7.     <where_condition>
  8. group by
  9.     <group_by_list>
  10. having
  11.     <having_condition>
  12. order by
  13.     <order_by_condition>
  14. limit <limit number>

SQL执行顺序

  1. 1、from <left_table><join_type>
  2. 2、on <join_condition>
  3. 3、<join_type> join <right_table>
  4. 4、where <where_condition>
  5. 5、group by <group_by_list>
  6. 6、having <having_condition>
  7. 7、select
  8. 8、distinct <select_list>
  9. 9、order by <order_by_condition>
  10. 10、limit <limit_number>