Mysql-高性能索引

索引一种数据结构，其目的是为了更快的查询数据，在数据量很大的表中，建立良好的索引能够提升极大的性能。

磁盘io与预读

因为数据库存储数据量大，是不可能存储在内存中以供查询的，所以对于数据的查询必然会跟磁盘打交道，所以只有了解了磁盘io和预读的基本知识，我们才能真正的理解索引的原理。

磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分，寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms；传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。那么访问一次磁盘的时间，即一次磁盘 IO的时间约等于5+4.17 = 9ms左右，听起来还挺不错的，但要知道一台500MIPS的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO。

索引的数据结构

之前说到了磁盘读取数据的方式，那么我们的索引是如何配合这个方式更快的搜索到数据呢？首先，我们要了解索引的数据结构。我们这里讲到的索引B+TREE的索引，因为这个索引我们最常用，实际上索引还有哈希索引，空间数据索引，全文索引。

首先我们来理解B+TREE的数据结构： B+Tree是一种多路搜索树（并不是二叉的）：

定义任意非叶子结点最多只有M个儿子；且M>2；
根结点的儿子数为[2, M]；
除根结点以外的非叶子结点的儿子数为[M/2, M]；
每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
非叶子结点的关键字个数=指向儿子的指针个数-1；
非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于等于K[M-1]的子树，其它P[i]指向关键字属于[K[i], K[i+1])的子树；
所有叶子结点位于同一层；
为所有叶子结点增加一个链指针；
所有关键字都在叶子结点出现；如图，是一个M为3的B-TREE

B+的特性：

所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
不可能在非叶子结点命中；
非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
更适合文件索引系统；

B+TREE索引性能分析：

B+TREE的深度最多是O(log[M/2]N)，在路径上的每个节点需要用O(logM)s时间复杂度来确定是哪个分支（使用二分查找），inset和delete可能需要O(M)的工作量来调整该节点上的所有信息，所以insert和delete的运行时间最坏情况是O(Mlog[M]N),而每次的查询只需要花费O(logN)。从刚刚的时间复杂度可以看出当在内存中查询时，Mzuihaode选择是3或者4，再增大时速度就会增加。但是我们的数据存储是在磁盘中的，相比读取一个存储器所花费的时间，M增大所增加的时间花费不值一提。此时M的值选择为使得一个内部节点能够装入一个磁盘区块的最大值，所以M取值范围为[32,256],这样当一片树叶上元素是满的，而且树叶是满的那么硬盘上一个区块就被装满了。这样意味着，一个记录总可以在很少的磁盘访问中被找到，因为此时B树深度只有2或3，而根可以直接加载到内存中，所以整个访问速度就会很快。

所以我们再来看上图：如果要查找数据项30，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在28和65之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，30在28和35之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到 30，结束查询，总计三次IO。真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。

高性能的索引策略

独立的列

有些查询不当的使用索引，使得Mysql无法使用已有的索引。比如查询中列不是独立的，则Mysql不会使用索引。独立的列指的是：索引不能是表达式的一部分，更不能是函数的参数，例如：

select app_id from app where app_id + 1 = 5;

MySQL无法解析app_id + 1这个表达式，所以无法使用索引。

前缀索引和索引选择性

有时候索引的字段特别的长，这会让索引变得又大又慢。这种情况可以通过只取出字段前面几个字符来做索引，这样可以节约索引空间，从而提高索引的效率，但是这样会减少索引的选择性。索引的选择性，指的是不重复的索引值（基数）跟数据表的总数的比值。索引选择性越高查询的效率就越快，因为这样索引能帮助Mysql查找时过滤掉更多的行。比如主键和唯一索引，这种时候性能最好。所以在选择索引长度时要同时考虑索引选择性才能达到性能最优化。

多列索引

大多数对于索引理解不够的，所以容易犯以下两个：

为很多个列创建独立索引。在多个列上建立单独索引并不能提高Mysql的查询性能。5.0以后的Mysql引入了“索引合并”的策略，这样可以多个单列索引就行扫描，并将结果进行合并。这种算法有三种变形： OR条件联合，AND条件相交。这种情况下，合并结果会耗用大量的CPU，而且这个优化过程不计入“查询成本”中。所以这些成本会被低估，有时候效率甚至低于全盘扫描，而且容易导致优化的时候注意不到这个点。
创建多列索引的顺序有误。查询的时候没有按照索引的顺序来查询，也会导致Mysql无法使用索引。在创建多列索引的时候有一些有用的原则：在不考虑排序和分组的情况下，将选择性最高的列放在前面。但是很多时候这样用也未必是好的，还是要根据具体的情况来判断。

聚簇索引

聚簇索引并不是一个单独的索引形式，而是Mysql在B+TREE索引上的数据存储形式。InnoDB的聚簇索引实现就是在统一结构里面保存了B+TREE索引和数据行如图：

聚簇索引有时候对性能很有帮助，但有时候也对性能造成严重的问题。下面我们用几张图来分辨下非聚簇索引的表和聚簇索引的表的区别：

非聚簇索引表的数据如上图

非聚簇索引表的主键索引图

聚簇索引的主键索引图

从上面几张图可以看出，非聚簇索引表的主键索引跟普通的索引没有区别，他直接就是索引里有个指向数据所在指针的形式，但是聚簇索引表的主键索引“就是”一张表，所以不需要非聚簇索引表那样数据的独立行储存。我们直接来看两者的对比图：

