文章

MySQL 认识索引

发表于 更新于
作者 ManShouyuan
本文总阅读量次， 39 分钟阅读
MySQL 认识索引

背景

在应用的开发过程中，由于初期数据量小，开发人员在写SQL语句时更重视功能上的实现，但当应用系统正式上线后，随着生产数据量的急剧增长，很多SQL语句开始逐渐暴露出性能问题，对生产的影响也越来越大，此时这些有问题的SQL就成为了整个系统性能的瓶颈，这时必须对它们进行优化。

进行SQL优化，索引将是数据库用来提高性能的最常用工具。所有MySQL列类型可以被索引，对相关列使用索引是提高SELECT操作性能的最佳途径。

Bad Case

count(*)

虽然下面的执行计划命中了idx_vflag普通索引，但遍历该二级索引树时，扫描的行数依然很多，接近全表扫描，效率非常低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

MySQL [bussinessc]> show index from bussinessc.t_bussiness;
+-------------+------------+-------------------+--------------+---------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table       | Non_unique | Key_name          | Seq_in_index | Column_name   | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+------------+------------+--------------------+--------------+---------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| t_bussiness | 0          | PRIMARY           | 1            | id            | A         | 1779703     | NULL     | NULL   | | BTREE | | |
| t_bussiness | 0          | uk_bussiness_id   | 1            | bussiness_id  | A         | 1799108     | NULL     | NULL   | | BTREE | | |
| t_bussiness | 1          | idx_tel           | 1            | tel           | A         | 330417      | NULL     | NULL   | | BTREE | | |
| t_bussiness | 1          | idx_add_time      | 1            | add_time      | A         | 291181      | NULL     | NULL   | | BTREE | | |
| t_bussiness | 1          | idx_create_time   | 1            | create_time   | A         | 1190831     | NULL     | NULL   | | BTREE | | |
| t_bussiness | 1          | idx_update_time   | 1            | update_time   | A         | 1061260     | NULL     | NULL   | | BTREE | | |
| t_bussiness | 1          | idx_vflag         | 1            | vflag         | A         | 1           | NULL     | NULL   | | BTREE | | |
| t_bussiness | 1          | idx_tag           | 1            | tag           | A         | 2           | NULL     | NULL   | | BTREE | | |
+------------ +------------+-------------------+--------------+---------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
8 rows in set (0.002 sec)
 
MySQL [bussinessc]> explain SELECT count(*) FROM bussinessc.t_bussiness \G;
 
*************************** 1. row *************************** 
           id: 1
  select_type: SIMPLE
        table: t_bussiness 
   partitions: NULL
         type: index 
possible_keys: NULL
          key: idx_vflag 
      key_len: 1
          ref: NULL 
         rows: 1879793
     filtered: 100.00 
        Extra: Using index
1 row in set, 1 warning (0.002 sec)

因为InnoDB引擎实现了多版本并发控制（MVCC），对同一个表，不同事物在同一时刻，看到的数据可能是不一样的。

所以在InnoDB引擎中，不能像在MyISAM中直接把对应值存到内存和磁盘文件中，当执行count(*)的时候，它需要一行一行的进行统计和计数，并将最终的统计结果返回。

count(*)的改进
在5.7.18版本之前，InnoDB处理select count(*)是通过扫描聚簇索引，来获取总记录数。从5.7.18版本开始，InnoDB扫描一个最小的可用的二级索引来获取总记录数，或者由SQL hint来告诉优化器使用哪个索引。如果二级索引不存在，InnoDB将会扫描聚簇索引。
原因：InnoDB是索引组织表，主键索引的叶子节点是数据，而普通索引的叶子节点是主键值，所以普通索引树比主键索引树小很多。对于COUNT(*)来说，遍历哪颗树都一样，所以mysql优化器会选择最小的树进行遍历。在保证逻辑正确的前提下，尽量减少扫描的数据量。加载同样的数据量， 由于二级索引叶子节点存放的是主键Id，所有走二级索引需要的io次数更少。

定位索引

索引是什么？

