前言

数据库中存储的数据比作字典的话，索引就相当于是字典中的目录。如果没有索引，查找一个数据就需要从第一页开始全局检索直至找到需要的诗句，有了索引可以先在目录中根据拼音查找到该数据所在的页数，因此通过索引可以大大减少了查询时间

索引类型

Mysql中根据 索引中是否存在数据，将索引分为了两种类型的索引：聚簇索引和非聚簇索引。

• 聚簇索引

  聚簇索引是在索引树的叶子节点中保存了完整的数据信息，则索引称为聚簇索引。Mysql的 InnoDB引擎为主键创建的主键索引即是聚簇索引，数据文件即是索引文件。MyIsam引擎中的主键索引也是非聚簇索引。

• 非聚簇索引

  非聚簇索引是指索引树的叶子节点中保存的不是完整的数据信息，而是指向数据的一个指针或者是地址信息等（MyIsam的主键索引是指向数据的地址信息，InnoDB 中是主键的Id）。如果需要获取全部的数据信息，需要进行一次回表的操作。

• 联合索引

  联合索引是同时对多个列创建的索引。索引树中的叶子节点会同时包含多个列的值，叶子节点之间的排序，会根据创建索引时候列的顺序排序，排序满足最左前缀规则。

  最左前缀规则：例如当存在一个联合索引，包括了A、B、C三列的时候，如果查询是使用了 A、【A、B】、【A、B、C】的查询方式，则可以使用这个索引，如果是 使用了 【B、C】作为查询条件，则不满足最左前缀原则，则不会使用这个索引。

  因为Mysql在创建联合索引的时候，是先去比较第一列的值，当第一列的值相同的时候，才会比较第二列的值，当第二列的值相同的时候，再去比较第三列的值，以此类推，直到最后的一列。所以，当跳过第一列的值，直接匹配第二列的时候，此时第二列的值不一定是有序的，所以无法使用。

• 覆盖索引

  当使用某个查询条件的时候，如果需要查询的所有字段在索引中已经存在，即可直接返回，不用再根据查询到的主键ID进行回表操作，称为覆盖索引。

  如果我们为name和age 创建了一个索引。当我们查询name为指定值的数据的age 和Id的时候，就会使用覆盖索引。因为在索引数据已经存在了 name 和 age 的值（主键ID的值是每一个索引都会存在的），不会再根据id回表聚簇索引查询数据。

  如果在索引中不存在查询的字段数据信息，则会在查找到满足条件的数据之后，会根据查找到数据的主键ID，回表聚簇索引查找其他的信息，最终返回数据。

• 唯一索引

  唯一索引要求指定的列的值不能存在相同的值，数据库在每一次进行添加或者修改的时候，都会进行数据的检查，如果数据存在了重复的值，则会直接返回失败。

存储类型

索引有两种存储类型：B树（BTREE）索引和哈希（HASH）索引，InnoDB和MyISAM存储引擎支持BTREE索引，MEMORY引擎两种都支持，默认为BTREE

大多数的存储引擎都支持B树索引，B树通常意味着所有的值按照顺序存储，并且每个叶子节点到根的距离相同，B树索引能顾加快数据访问的速度

在引入B数之前，数据结构中比较熟悉的一种树二叉树，那么为何不用二叉树来做索引，主要有几个问题：

• 如果索引数据很多，树的层次会很高（只有左右两个子节点），数据量大时查询还是会慢
• 二叉树每个节点只存储一个记录，一次查询在树上找的时候花费磁盘IO次数较多

所以它并不适合直接拿来做索引存储，算法设计人员在二叉树的基础之上进行了变种，引入了BTREE的概念，B树与二叉树有几个区别

• 不再是二叉搜索，而是N叉搜索，树的高度会降低，查询速度变快
• 叶子节点与非叶子节点都可以存储数据，且可以存储多个数据。
• 通过中序遍历，可以访问树上所有节点

BTREE被作为实现索引的数据结构被创造出来，是因为它能够完美的利用“局部性原理”，其设计逻辑是这样的：