了解了他们的区别我们接着来讨论聚簇索引的优点：

可以把相关数据保存在一起，查询时只需在磁盘读取少数数据页就能获得所有的所需数据。
数据访问速度快，因为数据和索引在一起所以查询起来很快。
使用覆盖索引扫描的查询可以直接使用叶节点的主键值。二级索引（辅助索引）使用主键作为"指针" 而不是使用地址值作为指针的好处是，减少了当出现行移动或者数据页分裂时辅助索引的维护工作，使用主键值当作指针会让辅助索引占用更多的空间，换来的好处是InnoDB在移动行时无须更新辅助索引中的这个"指针"。也就是说行的位置会随着数据库里数据的修改而发生变化（后面缺点处会讲到B+树节点分裂以及页分裂），使用聚簇索引就可以保证不管这个主键B+树的节点如何变化，辅助索引树都不受影响。

下面我们来看看聚簇索引的缺点：

聚簇索引在数据都放在内存中的数据毫无优势。
插入速度在按照主键顺序插入的时候影响不大，但不按照顺序加入的时候，速度会受到影响而且插入后要使用optimize table优化一下表，能更新索引统计数据并释放成簇索引中的未使用的空间。
更新聚簇索引的成本很高，因为InnoDB会强制将每个被更新的行移动到新的位置上。
基于聚簇索引的表插入新行，或者主键被更新导致需要移动行时，可能面临“页分裂的问题”。当该行插入到一个某个已经满了的页的时候，存储引擎会将页分裂成两个页面来容纳该行，这样的页分裂操作会导致表占用更多空间。而且这样会造成数据存储不连续，行比较稀疏的问题，也会导致全盘扫描变慢。页分裂还会造成大量数据的移动，一次插入至少修改到3个页。而顺序插入的时候，很少遇到需要大量修改页的情况，最大的性能瓶颈就在自动增减主键的时候锁的开销。如图：
顺序添加
插入无序值的时候
二级索引（辅助索引）可能比想象的要大，因为二级索引叶子节点包含了引用行主键的列。而且二级索引需要两次查找。

覆盖索引

覆盖索引指的是包含了一个查询所有需要查询字段的值。覆盖索引是一个非常有用的工具，能够极大的提升效率，因为索引的叶子节点已经包含了所有需要的数据，无需再去读取数据行。其优点如下：

索引条目比起数据行要小得多，所以如果只需要读取索引，那MySQL就能极大的减少数据访问量。
因为索引是按照列值顺序存储的，所以对于IO密集型的范围查询，只查找索引就会比去硬盘中随机查询每一行数据快得多。
数据库引擎（如MyISAM）在内存中只缓存索引，数据缓存依赖于操作系统缓存，因此访问数据需要系统调用，这个会造成严重的性能问题。
上面说的聚簇索引，覆盖索引的时候就特别有用了。

因为覆盖索引是索引中存储了列的值，所以覆盖索引的适用范围仅适用于B+TREE的时候.

索引扫描来做排序

扫描索引本身很快，因为只需要一条索引记录移动到下一条索引记录就行了。但是如果索引不能覆盖查询的所有列，那就只能每一条索引记录都要去查询一次对应的行。这基本上都是随机IO,所以按索引顺序读取数据的速度反而要比顺序的全表扫描慢，尤其是IO密集型的工作负载时。只有当索引的列顺序和order by的字句顺序完全一致，并且所有列的排序方向（正序倒序）都一样时，Mysql才能使用索引来对结果做排序。当然如果最左前缀在where条件中已经是一个常量了，可以不用满足最左前缀的order by子句。

索引和锁

索引可以让查询锁定更少的行。比如之前我们遇到过得for update语句如果用了主键的索引，那么就只锁定一行，而其他的就会锁表。还有很多情况查询的时候只锁定索引查出来的行，这样的话能减少很多锁的开销。还有个InnoDB的细节需要注意： InnoDB在二级索引（辅助索引）上用的是共享锁（读锁），但是访问主键索引就用的是排他锁（写锁）（其实也就是之前我们工作中遇到的那个用主键的索引就是行锁，但是其他索引就是表锁）。这种情况就没法使用之前讲到的覆盖索引（二级索引访问主键索引），并且使用 for update 比share in share mode或非锁定查询要慢得多。

一些微小的建议

数据库的优化是一个非常重要的工作，很多时候不能犯教条主义错误，最主要的方式还是要通过自己操作来验证到底该如何优化。很可能一次优化在100M的数据量的时候起作用了，但是1G的时候又会变成慢查询，这种情况就要去思考如何才能避免再出这样的问题。数据库可以存储一些历史数据作为记录，但是大多数情况我们需要的是最近的数据或者是少数的几个热数据，这种情况下就需要用高速缓存的方式来完成这方面的工作，而不是一味的只用数据库。这才设计构思的时候很重要。还有索引不是万能的，千万不要乱建索引，有时候还会造成速度变得更低，而且还浪费了空间，再建立索引的时候也要好好思考一下这个索引的必要性和用处。另外优化慢查询有时候也未必非要加索引，很多时候通过一些语句的构造也能实现优化的目的。以上内容主要来自我之前阅读的一本书籍《高性能MySQL》，配合一些算法知识再加上我自身的一些经验，写在这里只是起到抛砖引玉的作用，数据库优化的路还很长，坑还很多，希望与大家一起学习，共同进步。