索引

介绍

索引包括两个部分：排序和查找。排序的过程用到BTree、B+Tree、Hash进行建表。以B+Tree为例，非叶子节点保存了键（key）、叶子节点保存了key和data；并且叶子节点有一条引用链指向与它相邻的叶子节点。这样就可以实现高效查找；

优点

  • 快速查找：提高数据检索的效率，降低数据库的IO成本；降低树的高度，减少IO成本
  • 排好序：通过索引列对数据进行排序，降低数据排序的成本，降低了CPU的消耗；时间复杂度O（log n）


分类

聚合索引：

  • 聚簇索引并不是一个单独的索引类型，而是一种数据存储方式。
  • InnoDB引擎，数据文件本身就是索引文件，data存放的就是完整的数据记录；由于数据行只有一份，聚簇索引在一个表只有一个。
  • InnoDB通过主键聚集索引（一个数据表只能有一个主键索引，并且不能为null，不能重复）；如果没有定义主键，则会选择一个唯一的非空索引替代；如果还是没有这样的索引，则会隐式定义一个自增id列来作为聚簇索引。

非聚合索引：

MyISAM引擎，数据文件与索引文件是分离的，所以data存放的是数据记录的地址，多了一步根据地址读取相应的数据记录；
  • 唯一索引：索引列的值必须唯一，但允许有null值；
  • 普通索引：一个索引只包含单个列，一个表可以有多个单列索引；
  • 复合索引：多列值组成一个索引，根据最佳左前缀原则使用；
  • 覆盖索引：一个索引包含了所需要查询字段的值，就直接返回无需回表；

覆盖索引的用途？




B树、B+树、AVL、红黑树

B树

主要特点就是所有节点都带有指向记录的指针。

B+树

  1. 只有叶子节点才带有指向记录的指针。这样一块可以容纳更多的索引项、从而降低了树的高度、也就降低了IO次数。
  2. 每一个节点都是一个数据页（InnoDB的数据按照数据页为单位来读写的，也就是需要读一条记录的时候，并不是将这个记录本身从磁盘读取出来，而是以页为单位，将其整体读入内存；InnoDB的数据页的默认大小是16KB）
  3. 所有叶子节点都是通过指针连接在一起。这样就可以层序遍历。
  4. 适用于外存、磁盘上。时间复杂度：log(n)。
  5. 优点：         
  • 降低IO次数。
  • 查找效率更加稳定。
  • 遍历所有数据更方便。

对比B+树与B树的区别

  • 每个叶子节点都有指向相邻的叶子节点的地址，所以对于范围查找时只需要查找两个节点，进行遍历即可；B树需要获取所有节点，所以B+树效率更高；
  • 非叶子节点不存储数据，使得存储更多的键值，会导致树的高度降低，会使得查询数据的时候进行磁盘的IO次数会降低，所以数据查询效率会更快；
  • B+树有大量的冗余节点（所有非叶子节点都是冗余索引），这样使得删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点，这样删除、插入效率更高。

AVL

  • 适用于读取。
  • 插入删除的时候需要通过旋转来维持平衡，所以维护比较困难。

红黑树

1、规则严格：
  • 每个节点非黑即红
  • 根节点是黑的。
  • 每个叶节点都是黑色的空节点（NIL节点）。
  • 如果节点是红的，则它的子节点必须是黑色的（反之不一定）。
  • 从根节点到叶子节点或者空子节点的每条路径，必须包含相同数目的黑结点（即相同的黑色高度）。
2、主要就是解决平衡树维护起来比较困难的问题。
3、适用于内存。map、set内部都是用红黑树来实现。时间复杂度为log(n)。
4、总结：读取略逊于AVL、维护强于AVL。



常见问题

主键索引与唯一索引差别？

  • 主键是一种约束，唯一索引就是一种索引；
  • 一张表只有一个主键，可以有多个唯一索引；
  • 主键索引不允许有null值，唯一索引可以允许有null值；

为什么设置主键？

  • InnoDB主键中存放了所有数据，是聚簇索引；同时InnoDB默认是按照主键进行聚簇的，所以必须要设置主键；
  • 当没有设置主键时，数据库会搜索唯一的一列自动作为主键；如果每一列都不唯一则在最后新生成一列作为主键；

为什么需要使用整型自增的主键？

  • 因为每一次辅助索引都需要经过主键索引，如果主键字段太大的话会占用很大的内存空间，导致叶子节点存储的主键数量减少，树的高度增加导致IO成本增加；
  • 因为InnoDB底层是一个B+Tree，当使用自增型的主键插入新记录时会比较容易维护B+Tree；

为什么主键id设置int类型，而不是varchar类型？

  • MySQL在遇到字符串和数字比较的时候，会自动的把字符串转化为数字，然后再进行比较；
  • 所以如果设置为varchar类型，会使用函数将索引从字符串类型转化为数字，也就是对索引使用了函数，会导致索引失效。


回表

  • 主键索引的叶子节点包含数据的全部信息，普通索引叶子节点存放的是主键索引，回到主键索引树搜索的过程叫做回表；

  • 避免回表：覆盖索引，因为所需要的数据都在叶子节点包含了，直接返回即可；like查询就可以使用覆盖索引



复合索引的最佳左前缀原则

例如：

  • 复合索引（a, b, c），只有（a），（a, b），（a, b, c），这几种情况；
where a = 1 and c = 2，a可以使用索引，c不能使用索引；
where b = 1 and a = 2，通过优化器等效为（a, b）所以都可以使用索引。
  • 带头大哥不能死，中间小弟不能断；

原理：

  • 索引底层是一颗B+树，构建B+树只能根据一个值来构建，当此值相等的时候才会根据下一个值构建，因为数据库依据联合索引最左的字段来构建B+树；
  • 让我联想到排序算法的稳定性，桶排序里面的基数排序（手机号排序问题），参考链接：https://blog.nowcoder.net/n/236418dae4fd4777b38602dc896228f8。

例如：

  • 按照a索引是有序的，1,1,2,2,3,3；
  • 按照b索引是无序的，1,2,1,4,1,2；





索引失效

  1. 不按照最佳左前缀原则；
  2. range类型查询字段后面的索引无效（between、<、>、order by、 in（正常会走索引，但是取值范围较大的时候索引失效））；
  3. like以通配符开头（%ABC...）会导致后面的索引失效；
  4. 尽量使用覆盖索引，减少select *；
  5. 使用（!=、<、>、is null、is not null）的时候会导致索引失效；
  6. or连接的时候只有一侧建立索引会索引失效；
  7. 在索引列上做任何操作（计算、函数、类型转换）会导致索引失效；
  8. 参考：cnblogs.com/bulushengse/p/12703789.html



索引下推

对于失效的索引（不满足最佳最前缀原则等），MySQL5.6引入索引下推进行优化，可以索引遍历的过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表的次数；
范围之后索引失效，只能根据name索引进行查找，但是还是会回表4次，但是通过索引下推，将age字段不满足的数据过滤，就可以只回表两次；
例如：
优化：


SQL优化

  • 使用explain + SQL分析
  • 将造成索引失效的字段放在后面



慢查询

通过语句查看：slow_query_log_file文件
show varables like '%slow_query_log%'
查看有几条慢查询语句 
show global status like '%show_query%'
根据慢日志文件里面记录的慢SQL。找到之后进行explain+SQL分析原因；