Mysql底层原理与性能调优

在工作中，公司就线上生产环节，有没有时常碰到过一些慢SQL查询，那我相信大多时候第一时间想到的优化策略，我相信肯定就是索引，可能第一时间就会想到，看一下SQL是不是有加合适的索引，它的条件里面是不是所有的条件都正常的走了我们索引，有的时候你SQL里面有索引，但是它并不一定走了这条索引，如果说我原来一条复杂的SQL语句，如果查询条件里面没有没有涉及到索引字段的查询，或者说没有走合适的索引他可能要查的非常慢，但是一旦你加了合适的索引，where语句条件也走了合适的索引，你会发现你的SQL瞬间查询效率会提高很多倍，原来可能几十秒，你加了索引之后，它的执行时间可能也就几百毫秒，甚至几十毫秒。

原理

索引是帮助MySQL高速获取数据的排好序的数据结构。
数据结构有很多种，比方说二叉树，红黑树，哈希表，B-Tree等。
数据结构：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
请添加图片描述

这里举一个简单的例子，有上图这样一个简单的表，假设这个表的字段值是唯一的值。
如果我们要查询下面这条SQL语句：

SELECT * FROM COl2=89

如果我这张表不加任何索引，那会把这张表的所有数据，从第一行开始查，一行行去查对不对，查找了这一行，查找到这一行数据查出来之后，然后再跟再把这一行数据的COl2这个字段拿出来，跟我要查找的条件比对一下，如果相同，说明是已经查到了。当然后面还有其他的值，他肯定还会往下去查找。
刚刚这个SQL要至少经过六次查找才能查到我们要查找的结果。

如果我把这张表的COl2建立了一个索引，索引本质底层是一个数据结构。

二叉树

比方说先拿二叉树来举例，这个二叉树的结构大概就是每个节点里面可能存储的一个key-value ，Key它可以存储的是我们这个这一列数据的索引的值， value存储这个索引所在那一行数据对应的物理磁盘的地址指针。
现在，查询上面这个SQL，发现COl2就是我的索引列，索引列已经维护到二叉树，二叉树里面去查找了，从根结点开始查找，经过两次查找就能查到我们要查找的结果。
感觉二叉树查找次数至少缩减了一半，但是假如我再COl1上添加索引？如下图：
请添加图片描述
发现这种情况它并不能加快查询速度。

平衡二叉树(AVL)

AVL树是严格的平衡二叉树，所有节点的左右子树高度差不能超过1；AVL树查找、插入和删除在平均和最坏情况下都是O(logn)。
请添加图片描述
AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要1次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(logn)。
由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。

红黑树

与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡：只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。从实现来看，红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一，且节点颜色的划分需要满足特定的规则。红黑树示例如下：
请添加图片描述
因此，在实际应用中，AVL树的使用相对较少，而红黑树的使用非常广泛。例如，Java中的TreeMap使用红黑树存储排序键值对；Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时，使用链表，当冲突节点较多时，使用红黑树)。
对于数据在内存中的情况（如上述的TreeMap和HashMap），红黑树的表现是非常优异的。但是对于数据在磁盘等辅助存储设备中的情况（如MySQL等数据库），红黑树并不擅长，因为红黑树长得还是太高了。当数据在磁盘中时，磁盘IO会成为最大的性能瓶颈，设计的目标应该是尽量减少IO次数；而树的高度越高，增删改查所需要的IO次数也越多，会严重影响性能。
假设我这张表有500万行数据，我这个红黑树的存储的高度没有具体计算假设就20左右。假设我要查找的那个索引的数据刚好就在叶子节点，经过20次的索引查找，说白了就是跟磁盘做了20次的磁盘IO，大家都知道一次磁盘IO性能是非常非常低的，那查询性能也就不会很好。

B-Tree

那么，我们想减少磁盘IO，控制它的树的高度，如果让高度小于等于五？
那我是不是可以对这红黑树做一点改造，什么改造，我把这一个节点一开始在分配这个节点放索引的时候，我把这个节点的存储大小弄大一点，这个节点就可以放更多的索引元素，我放了更多的索引元素之后，它就可以分更多的叉，然后每分的一个叉的下面的一个子节点一样的也分配这么大……
改造之后的这一棵树的多叉树的结构，存储同样的一千万行数据，改造之后的这个树结构，它的树的高度会小得多，具体的数的高度是有能够是几的话，是根据你这个横向能存储元素多少，横向能存储越多的元素，树的高度越小。

这个结构实际上就是B-Tree。
请添加图片描述
但是我们MySQL的底层，也不是用的B-Tree来存储，而是对B-Tree做了一点点改造，也就是B+Tree。

