mysql学习之优化总结(2)--索引的那些事

一、前言

上一篇文章我们在研究MySQL查询过程的查询优化步骤中提到过优化索引可以优化查询优化的过程，索引到底是什么？它在查询过程中是一个怎样的角色？索引适用于什么场景？我们怎么用好它呢，这一节我们一起来深入了解下索引，理解索引相关的数据结构和算法，理解它的原理，帮助我们更好的使用索引。

二、概念

索引是对数据库表中一个或多个列的值进行排序的结构。

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。

三、索引的产生

1、为什么需要索引？索引是怎样产生的？

我们先来看看没有索引时数据的查询过程：

如下图，数据库中的磁盘空间被分为很多不同的block(块)，这些块的大小相同，数据是以Row为单位存放在磁盘上的块里。

数据库磁盘结构

当我们要定位一条userid为0234的数据时, 查询语句为：

select * from user where userid= 0234

为了找出满足条件的查询，数据库管理器必须扫描account表中的所有行，需要扫描磁盘中所有的block，一行一行的进行数据匹配，效率极低，时间复杂度为O(N)。这会向缓冲池调入大量的数据页，需要大量的磁盘IO操作，执行大量I/O操作无疑是非常影响性能的。

要怎样减少查找数据时磁盘的IO操作呢？

在数据存储不能减小的情况下，最有效的办法是减少读取数据的总量。而在上面定位一条数据时：

1、我们读出了所有块的所有row数据，大部分row是无用数据，加大了IO操作；

2、我们读出了一个row中所有列的数据，然而我们根据userid定位时只是和一列数据对比，其他的也是无用数据，也增大了IO的消耗。

2、索引诞生之初--Dense Index（稠密索引） 以空间换时间

上图中第一列为userid，当查找userid为xxx的记录时，并不需要匹配整行数据。而是只匹配userid一列的值就行了。

当进行定位操作时，不再进行表扫描。而是进行索引扫描，依次读出所有的索引块，进行键值的匹配。当找到匹配的键值后，根据该行的指针直接读取对应的数据块，进行操作。

假设1block = 100row ,1row = 10column

100万行数据需要1万block

Dense索引占用空间 = 1万*1/10 = 1000block

结果：大约磁盘1/10的额外存储空间换来了大约全表扫描10倍的效率。

3、索引的进化 --Sparse Index（稀疏索引）

Dense Index的效率仍然较低，能不能继续减少IO操作的次数？

如下图继续对dense index升级：

1. 对Dense Index排序
2. 排序后读出每个块后只需要和第一行的键值匹配，就可以决定下一个块的寻找方向。 因此有效数据是每个块的第一行的数据。还是根据减少无效数据IO的原则，将每一个块的第一行的数据单独拿出来存起来，并且指向原索引数组块的地址。我们只需要在新的索引数组里进行二分查找就可以尽快找到dense index地址。至于在新索引数组里二分查找的性能消耗我们后面介绍。

parse index 存储结构和dense index完全一样。

假设存储100row,之前已有的1000block的dense index需要10个block.那我们查找一条数据的需要查询的block数 = 10（sparse index）block + 1(dense index)block +1数据block = 12block。大大降低了读取数据所需的IO读取操作。

我们仍然可以对第一次sparse index再建一层sparse index，这样就形成了一颗树型，读取block会更少，这样已经形成了mysql经典索引结构B+树的雏形，后面详细介绍。

四、索引的数据结构

Dense Index它实际就是一个顺序存储，时间复杂度为O(n)。

排序+更优的查找算法

1)二分查找

比顺序查找更快的就是二分查找了，时间复杂度为O(logn)。

2)二叉树查找

O(Log2n)

索引是以文件的形式存储在磁盘上的，查找过程中要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级。如果一个数据量巨大，为它在磁盘中存储一棵二叉树索引深度是巨大的，将这么大深度的一颗二叉树放磁盘上，每读取一个节点，需要一次磁盘的I/O读取，整个查找的耗时显然是不能够接受的。那么如何减少查找过程中的I/O存取次数？

