MySQL 索引

The Index of MySQL

Posted by decaywood on 2017-04-06
- 错误校对

索引(在MySQL中也叫做键)是存储引擎用于快速找到记录的一种数据结构。这是索引的基本功能,除此之外,本章还将讨论索引其他一些方面的有用的属性。索引对于良好的性能非常关键。尤其是当表中的数据量越来越大时,索引对性能的影响愈发重要。在数据量较小且负载较低时,不恰当的索引对性能的影响可能还不明显,但当数据量逐渐增大时,性能则会急剧下降。

不过,索引却经常被忽略,有时候甚至被误解,所以在实际案例中经常会遇到由糟糕索引导致的问题。索引优化应该是对查询性能优化最有效的手段了。索引能够轻易将查询性能提高几个数量级,“最优”的索引有时候比一个“好的”索引性能要好两个数量级,而创建一个真正“最优”的索引经常需要重写查询。

索引的类型

索引有很多种类型,可以为不同场景提供更好的性能。在MySQL中,索引是在存储引擎层而不是服务器层实现的。所以并没有统一的索引标准,不同的存储引擎的索引的工作方式是不同的,也不是所有的存储引擎都支持所有类型的索引。即使多个存储引擎支持同一种类型的索引,其底层的实现也可能不同。

B-Tree 索引

如果没有特别指明索引类型,默认索引类型为B-TREE索引。它通过B-TREE数据结构来进行存储数据,大多数MySQL引擎都支持这种索引。存储引擎以不同的方式使用B-TREE索引,性能也有所不同,各有优劣。MyISAM使用前缀压缩技术使得索引更小,但InnoDB则按照原数据格式进行存储。MyISAM索引通过数据的物理位置引用被索引的行,而InnoDB则根据主键引用被索引的行。

B-TREE索引能够加快访问数据的速度,因为存储引擎不再需要进行全表扫描来获取需要的数据,取而代之的是从索引的根节点开始进行搜索。B-TREE对索引列是顺序组织存储的,所以很适合查找范围数据。B-TREE索引适用于全键值、键值范围或者键前缀查找,其中键前缀查找只适用于根据最左前缀查找

但是B-TREE索引的限制:

  • 如果不是按照索引的最左列开始查找,则无法使用索引
  • 不能跳过索引中的列
  • 如果查询中有某个列的范围查询,则其右边所有列都无法使用索引最优化查找
  • 索引列的顺序非常重要:这些限制都和索引列的顺序有关

哈希索引

哈希索引是基于哈希表来实现的,只有精确匹配索引所有列的查询才有效。在MySQL中,只有Memory引擎显式支持哈希索引,也是Memory引擎表默认索引类型,Memory引擎同时支持B-TREE索引。而且Memory引擎是支持非唯一索引的。因为索引自身只需存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找的速度非常快,但是也有其限制:

  • 哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避免读取行。
  • 哈希索引数据并不是按照索引顺序存储的,所以无法用于排序。
  • 哈希索引也不支持部分索引列匹配查找,因为哈希索引始终是使用索引列的全部内容来计算哈希值的。
  • 哈希索引只支持等值比较查询。
  • 访问哈希索引的数据非常快,除非有很多哈希冲突
  • 如果哈希冲突很多的话,一些索引维护操作的代价也会很高。
  • 除了Memory引擎以外,NDB集群引擎也支持唯一哈希索引,并且在NDB集群引擎中作用非常特殊。

InnoDB引擎有一个特殊功能:“自适应哈希索引”。InnoDB会注意到某些索引值被使用得非常频繁时,它会在内存中基于B-TREE索引之上再创建一个哈希索引。

空间数据索引

MyISAM表支持空间索引,可以用作地理数据存储。和B-TREE索引不同,这类索引无需前缀查询。空间索引会从所有维度来索引数据。查询时,可以有效地使用任意维度来组合查询。

全文索引

全文索引是一种特殊类型的索引,它查找的是文本中的关键词,而不是直接比较索引中的值。全文搜索和其他几类索引的匹配方式完全不同,它有许多需要注意的细节,如停用词、词干、布尔搜素等等。全文索引更类似于搜索引擎做的事情,而不是简单的Where条件匹配。

索引的优点

  • 索引大大减少了服务器需要扫描的数据量
  • 所以可以帮助服务器避免排序和临时表
  • 索引可以将随机IO变为顺序IO

lational Database Index Design and the Optimizers一书中,评价索引是否适合某个查询的“三星系统”:

  • 索引将相关的记录放到一起则获得一星
  • 如果索引中的数据顺序和查找中的排列顺序一致则获得二星
  • 如果索引中的列包含了查询中需要的全部列则获得三星。

高性能的索引策略

正确地创建和使用索引是实现高性能查询的基础。

独立的列

我们通常会看到一些查询不当地使用索引,或者使得MySQL无法使用已有的索引。如果查询中的列不是独立的,则MySQL就不会使用索引。“独立的列”是指索引列不能是表达式的一部分,也不能是函数的参数。

前缀索引和索引的选择性