索引是对数据库表中一列或多列的值进行排序的一种结构，包含着对数据表里所有记录的引用指针，大多单独存储在磁盘上。使用索引可以提高数据库中特定数据的查询速度，如果表中查询的列有一个索引，Mysql能快速到达一个位置去搜索数据文件，而不必查看所有数据，避免进行全表扫描。

常见索引的数据结构实现，一般可以分为B+tree索引、B-tree索引、Hash索引、Full-text索引和空间索引。

索引在哪里？

索引是在存储引擎层中实现的，不是在服务器层，所以每种存储引擎的索引都不一定完全相同，也不是所有存储引擎都支持所有的索引类型。

根据存储引擎，可以定义每个表的最大索引和最大索引长度，每种存储引擎对每个表至少支持16个索引，总索引长度至少为256字节。大多数存储引擎有更高的限制。

认识MySQL体系

MySQL体系结构，大致分下面几个部分，

客户端连接部分 → MySQL Server部分 → Service&Utilities部分 → SQL处理所需要的模块 → MySQL所支持的各个存储引擎 → 物理存储层

Desktop View MySQL体系结构

  1. 客户端连接部分
    • 处理客户端的连接请求，MySQL支持所有的连接类型
  2. MySQL Server部分
    • 数据库给客户端创建的连接都在connection pool中处理和存储，用一个线程管理一个连接，包括用户认证、安全管理等。
  3. Service & Utilities部分
    • 管理工具&工具集，用于备份恢复、安全管理、集群管理服务&工具
  4. SQL处理所需要的模块
    • 查询优化，会根据解析树生成执行计划，选择合适的索引，之后会按照执行计划去执行SQL，和各个引擎交互。
    • SQL接口（接收用户的SQL命令并处理）
    • SQL解析器（负责将请求的SQL解析生成一个”解析树”，然后根据一些MySQL规则进一步检查解析树是否合法）
    • 查询优化器（对查询语句进行优化，选择合适索引，优化器的作用就是以它认为的最优的执行方案去执行（有时候可能也不是最优），比如多个索引的时候该如何选择索引，多表查询的时候如何选择关联顺序等。可以说，经过了优化器之后可以说这个语句具体该如何执行就已经定下来）
    • 缓存（包括各个引擎的缓存部分，比如InnoDB存储有pool，MyISAM有KeyBuffer等，也会缓存一些权限，是一些session级别的缓存）
  5. MySQL所支持的各个存储引擎
    • 插件式存储引擎（只要写好跟MySQL Server的接口，任何引擎都可以接入到MySQL里。这也是MySQL流行的原因之一）
  6. 物理存储层
    • 文件的物理存储，包括二进制日志、数据文件、错误日志、慢查询日志、全日志、redo日志、undo日志等等。

一条Select的执行轨迹

权限校验（如果命中缓存）→ 查询缓存 → 分析器 → 优化器 → 权限校验 → 执行器 → 引擎

Desktop View select执行轨迹

  1. 客户端通过CS通信协议和MySQL建立连接，
  2. 查询缓存，这是一个优化查询的地方，如果开启了Query_cache，且在缓存中有完全相同的SQL，则会直接返回结果给客户端，如果没有完全一样的sql，就会经过解析器进行语法解析，生成解析树，
  3. 预处理器生成新解析树，
  4. 查询优化器，生成执行计划，
  5. 查询引擎执行真正的SQL，此时会根据SQL中的表的存储引擎类型、对应的API接口，与底层存储引擎、缓存或者物理文件进行交互，得到查询结果，由MySQL Server过滤后，缓存起来，返回给客户端。若开启了Query_cache，会将结果完全缓存起来，以后便于直接返回结果，当然这里的sql语句是hash过的。

什么是存储引擎？

插件式存储引擎，是MySQL中具体与文件打交道的子系统，根据MySQL AB公司提供的文件访问层抽象接口定制的一种文件访问机制。作为MySQL最重要的特定之一，用户可以根据应用的需要选择存储和索引数据的方式、是否使用事务等，可以理解为表类型。

MySQL默认支持多种存储引擎，适用于不同领域的数据库应用需要，用户可以选择不同的存储引擎提高应用的效率，提供灵活的存储，甚至还可以定制自己的存储引擎。

