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

磁盘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是一种多路搜索树(并不是二叉的):

  1. 定义任意非叶子结点最多只有M个儿子;且M>2;
  2. 根结点的儿子数为[2, M];
  3. 除根结点以外的非叶子结点的儿子数为[M/2, M];
  4. 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
  5. 非叶子结点的关键字个数=指向儿子的指针个数-1;
  6. 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
  7. 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于等于K[M-1]的子树,其它P[i]指向关键字属于[K[i], K[i+1])的子树;
  8. 所有叶子结点位于同一层;
  9. 为所有叶子结点增加一个链指针;
  10. 所有关键字都在叶子结点出现;
    如图,是一个M为3的B-TREE
    mysql-gao-xing-neng-suo-yin

B+的特性:

  1. 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
  2. 不可能在非叶子结点命中;
  3. 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
  4. 更适合文件索引系统;

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查找时过滤掉更多的行。比如主键和唯一索引,这种时候性能最好。所以在选择索引长度时要同时考虑索引选择性才能达到性能最优化。

多列索引

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

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

聚簇索引并不是一个单独的索引形式,而是Mysql在B+TREE索引上的数据存储形式。InnoDB的聚簇索引实现就是在统一结构里面保存了B+TREE索引和数据行如图:
mysql-gao-xing-neng-suo-yin
聚簇索引有时候对性能很有帮助,但有时候也对性能造成严重的问题。下面我们用几张图来分辨下非聚簇索引的表和聚簇索引的表的区别:
mysql-gao-xing-neng-suo-yin
非聚簇索引表的数据如上图
mysql-gao-xing-neng-suo-yin
非聚簇索引表的主键索引图
mysql-gao-xing-neng-suo-yin
聚簇索引的主键索引图

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

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

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

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

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

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

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

因为覆盖索引是索引中存储了列的值,所以覆盖索引的适用范围仅适用于B+TREE的时候。下面有个例子:
mysql-gao-xing-neng-suo-yin

注意下面的一个例子,我们来优化这个语句让它成为覆盖索引:

mysql-gao-xing-neng-suo-yin
这个语句优化如下,让它使用覆盖索引:
mysql-gao-xing-neng-suo-yin

索引扫描来做排序

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

索引和锁

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

一些微小的建议

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