有时候需要索引很长的字符列,这会让索引变得大且慢。一个策略是前面提到过的模拟哈希索引。通常可以索引开始的部分字符,这样可以大大节约索引空间,从而提高索引效率,但是也会降低索引的选择性。(索引选择性是指不重复的索引值和数据表的记录总数的比值)索引的选择性越高则查询效率越高。

多列索引

一个常见的错误是:为每个列创建独立的索引,或者按照错误的顺序创建索引。但实际上,在多个列上建立独立的单列索引大部分情况下并不能提高MySQL的查询性能。5.0和之后的版本引入“索引合并”的策略,一定程度上缓解了这个问题。索引合并策略有时候是一种优化的结果,但实际上更多时候则说明了表上的索引很糟糕。

  • 当出现服务器对多个索引做相交操作的时候,意味着需要一个包含所有相关列的多列索引而不是多个独立的单列索引
  • 当服务器需要对多个索引做联合操作时,通常需要耗费大量的CPU和内存资源在算法上的缓存、排序和合并。
  • 优化其不会把这些计算到“查询成本”中,优化器只关心随机页面的读取。这会使得查询的成本被“低估”,导致该执行计划还不如直接走全表扫描。
  • 选择合适的索引列顺序。 正确的顺序依赖于使用该索引的查询,并且同时需要考虑如何更好地满足排序和分组的需要。 在一个多列B-TREE中,索引列的顺序意味着索引首先要按照最左列进行排序,其次是第二列,以此类推。对于如何建立索引列的顺序有一个经验法则:将选择性最高的列放到索引最前面。

合适的索引顺序

对于如何选择索引的顺序有一个经验法则:将选择性最高的列放在索引最前列。当不需要考虑排序和分组时,将选择性最高的列放在前面通常是最好的。然后,性能不只是依赖于所有索引列的选择性(整体基数),也和查询条件的具体值有关,也就是和值的分布有关。这和前面介绍的选择前缀的长度需要考虑的地方一样。可能需要根据那些运行频率最高的查询来调整索引列的顺序,让这种情况下索引的选择性最高。使用经验法则要注意不要假设平均情况下的性能也能代表特殊情况下的性能,特殊情况可能会摧毁整个应用的性能(当使用前缀索引时,在某些条件值的基数比正常值高的时候)。

聚簇索引

聚簇索引并不是一种单独的索引类型,而是一种数据存储方式。比较常用的就是 InnoDB 中的聚簇索引,它实际上是在同一结构中保存了 B-tree 索引和数据行。也就是说一个表的数据实际存放在索引的叶子页中(MYISAM 是按列值与行号来组织索引的。它的叶子节点中保存的实际上是指向存放数据的物理块的指针。从MYISAM存储的物理文件我们能看出,MYISAM引擎的索引文件(.MYI)和数据文件(.MYD)是相互独立的。而InnoDB按聚簇索引的形式存储数据,所以它的数据布局有着很大的不同)。

Mysql(InnoDB)中的聚簇索引不能指定,只能 MySQL 自动生成。InnoDB 中一般是通过主键聚集数据。(而在 Oracle 中则是需要手动创建) 在 InnoDB 中如果没有定义主键,会选择一个唯一的非空索引来代替,如果没有这样的索引,InnoDB 会隐式定义个主键来作为聚簇索引。

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

当一个数据被用到时,其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高IO效率。预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。一般使用磁盘IO次数评价索引结构的优劣。先从 B+ Tree 分析,根据 B+ Tree 的定义,可知检索一次最多需要访问h个节点。

数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次IO就可以完全载入。为了达到这个目的,在实际实现 B+ Tree 还需要使用如下技巧:

每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次IO。

聚族索引的优点

  • 可以把相关数据保存在一起。例如实现电子邮件时,可以根据用户ID来聚集数据,这样只需要从磁盘读取少数的数据页就能获取某个用户的全部邮件。如果没有使用聚族索引,则每封邮件都可能导致一次磁盘IO
  • 数据访问更快。聚族索引将索引和数据保存在同一个B-Tree中,因此从聚族索引中获取数据通常比在非聚族索引中查找更快
  • 使用覆盖索引扫描的查询可以直接使用节点中的主键值

聚族索引的缺点

  • 聚簇数据最大限度的提高了IO密集型应用的性能,但如果数据全部都放在内存中,则访问的顺序就没有那么重要了,聚簇索引也就没有那么优势了
  • 插入速度严重依赖于插入顺序。按照主键的顺序插入是加载数据到InnoDB表中速度最快的方式。但如果不是按照主键顺序加载数据,那么在加载完成后最好使用OPTIMIZE TABLE命令重新组织一下表
  • 更新聚簇索引列的代价很高,因为会强制InnoDB将每个被更新的行移动到新的位置
  • 基于聚簇索引的表在插入新行,或者主键被更新导致需要移动行的时候,可能面临“页分裂”的问题。当行的主键值要求必须将这一行插入到某个已满的页中时,存储引擎会将该页分裂成两个页面来容纳该行,这就是一次分裂操作。页分裂会导致表占用更多的磁盘空间
  • 聚簇索引可能导致全表扫描变慢,尤其是行比较稀疏,或者由于页分裂导致数据存储不连续的时候
  • 二级索引(非聚簇索引)可能比想象的要更大,因为在二级索引的叶子节点包含了引用行的主键列
  • 二级索引访问需要两次索引查找,而不是一次