MySQL 5.6之前，默认存储引擎是MyISAM；5.6之后，改成了InnoDB。

Desktop View MySQL存储引擎

常见存储引擎的功能特性

MyISAM不支持事务，不支持外键，优势在于访问速度快，对事务完整性没有要求，表级锁。

InnoDB提供了具有提交、回滚和崩溃回复能力的事务安全，相比于MyISAM，InnoDB写的处理效率差一些，还会占用更多的磁盘空间来保留数据和索引，表级锁/行级锁。

Memory使用存在于内存中的内容创建表，访问表非常快，由于内存特性，表中的数据容易丢失。

Desktop View 常见存储引擎功能特性

常见存储引擎的存储特性

MyISAM在磁盘上存储成3个文件，文件名和表名相同，扩展名分别是，

  • frm（存储表定义）
  • MYD（存储数据）
  • MYI（存储索引）

InnoDB存储表和索引有两种方式，

  • 共享表空间存储（这种方式创建的表的表结构存储在frm文件，数据和索引分别存在不同定义的表空间下，可以是多个文件）
  • 多表空间存储（这种方式创建的表的表结构仍然保存在frm文件中，但每个表的数据和索引单独保存在ibd中）
  • 即使在多表空间的存储方式下，共享表空间仍然是必须的，InnoDB把内部数据词典和在线重做日志放在这个文件中。 Memory则是使用存在于内存中的内容创建表。每个Memory表只实际对应一个frm格式的磁盘文件，一旦服务关闭，表中的数据就会丢失。

常见存储引擎支持的索引数据结构

  1. BTREE索引（B+TREE索引）
    • MyISAM、InnoDB的表默认创建的都是BTREE索引，B+Tree是B-tree的升级结构。
  2. Hash索引
    • MyISAM不支持Hash索引；InnoDB支持自适应Hash索引，但InnoDB中Hash索引的创建由存储引擎自动优化创建，不能人为干预是否创建Hash索引；Memory默认使用Hash索引，但也支持BTREE索引。
  3. FULLTEXT索引
    • MySQL 5.6之前，只有MyISAM支持FULLTEXT全文本索引，本质是对文本的内容进行分词，进行搜索，只限于CHAR、VARCHAR、TEXT列，对整个列进行，不支持局部前缀索引。它的出现是为了解决WHERE name LIKE “%word%"这类针对文本的模糊查询效率较低的问题。5.6之后，InnoDB也支持FULLTEXT。
  4. 空间索引
    • MyISAM表支持空间索引，在MySQL5.7版本以后，InnoDB还引入了空间索引，对GIS数据的支持，即可以存储和查询空间数据。

常见存储引擎的适用场景

如果应用是以select和insert为主，只有很少的update、delete，并且对事务的完整性、并发性要求不是很高，使用MyISAM很合适。

如果应用对事务的完整性有比较高的要求，在并发条件下要求数据的一致性，数据操作除了select和insert外，还有很多update、delete，使用InnoDB比较合适。

在需要快速定位记录时，Memory可以提供极快的访问。但对表的大小有限制，太大的表无法缓存到内存，通常用在更新不太频繁的小表，快速得到访问结果。

索引的原理

索引分类标准

按数据结构分类可分为：B+tree索引、B-Tree索引、Hash索引、Full-text索引、空间索引。

按物理存储分类可分为：聚簇索引、二级索引（辅助索引）。

按字段特性分类可分为：主键索引、普通索引、唯一索引、前缀索引。

按字段个数分类可分为：单列索引、联合索引（复合索引、组合索引）。

聚簇索引

聚簇索引的每个叶子节点存储了一行完整的表数据，叶子节点间按id列递增连接，可以方便地进行顺序检索。

也就是说，聚集索引的B+树中的叶子节点存放的是整张表的行记录数据。一个表最多只能有一个聚集索引，Innodb通过主键聚集数据，如果没有定义主键， Innodb会选择非空的唯一索引代替。如果没有这样的索引，Innodb会隐式的定义一个主键来作为聚集索引。