一个有效的解决方法是减少树的深度，将二叉树变为n叉树。

3)B-树与B+树

B-树示例：

B-树

例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)，B-Tree是一个非常有效率的索引数据结构。

B+树示例：

B+树

B+Tree是BTree的一个变种，B+Tree和BTree的不同主要在于：

• B+Tree中的非叶子结点不存储数据，只存储键值；
• B+Tree的叶子结点没有指针，所有键值都会出现在叶子结点上，且key存储的键值对应的数据的物理地址；

一般来说B+Tree比BTree更适合实现外存的索引结构，因为存储引擎的设计专家巧妙的利用了外存（磁盘）的存储结构，即磁盘的一个扇区是一个page（页）的整数倍，页是存储中的一个单位，索引结构的节点被设计为一个页的大小，然后利用外存的“预读取”原则，每次读取的时候，把整个节点的数据读取到内存中，然后在内存中查找，已知内存的读取速度是外存读取I/O速度的几百倍，那么提升查找速度的关键就在于尽可能少的磁盘I/O，那么可以知道，每个节点中的key个数越多，那么树的高度越小，需要I/O的次数越少；

因此一般来说B+Tree比BTree更快，因为B+Tree的非叶节点中不存储data，就可以存储更多的key。

4) 磁盘存取原理

索引以文件形式存储在磁盘上，索引检索需要磁盘I/O操作

磁盘结构：

磁盘

磁盘结构

磁道：盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。

扇区：磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。

从磁盘读取数据流程：

为了读取这个扇区的数据，需要将磁头放到这个扇区上方

1、寻址：系统将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。

2、寻道：磁头移动，对准相应磁道，耗费时间叫做寻道时间

3、磁盘旋转：然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页，主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

数据库系统的设计者巧妙的利用了磁盘预读原理，将一个结点的大小设为等于一个块（block），这样每个结点只需要一次I/O就可以完全载入。

5）B+Tree查找过程

如下图：

如果要找到数据项36 ，只需读取磁盘块1，磁盘块4，磁盘块9 总共3次IO，每次将一个磁盘块的内容加载到内存做查找操作，内存耗时相比IO操作可以忽略不计，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，成本非常大。

B+树查找过程

6）带顺序索引的B+TREE

带顺序索引的B+树

在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如上图中如果要查询key为从100到180的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

五、MySQL索引实现

1、主索引和辅助索引

•  一个表只能有一个Clustered Index（主索引）,因为数据只能根据一个键排序.用来排序数据的键叫做主键Primary Key
• 用其他的键来建立索引树时，必须要先建立一个dense索引层，在dense索引层上对此键的值进行排序。这样的索引树称作Secondary Index（辅助索引）. 一个表上可以有多个Secondary Index.

 2）非聚簇索引与聚簇索引

1. MyISAM存储引擎采用的是非聚簇索引，使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址
2. InnoDB采用的是聚簇索引，InnoDB的数据文件本身就是索引文件。InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引
3. 其中与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。

聚簇索引与非聚簇索引

Mysql在V5.1之前默认存储引擎是MyISAM；在此之后默认存储引擎是InnoDB

2者对比：

1、聚簇索引更适合主索引查找：因为聚簇索引只需要查找一次，而非聚簇在查到数据的地址后，还要进行一次I/O查找数据

2、因为聚簇辅助索引存储的是主键的键值，因此可以在数据行移动或者页分裂的时候降低维护成本，因为这时不用维护辅助索引。但是辅助索引会占用更多的空间。

3、聚簇索引在插入新数据的时候比非聚簇索引慢很多，因为插入新数据时需要检测主键是否重复，这需要遍历主索引的所有叶节点，而非聚簇索引的叶节点保存的是数据地址，占用空间少，因此分布集中，查询的时候I/O更少，但聚簇索引的主索引中存储的是数据本身，数据占用空间大，分布范围更大，可能占用好多的扇区，因此需要更多次I/O才能遍历完毕

六、索引的优化

我们一定要合理使用索引，因为为表设置索引是要付出代价的：