B+Tree

B+树也是多路平衡查找树，其与B树的区别主要在于：

B树中每个节点（包括叶节点和非叶节点）都存储真实的数据，B+树中只有叶子节点存储真实的数据，非叶节点只存储键。在MySQL中，这里所说的真实数据，可能是行的全部数据（如Innodb的聚簇索引），也可能只是行的主键（如Innodb的辅助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。
B树中一条记录只会出现一次，不会重复出现，而B+树的键则可能重复重现：一定会在叶节点出现，也可能在非叶节点重复出现。
B+树的叶节点之间通过双向链表链接。适合于范围查询
B树中的非叶节点，记录数比子节点个数少1；而B+树中记录数与子节点个数相同。
由此，B+树与B树相比，有以下优势：
更少的IO次数：B+树的非叶节点只包含键，而不包含真实数据，因此每个节点存储的记录个数比B数多很多（即阶m更大），因此B+树的高度更低，访问时所需要的IO次数更少。此外，由于每个节点存储的记录数更多，所以对访问局部性原理的利用更好，缓存命中率更高。
更适于范围查询：在B树中进行范围查询时，首先找到要查找的下限，然后对B树进行中序遍历，直到找到查找的上限；而B+树的范围查询，只需要对链表进行遍历即可。
更稳定的查询效率：B树的查询时间复杂度在1到树高之间(分别对应记录在根节点和叶节点)，而B+树的查询复杂度则稳定为树高，因为所有数据都在叶节点。

你的数据表有一千万，甚至有几千万行数据，用B加树来存储，他的树的高度可能也就三，或者说四。
注意它的索引来源，索引元素都是实际上都是存储在我们的叶子节点的，也就是所有的元素都是在叶子节点有一份完整的存储。

刚才不是说了吗，对这个节点横向做文章，让他横向能存储更多的元素，就可以减少它的树的高度。那是不是我把一张数据库表的所有的所有的索引元素全部放到这一个节点上面，不那树的高度就一，那要查找一个索引元素，那就简单了？
如果数据比较少的话还好，如果你有几千万行的数据，你想一下，全部存储了一个节点上面得多大，几百兆甚至几个G，你一次查找你要load几个G的数据到内存里面，你觉得合适吗?内存里面的资源本来就很宝贵，我要查一条索引的元素记录，直接把整个索引表的索引全部加载到内存，是不是浪费。一张大表里面的数据，我们最常用的可能也就20%的数据，一上来就把整张表，全部load到内存里面，合适吗。

这个节点的大小，实际上是有限制的。
MySQL把这个节点大概设置了大概是16K。查询SQL：

SHOW GLOBAL STATUS LIKE 'Innodb_page_size';

请添加图片描述
为什么这个非叶节点它不存储数据，就是这个data元素为什么都要挪到了叶子结点？
每一个节点大小已经设置死了，假设它大小是有固定大小的，这个data这个元素它肯定占磁盘大小，把data元素挪到叶子节点上，可以空出来更多的非叶节点的存储空间，那非叶节点就可以在横向上面就可以存储更多的索引元素，树的高度就可以更小。
比方说有一个主键索引，是常用整型的字段bigint，bigint在mysql那边占八个字节，旁边这个指针MySQL在底层源码上面是给他分配的是六个字节。在这个非叶结点里面，要存储一个索引大概要花费14个字节存储空间，那么一个非叶节点可以存储的索引元素个数就是16384/14，大概是1170，叶子节点要存储data，假设一条数据大小1kb，那么一个叶子节点可以存储16个数据，那么一个3层的树大概可以存储1170117016条数据，也就是一个3层树存储满了大概可以存2000多万个元素。
把这个节点一次性load内存里面去然后在内存里面去比对。把这个节点load到内存之后，在内存里面去查找比对我这个元素速度是非常快的，基本上这个时间可以忽略不计。
所以，即便你是两千万，甚至三千万、四千万行的数据表，只要合适的走了索引，他的查找速度依然很快。

这里先穿插说下Hash表
我们经常在去设计MySQL表的时候，去建索引的时候，都会发现有个索引方法，一个是BTREE，一个是HASH。
请添加图片描述

MySQL索引底层既可以用BTREE，也可以用HASH。用HASH时有一张哈希表，哈希表里面存储的就是我们的索引元素对应的哈希结果值，这个哈希结果值实际上就对应了我们这一行数据的那个磁盘文件地址。

