首页 > 代码库 > 高性能索引

高性能索引

什么是索引

索引是存储引擎用于快速找到记录的一种数据结构。

索引工作流程

如果想在一本书中找到某个特定主体,一般会先看书的“索引”,然后找到对应的页码。在MYSQL中,存储引擎用类似的方法使用索引,先在索引中找到对应值,然后根据匹配的索引记录找到对应的数据行。例如:要查找user_id = 2 的 用户信息,其中在user_id上建有索引:
SELECT name,age FROM user WHERE user_id = 2;
则MYSQL先在索引上按值进行查找到 user_id = 2的行,然后返回所有包含该值的数据行。
索引可以包含一个或者多个列的值。如果索引包含多个列,那么索引只能高效的使用索引的最左前缀列

索引类型和实现原理

索引类型

  • B-Tree索引
  • 哈希索引
  • 空间数据索引
  • 全文索引
目前会用到的索引为B-Tree索引,所以其他索引暂时不讨论。

B-Tree索引

B-Tree索引底层使用B-Tree数据结构来存储数据。索引定义中提到索引是一种快速找到记录的数据结构。那么为什么这种数据结构能够快速找到记录呢?先来了解一下B-Tree数据结构。
B-Tree (B+Tree)又叫平衡多路查找树。从名字可以看到:
  • 首先它是一棵查找树,左子树上所有结点的值均小于它的根结点的值,右子树上所有的节点的值均大于它的根节点的值。(二叉)
  • 其次它是一棵平衡树,保证树的深度由各个子节点均摊
  • 最后它是多路,每层有多个节点分支,减少访问深度,减少磁盘I/O次数