备注:有关二级索引需要两次索引查找的问题?

答案在于二级索引中保存的“行指针”的实质。要记住,二级索引叶子节点保存的不是指向行的物理位置的指针,而是行的主键值。这意味着通过二级索引查找行,存储引擎需要找到二级索引的叶子节点获得对应的主键值,然后根据这个值去聚簇索引中查找到对应的行。这里做了重复的工作:两次B-Tree查找而不是一次。对于InnoDB,自适应哈希索引能够减少这样的重复工作。

覆盖索引

覆盖索引是一种非常强大的工具,能大大提高查询性能。设计优秀的索引应该考虑到整个查询,而不单单的where条件部分。索引确实是一种查找数据的高效方式,但是MYSQL也可以使用索引来直接获取列的数据,这样就不再需要读取数据行。索引的叶子节点中已经包含要查询的数据,那么就没有必要再回表查询了,如果索引包含满足查询的所有数据,就称为覆盖索引。只需要读取索引而不用读取数据有以下一些优点:

  • 索引项通常比记录要小,所以MySQL访问更少的数据
  • 索引都按值的大小顺序存储,相对于随机访问记录,需要更少的I/O
  • 大多数据引擎能更好的缓存索引。比如MyISAM只缓存索引
  • 覆盖索引对于InnoDB表尤其有用,因为InnoDB使用聚集索引组织数据,如果二级索引中包含查询所需的数据,就不再需要在聚集索引中查找了。 覆盖索引不能是任何索引,只有B-TREE索引存储相应的值。而且不同的存储引擎实现覆盖索引的方式都不同,并不是所有存储引擎都支持覆盖索引(Memory和Falcon就不支持)

查询注意事项

IN 与 EXISTS

假设有两张表A、B

select * from A where id in(select id from B)

以上查询使用了in语句,in()只执行一次,它查出B表中的所有id字段并缓存在内存中。之后,检查A表的id是否与B表中的id相等,如果相等则将A表的记录加入结果集中,直到遍历完A表的所有记录。此操作在内存中复杂度为O(A.len * B.len),可以看出,当B表数据较大时不适合使用in(),因为它会B表数据全部遍历一次,因此in()适合B表比A表数据小的情况。

select a.* from A a where exists(select 1 from B b where a.id=b.id)

以上查询使用了exists语句,exists()会执行A.length次,它并不缓存exists()结果集,因为exists()结果集的内容并不重要,重要的是结果集中是否有记录,如果有则返回true,没有则返回false。

当B表比A表数据大时适合使用exists(),因为它没有那么遍历操作,只需要再执行一次查询就行。

如:A表有10000条记录,B表有1000000条记录,那么exists()会执行10000次去判断A表中的id是否与B表中的id相等。

如:A表有10000条记录,B表有200000000条记录,那么exists()还是执行10000次,因为它只执行A.length次,可见B表数据越多,越适合exists()发挥效果。

再如:A表有10000条记录,B表有100条记录,那么exists()还是执行10000次,还不如使用in()遍历10000*100次,因为in()是在内存里遍历比较,而exists()需要查询数据库,我们都知道查询数据库所消耗的性能更高,而内存比较很快。

结论:exists()适合B表比A表数据大的情况,当A表数据与B表数据一样大时,in与exists效率差不多,可任选一个使用。

延迟关联

优化 LIMIT 分页查询的常见手段就是尽可能地使用索引覆盖扫描,而不是查询所有的列。然后根据需要做一次关联操作再返回所需的列。对于偏移量很大的时候,这样做的效率会提升非常大。

三星索引

数据库索引的好坏有一个大致的评判标准:

  • 如果与一个查询相关的索引行是相邻的,或者至少足够靠近的话,那这个索引就可以被标记上第一颗星。这最小化了必须扫描的索引片的宽度。
  • 如果索引行的顺序与查询语句的需求一致,则索引可以被标记上第二颗星。这排除了排序操作。
  • 如果索引行包含查询语句中的所有列——那么索引就可以被标记上第三颗星。这避免了访问表的操作,仅访问索引就可以了。

InnoDB 的二级索引

如前面章节提到的,InnoDB 使用的聚簇索引,故主键列对于 InnoDB 来说已经包含在二级索引里了。例如:

CREATE TABLE test (
   ID INT NOT NULL PRIMARY KEY,
   A INT NOT NULL,
   B INT NOT NULL
) ENGINE = InnoDB;

如果此时创建了一个索引(A)以及(A, ID),实际上(A, ID)是冗余的,因为主键列已经包含在了二级索引(A)中,但是如果建立的是(A, B),那么情况就不一样了,此时只有创建(A, B, ID)才能算是冗余索引。