二级索引

非聚集索引索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。Innodb里非主键索引又被称为二级索引、辅助索引， 均属于非聚集索引。

回表

当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据，这个过程称为回表。

索引覆盖

如果select后面查询的字段都可以从这个索引的树中获取，而不用回表，这种情况一般可以说是用到了覆盖索引。

索引下推

ICP，index condition pushdown，MySQL 5.6引入的一个优化，它可以在索引遍历过程中，对索引中包含的字段先做判断，直接在InnoDB存储引擎层过滤掉 不满足条件的记录，减少回表次数。

  • 索引下推发生在组合索引
  • 索引下推触发条件必须sql会回表，否则下推没有意义

前缀索引

对字符类型字段的前几个字符或对二进制类型字段的前几个bytes建立的索引，而不是在整个字段上建索引。

前缀索引可以建立在类型为char、varchar、binary、varbinary的列上，可以大大减少索引占用的存储空间，也能提升索引的查询效率。但在order by和group by时无法使用。

前缀索引的长度跟存储引擎相关，对于MyISAM表，索引的前缀长度可以达到1000字节长；对于InnoDB表，索引的前缀长度最长是767字节。

联合索引

建立在多个列上的索引被称为联合索引，又叫复合索引、组合索引。需要理解联合索引的有序性和最左前缀原理，否则会导致索引失效。

  • 减少开销：建一个联合索引(col1,col2,col3)，实际相当于建了(col1)，(col1,col2)，(col1,col2,col3)三个索引。每多一个索引，都会增加写操作的开销和磁盘空间的开销。对于大量数据的表，使用联合索引会大大的减少开销。
  • 覆盖索引：对联合索引(col1,col2,col3)，如果有如下的sql: select col1,col2,col3 from test where col1=1 and col2=2。那么MySQL可以直接通过遍历索引取得数据，而无需回表，这减少了很多的随机io操作。减少io操作，特别的随机io其实是dba主要的优化策略。所以，在真正的实际应用中，覆盖索引是主要的提升性能的优化手段之一。
  • 筛选效率高：索引列越多，通过索引筛选出的数据越少。有1000W条数据的表，有如下sql: select from table where col1=1 and col2=2 and col3=3，假设假设每个条件可以筛选出10%的数据，如果只有单值索引，那么通过该索引能筛选出1000W*10%=100w条数据，然后再回表从100w条数据中找到符合col2=2 and col3=3的数据，然后再排序，再分页；如果是联合索引，通过索引筛选出1000w*10%*10%*10%=1w。
  • 有序：索引本身是有顺序的，当要对索引字段排序时，那么查询到的数据天然就是有顺序的，减少了排序的开销。

Hash索引、BTREE索引、B+TREE索引

Hash索引

Hash索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以Hash索引的查询效率要远高于B-Tree索引。

虽然Hash索引效率高，但是Hash索引本身由于其特殊性也带来了很多限制，主要有以下这些，

  1. Hash索引仅仅能满足=,IN和<=>(表示NULL安全的等价) 查询，不能使用范围查询
    • 由于Hash索引比较的是进行Hash运算之后的Hash值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的Hash算法处理之后的Hash值的大小关系，并不能保证和Hash运算前完全一样。对于BTREE索引，使用>、<、>=、<=、BETWEEN、!=或者<>，或者like（pattern不以通配符开始），都可以使用相关列上的索引。
  2. 优化器不能使用Hash索引来加速order by操作
    • 由于Hash索引中存放的是经过Hash计算之后的Hash值，而且Hash值的大小关系并不一定和Hash运算前的键值完全一样，所以数据库无法利用 索引的数据来避免任何排序运算。
  3. Hash索引不能利用部分索引键查询，只能使用整个关键字搜索一行
    • 对于组合索引，Hash索引在计算Hash值的时候是组合索引键合并后再一起计算Hash值，而不是单独计算Hash值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash索引也无法被利用。
  4. Hash索引依然需要回表扫描
    • Hash索引只包含哈希值和行指针，而不存储字段值。
    • Hash索引是将索引键通过Hash运算之后，将Hash运算结果的Hash值和所对应的行指针信息存放于一个Hash表中，由于不同索引键可能存在相同Hash值，所以即使取满足某个Hash键值的数据的记录条数，也无法从Hash索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。
  5. Hash索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高
    • 选择性比较低的索引键，如果创建Hash索引，那么将会存在大量记录指针信息存于同一个Hash值相关联。这样要定位某一条记录时就会非常麻 烦，会浪费多次表数据的访问，而造成整体性能低下。
    • 如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选择性很低(哈希仲突很多)的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应行的引用，冲突越多，代价越大。