现在把上面这张表的COL1作为索引，并且这个索引我用的是哈希做存储结构。那我们在查找SELECT * FROM COl1=6这条语句时，MySQL底层做了些什么事情呢？
大概会先把COl1的这个结果值6做一次哈希计算，得到一个字符串，那这一个字符串它实际上就跟我们的这一行数据，这个6索引所在哪行数据的磁盘文件地址指针，有个映射关系。
这种哈希索引建立的方式，哪怕是千万级别的表，不管你这张表你查哪一个数据元素，查哪一个索引字段值，哪怕你查这张表的最后一行元素，你会发现查找的过程都是只要把那个索引的元素做一次哈希计算，基本上就能够拿到我这一行元素对应的那个磁盘文件，哪怕是你这张表的数据是亿级别的，都只要经过一次哈希运算，就能够查找到我们这一行数据对应的磁盘文件指针。

HASH这种方式查找性能更高，但我们真正在工作中使用MySQL，99%以上的场景都是使用的BTREE。因为加入我要查询语句：SELECT * FROM COl1>6，HASH索引就没法快速的定位到我所要的结果集。不使用范围查找的话，日常工作中的很多业务功能实现起来可能会巨复杂。

再看B+Tree，他在B-Tree的基础上，叶子节点之间多了一个顺序访问指针。
这个指针就是MySQL在维护底层索引的时候，他会在这个节点的末尾有一个指针，指针指向下一个节点的磁盘文件地址。
比如说：SELECT * FROM column>20
假设我这个column现在就是索引元素，并且用BTREE来维护，先快速根据根节点查找，先定位到我们20个元素，查找的是大于20，这个20的右边的这些元素，都是我要查找的结果集。就可以顺藤摸瓜，顺着这么一个指针，把这个节点load出来，接着顺着这个指针，把下一个节点颜load出来，就可以按照这个指顺序的指针，从左到右依次把20后面的所有元素全部一次性顺藤摸瓜全部load出，load出来放到我这个结果集里面去。范围查找非常快，不用每次把这个节点load了出来之后，又要回到根结点。

存储引擎

请添加图片描述
在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

MyISAM索引实现

请添加图片描述
索引文件和数据文件是分离的（非聚集）。
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

请添加图片描述
在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。所以辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

索引检索过程入下图：
请添加图片描述

为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
以 InnoDB 作为存储引擎的表，表中的数据都会有一个主键，如果没有定义主键，InnoDB 会选择一个唯一的非空索引代替。如果没有这样的索引，InnoDB 会隐式定义一个主键来作为聚簇索引。
知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

经常看到有帖子或博客讨论主键选择问题，有人建议使用业务无关的自增主键，有人觉得没有必要，完全可以使用如学号或身份证号这种唯一字段作为主键。不论支持哪种论点，大多数论据都是业务层面的。如果从数据库索引优化角度看，使用InnoDB引擎而不使用自增主键绝对是一个糟糕的主意。
上文讨论过InnoDB的索引实现，InnoDB使用聚集索引，数据记录本身被存于主索引（一颗B+Tree）的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。
如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。如下图所示：
请添加图片描述
这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置：
请添加图片描述

此时MySQL不得不为了将新记录插到合适位置而把数据页分割为两个数据页。出现页分裂时，需要将一个页的记录移动到另外一个页，性能会受到影响，同时页空间的利用率下降，造成存储空间的浪费。，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
因此，只要可以，请尽量在InnoDB上采用自增字段做主键。

为什么InnoDB非主键索引结构叶子节点存储的是主键值？
一致性和节省存储空间

索引优化

高效使用索引的首要条件是知道什么样的查询会使用到索引，这里先说一下联合索引的概念。在上文中，我们都是假设索引只引用了单个的列，实际上，MySQL中的索引可以以一定顺序引用多个列，这种索引叫做联合索引，一般的，一个联合索引是一个有序元组<a1, a2, …, an>，其中各个元素均为数据表的一列。另外，单列索引可以看成联合索引元素数为1的特例。
假设我们有个表employees.titles表为例，titles表的主索引为<emp_no, title, from_date>。
请添加图片描述

尽量全值匹配

SELECT * FROM employees.titles WHERE emp_no='10001' AND title='Senior Engineer' AND from_date='1986-06-26';

很明显，当按照索引中所有列进行精确匹配（这里精确匹配指“=”或“IN”匹配）时，索引可以被用到。这里有一点需要注意，理论上索引对顺序是敏感的，但是由于MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引，例如我们将where中的条件顺序颠倒：

SELECT * FROM employees.titles WHERE from_date='1986-06-26' AND emp_no='10001' AND title='Senior Engineer';