• 一是增加了数据库的存储空间；
• 二是在插入和修改数据时要花费较多的时间（因为索引也要随之变动）。

1、建索引的列一般是where,on,group by,order by 用到的列

2、尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是1，而一些状态、时间段、性别、地区在大数据面前区分度接近0，这些列使用索引的意义不大

3、对较小的数据列使用索引,这样会使索引文件更小,同时内存中也可以装载更多的索引键

4、索引列不能参与计算，保持列“干净”，比如date_sub(create_time,100) = ’2018-10-27’就不能使用到索引，原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。

5、数据很长的列使用前缀索引，如果列很长，通常可以索引开始的部分字符，这样可以有效节约索引空间，从而提高索引效率。

6、使用联合索引，当出现多个索引做相交操作时（多个AND条件，比如where anchor_id = 1 and actor_id = 1），通常来说一个包含所有相关列的索引要优于多个独立索引。

　　当出现多个索引做联合操作时（多个OR条件，如上例中查询语句），对结果集的合并、排序等操作需要耗费大量的CPU和内存资源，特别是当其中的某些索引的选择性不高，需要返回合并大量数据时，查询成本更高。所以这种情况下还不如走全表扫描。

　　因此explain时如果发现有索引合并，应该好好检查一下查询和表结构是不是已经是最优的，如果查询和表都没有问题，那只能说明索引建的非常糟糕，应当慎重考虑索引是否合适，有可能一个包含所有相关列的多列索引更适合。

7、使用索引的顺序选择

　　前面我们提到过索引如何组织数据存储的，从图中可以看到多列索引时，多列索引的顺序对于查询是至关重要的，很明显应该把选择性更高的字段放到索引的前面，这样通过第一个字段就可以过滤掉大多数不符合条件的数据。

　　理解索引选择性的概念后，就不难确定哪个字段的选择性较高了，查一下就知道了，比如：

SELECT * FROM new_union_anchor where anchor_id = 1 and union_id = 2

　　是应该创建(staff_id,customer_id)的索引还是应该颠倒一下顺序？执行下面的查询，哪个字段的选择性更接近1就把哪个字段索引前面就好。

select count(distinct anchor_id)/count(*) as anchor_id_selectivity,

count(distinct union_id)/count(*) as union_id_selectivity,

count(*) from new_union_anchor

8、尽量避免多个范围条件

实际开发中，我们会经常使用多个范围条件，比如想查询某个时间段内登录过的用户：

select user.* from user where login_time > '2017-04-01' and age between 18 and 30;

　　这个查询有一个问题：它有两个范围条件，login_time列和age列，MySQL可以使用login_time列的索引或者age列的索引，但无法同时使用它们。

8、去除冗余和重复索引

　　冗余索引是指在相同的列上按照相同的顺序创建的相同类型的索引，应当尽量避免这种索引，发现后立即删除。比如有一个索引(A,B)，再创建索引(A)就是冗余索引。冗余索引经常发生在为表添加新索引时，比如有人新建了索引(A,B)，但这个索引不是扩展已有的索引(A)。

　　大多数情况下都应该尽量扩展已有的索引而不是创建新索引。但有极少情况下出现性能方面的考虑需要冗余索引，比如扩展已有索引而导致其变得过大，从而影响到其他使用该索引的查询。

9、删除长期未使用的索引

七、使用索引的权衡

还是那句话，一定要合理使用索引。

不要过多创建索引, 权衡索引个数与DML之间关系，DML也就是插入、删除数据操作。这里需要权衡一个问题，建立索引的目的是为了提高查询效率的，但建立的索引过多，会影响插入、删除数据的速度，因为我们修改的表数据，索引也需要进行调整重建。

索引并不总是最好的工具，只有当索引帮助提高查询速度带来的好处大于其带来的额外消耗时，索引才是有效的。

小型的表，简单的全表扫描更高效。

中到大型的表，索引非常有效。

超大型的表，建立和维护索引的代价随之增长，这时候其他技术更有效，比如分库分表。