那么建立在B-Tree树上的索引是怎么样的呢?
技术分享
其中需要关注的点:
  • 叶子节点的指针指向的是被索引的数据,而不是其他的节点页
  • InnoDB 的逻辑页/数据页 16K的含义:这和盘块 大小有关。位于同一盘块的数据可以一次读取出来,设置成盘块的整数倍这样可以减少磁道查找时间。而且可以减少I/O次数。(待讨论
 B-Tree索引能够加快访问数据的速度,因为存储引擎不再需要进行全表扫描来获取需要的数据,取而代之的是从索引的根节点开始进行搜索。跟节点的槽中存放了指向子节点的指针,存储引擎根据这些指针向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点,这些指针实际上定义了子节点页中值的上限和下限。最终存储引擎要么找到对应的值,要么该记录不存在。
对于B-Tree索引,可以处理哪些类型的查询呢?什么样的查询可以用到B-Tree索引?
假设有以下数据表:
CREATE TABLE user(    last_name varchar(50) NOT NULL,    first_name VARCHAR(50) NOT NULL,    birthday DATE NOT NULL,    gendar enum(m,f) NOT NULL,    KEY(last_name,first_name,dob));
技术分享

 

其中需要注意的点:

索引对多个值进行排序的依据是CREATE TABLE 语句中定义索引列的顺序。为什么呢?因为索引树在建立后插入的顺序就是根据此规则插入的。顺序也就是:KEY(last_name,first_name,dob)

依据上述例子,可以用到B-Tree索引的查询有:全键值、键值范围或键前缀查找(最左前缀)。具体如下:

全值匹配(和索引中的所有列进行匹配):

               查找姓名为Cuba Allen、出生于1960-01-01的人

匹配最左前缀:

               查找所有姓为Allen的人

匹配列前缀:

               查找所有以J开头的姓的人

匹配范围值:

               查找姓在Allen和Barry之间的人

精确匹配某一列并范围匹配另外一列:

               查找所有姓为Allen,并且名字是字母与K开头的人

只访问索引的查询

总结来说也就是三种情况:1、就是索引全部用到了2、就是索引部分用到,且符合最左匹配原则3、就是使用索引的范围查询。(注意:如果查询中有某个列的范围查询,那么这个列右边的所有列(不包括该范围列)都无法使用索引优化查找。其中:LIKE 属于范围查找)

索引好处

索引可以让服务器快速的定位到表的指定位置。从而可以提升查询速度。
对于最常见的B-Tree索引,因为存储数据是顺序的,所以MYSQL可以用来做ORDER BY和GROUP BY操作。(使用索引扫描来做排序)。因为索引中存储了实际的列值,所以某些查询只使用索引就能够完成全部查询。(覆盖索引)。总结下来索引有如下三个优点:
  • 索引大大减少了服务器需要扫描的数据量(B-Tree为查找树,时间复杂度O(logxN))
  • 索引可以帮助服务器避免排序和临时表(查找树中序遍历本身是有序的,当可以使用到索引排序时)
  • 索引可以将随机I/O变为顺序I/O(使用覆盖索引时不用回表查询)

三星系统

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

确保正确使用了索引

独立的列(单列的时候)

独立的列是指索引不能是表达式的一部分,也不能是函数的参数。下面两种情况下不会使用索引:

表示式的一部分:(其中user_id上有索引,主键索引)

SELECT * FROM user WHERE user_id1 < 5;

索引作为表达式的一部分(CURRENT_DATE为索引列)

WHERE TO_DAYS(CURRENT_DATE)=1234545;

多列索引(多列的时候)

多列索引要选择合适得索引列顺序。因为索引是按照最左列进行排序。多列索引讨论的就是如何排序索引列让查询更合理。
多列索引的顺序问题需要考虑的因素:
  • 索引列的经验法则:将选择性最高的列放到索引最前列。(选择性高就是那一列能筛选出更少的数据,那一列的选择性就越高。例如:gender字段能大约筛选出 1/2 的数据,主键能筛选出唯一一条数据,那么主键的选择性就更高,如果不考虑其它因素,涉及到这两个列过滤时,就应该把主键列放在筛选条件的第一位)
  • 高频范围字段一般要靠后放:例如:年龄字段。因为使用了索引范围 右边的索引列就无法再使用到索引。
  • 对于可列举字段使用到索引的方法:使用 IN关键字。例如 WHERE gender IN(‘m‘,‘f‘)。这样后面也是可以用到索引的。同样的还有 NOT IN

聚簇索引

聚簇索引 并不是一种单独的索引类型,而是一种数据存储方式。
聚簇索引和B-Tree索引有啥区别:
   B-Tree索引存放的是索引列,聚簇索引存放行的全部数据。数据分布如下:
技术分享
值得注意的是:一个表只能有一个聚簇索引,InnoDB通过主键聚集数据,如果没有定义主键,选择一个唯一非空索引代替。
优缺点如下:
优点缺点
可以把相关数据保存在一起。
数据访问更快。直接在索引中找,不用回表 
......
插入速度严重依赖插入顺序
更新聚簇索引列代价高
可能导致全表扫描变慢
......

覆盖索引

定义:如果一个索引包含(或覆盖)所有需要查询的字段的值,就称之为覆盖索引。(包含:索引列比查找列多或相等 覆盖:刚好一样),MYSQL只能使用B-Tree索引做覆盖索引。
覆盖索引的好处:
  • 极大减少数据访问量,速度快+1
  • 索引顺序存储,所以I/O为顺序I/O,速度快+2
判断是否使用了覆盖索引:
  • 如果严格符合所以定义,那肯定使用了覆盖索引,哈哈
  • 使用EXPALIN关键字 查看。如果在 Extra列 看到"Using index",证明使用了覆盖索引。
执行SQL语句:(偷懒,,,id 默认有索引)
EXPLAIN SELECT id FROM tbl_role;
结果如下图:
技术分享
 可以看到:上述SQL语句使用到了主键索引。
顺便比较一下Explain 执行之后各个字段的含义和常见值。文章链接:http://www.cnitblog.com/aliyiyi08/archive/2008/09/09/48878.html
字段值含义常见值及含义
select_type查询类型SIMPLE(简单SELECT,不使用UNION或子查询等,普通WHERE可以)
PRIMARY(最外层的SELECT)
UNION(SELECT 之后使用了UNION)
type连接使用了哪种类别,有无使用索引,从最好到最差的连接类型为
const、eq_reg、ref、
range、index和ALL
const:表最多有一个匹配行,它将在查询开始时被读取。因为仅有一行,
在这行的列值可被优化器剩余部分认为是常数。const表很快,因为它们只读取一次
ref:基于索引做扫描,可以用于单表扫描或者连接
range:只检索给定范围的行,使用一个索引来选择行
index:仅仅扫描了索引
all:全表扫描,不适用索引,直接读取表上的数据

key使用的索引如果没有选择索引,键是NULL。要想强制MySQL使用或忽视possible_keys列中的索引,
在查询中使用FORCE INDEX、USE INDEX或者IGNORE INDEX
key_len键长度在不损失精确度的情况下,长度越短越好
ref参考ref列显示使用哪个列或常数与key一起从表中选择行
rows行数MySQL认为它执行查询时必须检查的行数。
Extra查询详细信息Distinct:一旦MYSQL找到了与行相联合匹配的行,就不再搜索了 
Using filesort:使用文件排序
Using index:覆盖索引
Using temporary:MySQL需要创建临时表来存储结果
Using where:使用了WHERE从句来限制哪些行将与下一张表匹配或者是返回给用户

使用索引扫描来排序

注意:如果索引不能覆盖查询所需的全部的列,那就不得不每扫描一条索引记录就回表查询一次对应的行。这基本上都是随机I/O,因此按索引顺序读取数据的速度通常要比顺序的全表扫描慢,尤其在I/O密集型工作时。

查看是否使用了索引来排序:

        如果 EXPLAIN 出来的 type 列的结果为 index,那说明MySQL使用了索引扫描来排序。还是上面的那个例子:
EXPLAIN SELECT id FROM tbl_role;
技术分享
使用索引扫描排序好处:
查询速度比没有使用更快。因为在使用索引查询时,找到索引记录之后需要回表查询数据,这种按索引顺序读取一般都是随机I/O,比较慢。
使用到索引扫描来排序的条件:
只有当索引的列顺序和ORDER BY子句的顺序完全一致,并且所有列的排序方向都一样时,MySQL才能够使用索引来对结果做排序。如果查询需要关联多张表,则只有当ORDER BY子句引用的字段全部为第一个表时,才能使用索引做排序。
上述条件注意的地方:
  • 索引列和ORDER BY子句的顺序完全一致:1、不包括主键索引2、满足索引的最左匹配原则,比如索引列为KEY(age,name),那么ORDER BY age是可以的。
  • 所有的方向都一样:就是DESC 和ASC,不能再ORDER BY子句里面 出现有的正向排序,有的逆向排序,这也同时说明了可以 DESC 或ASC,但是一般使用其中一种
  • 关联多张表,只要当ORDER BY子句引用的字段全部为第一个表时才可以。这里的第一个表并不是指SQL语句中第一个表,而是优化器优化后的第一个表。
条件例外的情况:
有一种情况下ORDER BY子句可以不满足索引的最左前缀的要求,那就是前导列为常量(这个字段属于索引列字段)的时候。如果WHERE子句或者JOIN子句中对这些列指定了常量,就可以“弥补”索引的不足。(这个常用
举例:现在有一个索引为KEY(birth,grade,age),执行如下SQL,

 发现type 不是 index,但是提示使用了索引

EXPLAIN SELECT * FROM user WHERE birth = 1993-01-02 ORDER BY grade,age;
技术分享

如果更改where 子句为 范围比较,则不能使用到索引(而是文件排序)。(图1)因为这里使用到了范围查询,后面的索引无法使用到,导致顺序有问题。同理,IN 关键字也是不可以使用的。(图2)

EXPLAIN SELECT * FROM user WHERE birth > 1993-01-02 ORDER BY grade,age
技术分享
图1
技术分享
图2

如果想使用索引,可以把birth放到ORDER BY后面

技术分享

 还有一种情况是WHERE 子句不涉及索引字段,这时候无法使用索引扫描排序。

技术分享

 冗余和重复索引

重复索引:是指在相同列上按照相同顺序创建的相同类型的索引。应该尽量避免冗余和重复索引,如果发现,一般是要删掉。
  • 相同列,相同顺序,相同类型
  • 尽量避免,发现删除
冗余索引:
  1. 创建了索引(A,B),再创建索引(A)就是冗余索引,因为索引(A,B)也可以当做索引(A)来使用
  2. 创建了索引(A,B),再创建索引(B,A),则不是冗余索引,索引(B)也不是冗余索引
  3. 其他不同类型的索引也不会是B-TREE索引的冗余索引
如果这些冗余索引没有特定的用途(性能需求等),一般删除。在建立新的索引的时候如果可以扩展原有的索引,那么就不创建新的索引,毕竟维护索引需要浪费资源和性能。

优化排序

如何处理排序和分页时 用户查看翻页到很靠后的数据?
SELECT * FROM profiles WHERE sex = M ORDER BY rating limit 10000,10
  1. 限制用户的翻页数量,用户很少会真正在乎搜索结果的第10000页
  2. 使用关联延迟,通过使用覆盖索引查询返回需要的主键,再根据这些主键关联原表获取需要的行。
SELECT <COLS> FROM profiles INNER JOIN( SELECT <primary key cols> FROM profiles WHERE x.sex = M ORDER BY rating LIMIT 10000,10) AS x using (<primary key cols>);

总结

 在选择索引和编写利用这些索引的查询时,有如下三个原则始终需要记住:
  1. 单行访问是很慢的。
  2. 按顺序访问范围数据是很快的,这有两个原因。第一:顺序I/O不需要多次磁盘寻道。第二:如果服务器能够按需要顺序读取数据,那么就不需要额外的排序操作。
  3. 索引覆盖查询是很快的。如果一个索引包含了查询所需要的所有列,那么存储引擎就不需要再回表查找行。这避免了大量的单行访问。

高性能索引