1. 概念
索引(在MySQL中也叫作“键(key)”),是存储引擎用于快速找到记录的一种数据结构。这是索引的基本功能,除此之外,索引还有其他的一些方面有用的属性。
索引对于良好的性能而言非常关键,尤其是表中的数据量非常大的时候,而糟糕的索引则会导致性能的急剧下降。
索引优化是对查询优化最有效的手段。
2. 基础
2.1 索引的简单使用
索引的工作方式:查询语句现在索引中找到对应值,然后根据匹配的索引记录找到对应的数据行。比如:SELECT book_title FROM t_book WHERE book_id = 36;
若book_id
列上建有索引,则MySQL将使用索引找到book_id
为36的行,即,MySQL先在索引上按值查找,然后返回包含该值的数据行。
索引可以包含一个或多个列的值。当包含多个列的值,此时列的顺序十分重要,MySQL只能高效的使用最左前缀列。
2.2 索引的存储
一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数,其中典型的例子就是树状索引使用数据结构B+Tree而不是B-Tree或红黑树。
3. 索引的类型
索引的实现与存储引擎的类型有关,没有统一的标准,下面讲述MySQL中支持的索引类型:B+Tree索引、哈希索引、空间数据索引、全文索引,其中,详细介绍B+Tree索引。
3.1 B+Tree 索引
3.1.1 概念
索引的默认类型是B+Tree索引,指的是使用B+Tree数据结构来存储数据,大多数存储引擎都支持这种索引,实际上很多存储引擎使用的是B+Tree数据结构,即每个结点都包含指向下一个叶子结点的指针,从而方便叶子结点的范围遍历。
3.1.2 特点
B+Tree意味着所有的值都是有序的,并且每个叶子页到根的距离相等。根结点存放了指向子结点的指针,存储引擎通过比较结点页的值和要查找的值,找到合适的指针进入下层的子结点,而叶子结点的指针指向被索引的数据。其抽象表示如下图:
3.1.3 适合B+Tree索引的查询类型及使用限制
假设有如下数据表:1
2
3
4
5
6
7CREATE TABLE t_book (
book_title VARCHAR(50) NOT NULL,
book_subtitle VARCHAR(50) NOT NULL,
publish_date Date NOT NULL,
author VARCHAR(50) NOT NULL,
key(book_title, book_subtitle, publish_date)
);
其中对于每一行数据,使用了book_title, book_subtitle, publish_date
共3列的值当索引,用这个当做例子进行下面的讲述。
- 全值匹配:指的是和索引中的所有列进行匹配,例如
SELECT * FROM t_book WHERE book_title = ? AND book_subtitle = ? AND publish_date = ?
。 - 匹配最左前缀:指的是只使用索引的第一列进行匹配,例如
SELECT * FROM t_book WHERE book_title = ?
。 - 匹配列前缀:指的是只使用某一列的开头部分进行匹配,例如
SELECT * FROM t_book WHERE book_title like 'computer%'
。 - 匹配范围值:指的是可以范围匹配符合条件的某一列,例如
SELECT * FROM t_book WHERE book_title > ? AND book_title < ?
,或者使用like
关键字。 - 精确匹配某一列并范围匹配另外一列:指的是使用索引的第一列进行匹配然后在范围匹配索引第二列,例如
SELECT * FROM t_book WHERE book_title = ? AND book_subtitle > ? AND book_subtitle < ?
。 - 只访问索引的查询:指的是查询只需要访问索引,而不需要访问数据行,例如
SELECT book_title FROM t_book WHERE book_title > ? AND book_title < ?
。
关于B+Tree索引的使用有下面的限制,主要是受到B+Tree数据结构本身的限制,但也受到存储引擎以及数据库优化器的影响:
- 如果不是按索引的最左列开始查询,则无法使用索引,反例如:
SELECT * FROM t_book WHERE book_subtitle = ? AND publish_date = ?
。where子句一定要包含复合索引的最左列,可不按顺序,如SELECT * FROM t_book WHERE publish_date = ? AND book_title = ?
是可以用到索引的。 - 不能跳过索引中的列,即不能跳过第一列利用第二列进行查询,反例如
SELECT * FROM t_book WHERE book_subtitle = ?
。 - 如果查询中有某个列的范围查询,则其右边的所有列都无法使用索引进行查询,反例如:
SELECT * FROM t_book WHERE book_title = ? AND book_subtitle like ? AND publish_date = ?
。publish_date一列无法使用索引。
显然,索引的顺序十分重要。
3.1.4 为何选择B+Tree,而不是B-Tree或红黑树
由上面的讲述可概括B+树的特点,即 B+树只有叶结点存放数据,其余结点用来索引,而B-树是每个索引结点都会有Data域。
- 单一结点存储更多的元素,B+树空间利用率更高,使得查询的IO次数更少。
- 所有查询都要查找到叶子结点,查询性能稳定。
- 所有叶子结点形成有序链表,便于范围查询。
- B+树非叶子结点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。
- 红黑树往往深度过大,导致磁盘IO次数多。
- B树,查询性能不稳定,查询结果高度不一致。
3.2 哈希索引
3.2.1 概念
哈希索引基(hash index)于哈希表实现,只有精确匹配索引所有列的查询才会起效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码,哈希码是一个较小的值,不同键值的行计算出来的哈希码也不同。
在MySQL中,只有MEMORY引擎支持哈希索引。
3.2.2 特点
哈希索引将所有的哈希码及指向数据行的指针存储在索引中,假设有如下表:1
2
3
4
5CREATE TABLE t_order (
order_id VARCHAR(50) NOT NULL,
order_info VARCHAR(50) NOT NULL,
KEY USING HASH(order_id)
)ENGINE=MEMORY;
表中包含如下数据:
序号 | order_id | order_info |
---|---|---|
1 | ORDER_10000 | INFO_1 |
2 | ORDER_20000 | INFO_2 |
3 | ORDER_30000 | INFO_3 |
4 | ORDER_40000 | INFO_4 |
假设使用哈希函数hash()
,满足以下条件:1
2
3
4hash("ORDER_10000") = 2222,
hash("ORDER_20000") = 1111,
hash("ORDER_30000") = 4444,
hash("ORDER_40000") = 3333
则哈希索引的结构如下:
序号 | 槽(Slot) | 值(Value) |
---|---|---|
1 | 1111 | 指向第2行的指针 |
2 | 2222 | 指向第1行的指针 |
3 | 3333 | 指向第4行的指针 |
4 | 4444 | 指向第3行的指针 |
显然,哈希索引按槽(哈希码)有序,但对于索引列的值来说是无序的。哈希索引存储内容少,结构紧凑,查找速度非常快。
3.2.3 哈希索引的使用限制
- 不能使用索引中的值来避免读取行:哈希索引只存储哈希码和行指针,而不存储字段值,不能使用索引中的值来避免读取行。
- 无法用于排序:哈希索引的数据并不是按照索引值顺序排序的。
- 不支持部分按列索引匹配查找:哈希索引始终是使用索引列内的全部内容来计算哈希值。
- 只支持等值比较查询:只能使用
=, IN(), <=>
,不支持任何范围查询,比如SELECT * FROM t_order WHERE order_id > ?
。 - 当哈希冲突很多时,索引代价维护随之变高:哈希索引采用链式哈希存储,当出现哈希冲突时,必须遍历链表的所有行指针进行匹配,同理,删除时也同样需要遍历。
可见,哈希索引的限制非常大,只适用于某些特定的场合。
3.2.4 自适应哈希索引
自适应哈希索引(Adaptive Hash Index):当InnoDB注意到某些索引值被使用得非常频繁的时候,它会在内存中基于B+Tree索引之上再创建一个哈希索引,让B+Tree索引具有一些哈希索引的优点,如快速哈希查找。这是完全封闭的、内部的、自动的行为,用户无法直接控制,但如果有必要,可以完全关闭此功能。
3.3 空间数据索引
MyISAM存储引擎支持空间索引,可以用作地理数据存储,这类索引无需前缀匹配查询,可以从所有维度来索引数据,查询时可任意的组合索引列。
必须使用MySQL的GIS相关函数如MBRCONTAINS()
等来维护数据,然而MySQL在5.5版本及之前做得并不完善,若要使用可使用开源的PostgreSQL数据库。
3.4 全文索引
全文索引是一种特殊索引,查找的是文本中的关键词,而不是直接比较索引中的值,类似于搜索引擎所做的事,适用于MATCH AGAINST
操作而不是普通的WHERE
操作。
4. 索引的优点
索引除了快速定位到查询的数据行外,根据所使用索引的数据结构的不同,也会有不同的附加效果。
根据常用的B+Tree索引的特性,索引的优点总的包括以下三点:
- 索引大大减少了服务器需要扫描的数据量;
- 索引可以帮助服务器避免排序和临时表;
- 索引可以将随机I/O变为顺序I/O。
索引并不总是最好的查询工具
总的来说,只有当索引帮助存储引擎快速查找到记录带来的好处大于其带来的额外工作时,索引才是有效的。对于非常小的表,大部分情况下简单的全表扫描更高效。对于中到大型表,索引就非常有效。对于特大型表,维护索引的代价随之增大,可使用分区技术。
5. 使用索引的正确方法
正确的使用索引非常重要,否则会导致索引无效、占用内存增加,最终导致服务器性能下降。
5.1 使用独立的列
使用索引除了索引类型本身的限制外,如果查询的列不是独立的,则MySQl同样不会使用索引,独立的列指的是索引列不能是表达式的一部分,也不能是函数的参数:
反例如:SELECT * FROM t_test WHERE test_id + 5 = 12;
或者SELECT * FROM t_test WHERE LEFT(test_name, 4) = 'kana';
5.2 多列索引
一个常见错误是:为每个列创建单独的索引,或者按照错误的顺序创建多列索引。
为每个列创建单独的索引,往往导致多条件AND查询时只在最左列使用到索引,对于多条件OR查询在MySQL5.0后的版本则会使用索引合并自动进行优化,嵌套进UNION
语句。当触发索引合并时,应当思考下索引创建是否合理。当索引的列顺序与查询的条件顺序一致时,才会使用索引。
5.3 避免多个范围查询
范围查询指的是查询包含了范围条件,比如<
、>
和BETWEEN
操作符,当索引列遇到该范围查询条件列,之后的列就无法再使用索引,情况允许的时候可以手动将某些条件转化成IN()
操作符,这样数据库在查询时就会转换成多个等值查询,继而后续列可以继续使用索引,否则,当查询注重效率时,应该考虑不要使用多个范围查询,或者范围条件放最后。
6. 聚簇索引
聚簇索引并不是一种索引类型而是一种数据存储方式。InnoDB的聚簇索引实际上在同一个数据结构中保存了B+Tree索引和数据行,“聚簇”表示数据行和相邻的键值紧紧地存储在一起,如下图
由于数据行和相邻的键值紧紧地存储在一起,因此无法同时把数据行存放在两个不同的地方,一个表只能由一个聚簇索引。
聚簇索引和非聚簇索引对比:
聚簇索引的数据的物理存放顺序与索引顺序是一致的,即:只要索引是相邻的,那么对应的数据一定也是相邻地存放在磁盘上的。聚簇索引要比非聚簇索引查询效率高很多。
聚集索引这种主+辅索引的好处是,当发生数据行移动或者页分裂时,辅助索引树不需要更新,因为辅助索引树存储的是主索引的主键关键字,而不是数据具体的物理地址。
非聚集索引,类似于图书的附录,那个专业术语出现在哪个章节,这些专业术语是有顺序的,但是出现的位置是没有顺序的。每个表只能有一个聚簇索引,因为一个表中的记录只能以一种物理顺序存放。但是,一个表可以有不止一个非聚簇索引。
7. 覆盖索引
如果一个索引包含(或者说覆盖)所有需要查询的字段的值,我们就称之为覆盖索引。当索引包含要查询的数据,就没有必要再回表查询,查询效率更加高效。
8. 备注
以上内容主要摘自《高性能MySQL第三版》第五章。
Copyright © 2018, CSCW back-end Kanarien, All Rights Reserved