效果是一样的。
当查询条件精确匹配索引的左边连续一个或几个列时，如<emp_no>或<emp_no, title>，所以可以被用到，但是只能用到一部分，即条件所组成的最左前缀。

最佳左前缀法则

SELECT * FROM employees.titles WHERE emp_no='10001' AND from_date='1986-06-26';

此时因为title未提供，所以查询只用到了索引的第一列，而后面的from_date虽然也在索引中，但是由于title不存在而无法和左前缀连接，因此需要对结果进行扫描过滤from_date。如果想让from_date也使用索引而不是where过滤，可以增加一个辅助索引<emp_no, from_date>，此时上面的查询会使用这个索引。除此之外，还可以使用一种称之为“隔离列”的优化方法，将emp_no与from_date之间的“坑”填上。
在成为“坑”的列值比较少的情况下，可以考虑用“IN”来填补这个“坑”从而形成最左前缀：

SELECT * FROM employees.titles WHERE emp_no='10001' AND title IN ('Senior Engineer', 'Staff', 'Engineer', 'Senior Staff', 'Assistant Engineer', 'Technique Leader', 'Manager') AND from_date='1986-06-26';

当然，如果title的值很多，用填坑就不合适了，必须建立辅助索引。
语句SELECT * FROM employees.titles WHERE from_date=‘1986-06-26’;由于不是最左前缀，所以这样的查询显然用不到索引。

范围条件放最后（是指索引定义顺序的最后）

SELECT * FROM employees.titles WHERE emp_no < '10010' and title='Senior Engineer';

范围列可以用到索引，但是范围列后面的列无法用到索引。同时，索引最多用于一个范围列，因此如果查询条件中有两个范围列则无法全用到索引。

不在索引列上做任何操作

SELECT * FROM employees.titles WHERE emp_no - 1='10000';

如果查询条件中含有函数或表达式，则MySQL不会为这列使用索引。

尽量使用覆盖索引

覆盖索引是指 SQL 中 query 的所有字段，在索引 B+Tree 的叶子节点上都能找得到的那些索引，从二级索引中查询得到记录，而不需要通过聚簇索引查询获得，可以避免回表的操作。使用覆盖索引的好处就是，不需要查询出包含整行记录的所有信息，也就减少了大量的 I/O 操作。尽量避免 select *。

前缀索引

有一种与索引选择性有关的索引优化策略叫做前缀索引，就是用列的前缀代替整个列作为索引key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时因为索引key变短而减少了索引文件的大小和维护开销。

ALTER TABLE employees.employees ADD INDEX `first_name_last_name4` (first_name, last_name(4));

假设这时选择性已经很接近<first_name, last_name>了，而这个索引的长度只有18，比<first_name, last_name>短了接近一半。
前缀索引兼顾索引大小和查询速度，但是其缺点是不能用于ORDER BY和GROUP BY操作，也不能用于Covering index（即当索引本身包含查询所需全部数据时，不再访问数据文件本身）。

不等于要慎用

在使用不等于（!= 或者<>），会导致索引失效。

NULL和Not NULL要慎用

在字段为NOT NULL的情况下，如果使用 is null 或者 is not null，会导致索引失效。
在字段为可以为NULL的情况下，使用IS NULL，索引正常；使用 IS NOT NULL，则索引失效。

LIKE查询要当心

like以通配符开头(‘%abc…’)mysql索引失效会变成全表扫描的操作。(‘abc%’)则可以使用索引，类似遵循最左前缀原则。

OR改UNION效率高

除了索引优化之外，还有一些查询优化的技巧，例如：当查询结果只可能为1条数据的时候，加上LIMIT 1可以增加性能，MySQL数据库引擎会在找到一条数据后停止搜索，而不是继续往后查少下一条符合记录的数据。本文主要讲索引相关，就不详细展开了。

索引选择性

既然索引可以加快查询速度，那么是不是只要是查询语句需要，就建上索引？答案是否定的。因为索引虽然加快了查询速度，但索引也是有代价的：索引文件本身要消耗存储空间，同时索引会加重插入、删除和修改记录时的负担，另外，MySQL在运行时也要消耗资源维护索引，因此索引并不是越多越好。一般两种情况下不建议建索引。
第一种情况是表记录比较少，例如一两千条甚至只有几百条记录的表，没必要建索引，让查询做全表扫描就好了。
另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性（Selectivity），是指不重复的索引值（也叫基数，Cardinality）与表记录数（#T）的比值：
Index Selectivity = Cardinality / #T
显然选择性的取值范围为(0, 1]，选择性越高的索引价值越大，这是由B+Tree的性质决定的。