由于范围查询是MySQL数据库查询中常见的场景，Hash表不适合做范围查询，它更适合做等值查询。另外Hash表还存在Hash函数选择和Hash值冲突等问题。因此，B+tree索引要比Hash表索引有更广的适用场景。

BTREE索引

B树是一个平衡多路查找树，B为Blanced，是为磁盘等外存储设备设计的一种平衡查找树，形状偏“瘦高”。

  • 关键字集合分布在整棵树中
  • 任何一个关键字出现且只出现在一个结点中
  • 搜索有可能在非叶子节点结束
  • 其搜索性能等价于在关键字全集内做一次二分查找

InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K。

1
2
3
4
5
6
7
8

MySQL16KB
mysql> show variables like 'innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.01 sec)

而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。

InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。

页分裂
B-Tree为了维护索引有序性，在插入新值的时候需要做必要的维护，当插入入一个新记录时，如果新插入的ID值在数据中间，就需要逻辑上挪动后面的数据，空出位置。
而更糟的情况是，所在的数据页已经满了，根据B-Tree的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能就会受影响。不是按顺序插入，而是随机插入，产生很多移动数据，也会导致页分裂。
页分裂会产生表空间碎片

1
2

影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约`50%`。
可能导致查询扫描的`IO`成本提升，效率查询降低。

当然有分裂就有合并。
当我们删除某一行记录时，其实MySQL只是把此行记录标记为了“可复用”，但磁盘大小是不会变的，所以通过delete表中记录是达不到回收表空间的。这些被标记为“可复用”而没有使用的空间看起来就像是“空洞”，当相邻两个页由于删除了数据，利用率很低之后，可将数据页做合并。即通过optimize table来重组文件。
产生表空间碎片的其他常见的原因

1
2

记录被`Delete`，且原空间无法复用；
记录被`Update`（通常出现在变长字段中），原空间无法复用。

自增主键 VS 非自增主键
自增主键的插入数据模式，正符合了递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。而有业务逻辑的字段做主键，由于每次插入主键的值近似于随机，则会产生很多移动数据，页分裂，进而造成了大量的碎片，大大影响性能。

为什么不用其他查询性能更好的树？
传统来搜索的平衡叉树有很多，如AVL树，红树等。这些树在般情况下查询性能常好，但当数据常的时候它们就能为了。原因当数据量常时，内存不够，无法将全部数据读入内存，部分数据只能存放在磁盘上，只有需要的数据才加载到内存中。般内存访问的时间约为50ns，磁盘在10ms左右。速度相差了近5个数量级，磁盘读取时间远远超过了数据在内存中较的时间。这说明程序部分时间会阻塞在磁盘IO上。而B树数据存储在各个节点上，那么每次读入内存的信息就比较有效，一次查询可能产生很多次IO，那么我们如何减少磁盘IO次数，于是有B+树。

B+TREE树

B+树是在B树基础上的一种优化，使其更适合实现存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构，形状偏“矮胖”。

B+树相对于B树有几点不同：

  • 非叶子节点只存储键值信息。
  • 所有叶子节点之间都有一个链指针。
  • 数据记录都存放在叶子节点中。

总结一下这种结构的优点：

  • B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快
  • B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定
  • B+树支持范围查询：叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针
  • B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高
  • B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3）。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿条记录。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

最后

只有深刻理解了这些索引的基础概念，才能在后边的索引优化工作中做到有的放矢。

架构, MySQL
MySQL
本文由作者按照 CC BY 4.0 进行授权