• 内存读写快，磁盘读写慢，而且慢很多
• 磁盘预读：磁盘读写并不是按需读取，而是按页预读，一次会读一页的数据，每次加载一些看起来是冗余的数据，如果未来要读取的数据就在这一页中，可以避免未来的磁盘读写，提高效率（通常，一页数据是4K）
• 局部性原理：软件设计要尽量遵循“数据读取集中”与“使用到一个数据，大概率会使用其附近的数据”，这样磁盘预读能充分提高磁盘IO效能

B树特征：

• 根节点至少包含两个孩子
• 树中每个结点最多含有m个孩子(m >= 2)
• 除了根节点和叶结点外，其他每个结点至少含有ceil(m/2)个孩子，ceil为向上取整
• 所有叶子结点位于同一层（高度相同）
• 假设每个非终端结点中包含有n个关键字信息，其中Ki(i = 1…n)为关键字，且按顺序升序排列关键字的个数n必须满足：[ceil(m / 2) - 1] <= n <= m - 1
• 非叶子结点的指针P[1],P[2],…,P[M];其中K[1]指向关键字小于K[1]的子树，P[M - 1] 指向关键字大于K[M - 1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树，比如看图中关键字值为8的这个结点，P1所对应的这个子树，其值均小于8

查询效率O(log n）

B+树特征

B+树是在BTree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。

B+树是B树的变体，基本定义与B树相同，其改进点在于：

• B+树仍然是N叉树，但是层级变得更小，非叶子结点的子树指针与关键字个数相同（所以相对于B树，B+树能够存储更多的关键字）
• 非叶子结点的子树指针P[i]，指向关键字值[K[i], K[i+1])的子树，注意区间为左闭右开，左侧值可以取到。
• 范围查找方面，当定位min与max之后，中间叶子节点，就是结果集，不用中序回溯（范围查询在SQL中用得很多，这是B+树比B树最大的优势）
• 非叶子结点仅仅用来索引，数据都保存在叶子结点中（B+树所有的检索都是从根部开始，检索到叶子结点才能结束，而且非叶子结点不存储数据的话就能存储更多关键字）
• 所有叶子结点均有一个链指针指向下一个叶子节点，这样以来就不用中序遍历，可以直接通过next指针快速访问

索引失效

索引失效是指为数据列创建了索引，但是在使用的时候，虽然使用了索引列，但是索引的作用不会生效，最终查询的时候，不会使用索引树进行查询。

索引失效的条件

• 索引列上的操作

  类型转换

  计算

• like查询以"%"开头

  因为Mysql在比较字符串的时候，是根据字符串从左到右做比较，满足最左匹配原则，当使用"%"开头查询的时候，就会破坏最左原则，所以不能使用索引。

• 破坏最左前缀原则：联合索引查询的时候，如果不满足最左前缀原则，则不会使用索引

• 范围查询的右边索引会失效

  当有A、B、C三个联合索引的时候，如果

  where A = 123 and B > 20 and C = 456;

  则C的索引会失效。因为 B 会返回多个值，会根据返回的多个值再去做匹配查询。因为在多个值的情况下，C的排序未必是有序的，可能是乱序的情况，无法使用索引。

• or 查询

  or 查询会产生多条数据，这多个数据之间排序规则是不确定的。

• 使用 ≠ 做判断

• 字符串没有加单引号：会发生类型的隐式转换

• 估计全表扫描会比索引快

索引type介绍

Explain介绍

在select语句之前增加explain关键字，执行后MySQL就会返回执行计划的信息，而不是执行sql。但如果from中包含子查询，MySQL仍会执行该子查询，并把子查询的结果放入临时表中。

Explain中的列

• id列

  id列的编号是select的序列号，有几个select就有几个id，并且id是按照select出现的顺序增长的，id列的值越大优先级越高，id相同则是按照执行计划列从上往下执行，id为空则是最后执行。

• select_type列

  表示对应行是简单查询还是复杂查询。

  simple：不包含子查询和union的简单查询

  primary：复杂查询中最外层的select

  subquery：包含在select中的子查询（不在from的子句中）

  derived：包含在from子句中的子查询。mysql会将查询结果放入一个临时表中，此临时表也叫衍生表。 union：在union中的第二个和随后的select，UNION RESULT为合并的结果

• table列

  表示当前行访问的是哪张表。当from中有子查询时，table列的格式为，表示当前查询依赖id=N行的查询，所以先执行id=N行的查询，如上面select_type列图4所示。当有union查询时，UNION RESULT的table列的值为<union1,2>，1和2表示参与union的行id。

• partitions列

  查询将匹配记录的分区。 对于非分区表，该值为 NULL。

• type列

  此列表示关联类型或访问类型。也就是MySQL决定如何查找表中的行。依次从最优到最差分别为：

  system > const > eq_ref > ref > range > index > all。

  NULL：MySQL能在优化阶段分解查询语句，在执行阶段不用再去访问表或者索引。

  system、const：MySQL对查询的某部分进行优化并把其转化成一个常量（可以通过show warnings命令查看结果）。system是const的一个特例，表示表里只有一条元组匹配时为system。

  eq_ref：主键或唯一键索引被连接使用，最多只会返回一条符合条件的记录。简单的select查询不会出现这种type。

  ref：相比eq_ref，不使用唯一索引，而是使用普通索引或者唯一索引的部分前缀，索引和某个值比较，会找到多个符合条件的行。

  range：通常出现在范围查询中，比如in、between、大于、小于等。使用索引来检索给定范围的行。

  index：扫描全索引拿到结果，一般是扫描某个二级索引，二级索引一般比较少，所以通常比ALL快一点。

  ALL：全表扫描，扫描聚簇索引的所有叶子节点。

• possible_keys列

  此列显示在查询中可能用到的索引。如果该列为NULL，则表示没有相关索引，可以通过检查where子句看是否可以添加一个适当的索引来提高性能。

• key列

  此列显示MySQL在查询时实际用到的索引。在执行计划中可能出现possible_keys列有值，而key列为null，这种情况可能是表中数据不多，MySQL认为索引对当前查询帮助不大而选择了全表查询。如果想强制MySQL使用或忽视possible_keys列中的索引，在查询时可使用force index、ignore index。

• key_len列

  此列显示MySQL在索引里使用的字节数，通过此列可以算出具体使用了索引中的那些列。索引最大长度为768字节，当长度过大时，MySQL会做一个类似最左前缀处理，将前半部分字符提取出做索引。当字段可以为null时，还需要1个字节去记录。

• key_len计算规则：

  字符串：

  char(n)：n个数字或者字母占n个字节，汉字占3n个字节

  varchar(n)： n个数字或者字母占n个字节，汉字占3n+2个字节。+2字节用来存储字符串长度。

  数字类型：

  tinyint：1字节 smallint：2字节 int：4字节 bigint：8字节

  时间类型

  date：3字节 timestamp：4字节 datetime：8字节

• ref列

  此列显示key列记录的索引中，表查找值时使用到的列或常量。常见的有const、字段名

• rows列

  此列是MySQL在查询中估计要读取的行数。注意这里不是结果集的行数。

• Extra列

  此列是一些额外信息。常见的重要值如下：

  Using index：使用覆盖索引（如果select后面查询的字段都可以从这个索引的树中获取，不需要通过辅助索引树找到主键，再通过主键去主键索引树里获取其它字段值，这种情况一般可以说是用到了覆盖索引）。

  Using where：使用 where 语句来处理结果，并且查询的列未被索引覆盖。

  Using index condition：查询的列不完全被索引覆盖，where条件中是一个查询的范围。

  Using temporary：MySQL需要创建一张临时表来处理查询。出现这种情况一般是要进行优化的。

  Using filesort：将使用外部排序而不是索引排序，数据较小时从内存排序，否则需要在磁盘完成排序。

  Select tables optimized away：使用某些聚合函数（比如 max、min）来访问存在索引的某个字段时。