MySQL-index

索引介绍

生活中随处可见索引的例子，例如词典、火车站车次表、图书目录等。他们的原理和目标都是一样的，就是通过不断缩小想要获取数据的范围，将随机的时间变成顺序的事件，也就是我们总是通过同一种查询方式来锁定数据。
对于MySQL，索引是一个单独的、存储在磁盘上的数据库结构，它们包含着对数据表里所有记录的引用指针。使用索引用于快速找出在某个或多个列中有一特定值的行，所有MySQL列类型都可以被索引，对相关列使用索引是提高查询操作速度的最佳途径。

索引结构

HASH索引

Hash索引是一种常见的索引，它的单条记录查询的效率非常高，时间复杂度为O(1)。但是Hash索引却不是常用的数据库索引类型，MySQL innodb存储引擎就不支持Hash索引。主要有以下原因：

• Hash索引适合KV类型的数据查询，但是对于范围查询不合适，因为它是无序的

有序数组

有序数组用于等值查询和范围查询表现都很优秀，但是作为数组存在一个致命缺陷，就是如果数据有更改的话，会导致他的更改节点后续的节点都需要改变。因此有序数组更适合于存储静态数据。
对于历史数据例如淘宝历史订单/支付宝历史账单等数据就很适合使用有序数组。

二叉树

先来介绍下二叉树的特点：

• 1. 二叉树的时间复杂度为 O(n)
• 1. 一个节点只能有两个子节点。即度不超过2
• 1. 左子节点 小于 本节点，右子节点 大于 本节点

极端情况下会出现二叉树链化的情况，其次二叉树在数据量越来越多时层高也会随之增加，层高越高就代表IO次数越多，检索效率越慢

B树

从B树的结构图中可以看到每个节点中不仅包含数据的 key 值，还有 data 值。

而每页的存储空间是有限的，如果 data 比较大，会导致每个节点的 key 存储的较少，当数据量较大的时候，同样会导致B树很深，从而增加了磁盘 IO 的次数，进而影响查询效率。

B+树

MySQL 中最常用的索引的数据结构是 B+ 树，他有以下特点：

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

InnoDB中，最小存储单元是页，1页的大小约16k，一个节点的大小就是16k，也就是说B+树每个节点可以存储16k的数据。
假设主键类型为bigint，大小为8Byte，指针可以占有6Byte，总共14Byte，则可以计算出一个非叶子节点可以存放大概16KB/14B=1170个“主键+指针组合”；
主键类型为int，大小为4Byte，指针6Byte，共10Byte，可计算出大概存放16KB/10K=1600数据；
叶子节点需要存放数据，假设一条数据的大小是1k，则叶子节点可存储16条数据。
因此bigint类型：
两层B+树：1170 * 16= 18720
三层B+树：1170 * 1170 * 16 = 21902400
int类型则翻倍

索引创建原则

索引是建立在数据库表的某些列上的 。因此，在建立索引的时候，就需要考虑某些列应该寄哪里索引，某些列不应该建立索引。

应该建立索引的列

• 在经常需要搜索的列上，可以加快搜索的速度
• 在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构
• 在经常用在连接（JOIN）的列上，这些列主要是一外键，可以加快连接的速度
• 在经常需要根据范围（<，<=，=，>，>=，BETWEEN，IN）进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的
• 在经常需要排序（order by）的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间；
• 在经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度。

不应该建立索引的列

• 对于那些在查询中很少使用或者参考的列不应该创建索引。
  若列很少使用到，因此有索引或者无索引，并不能提高查询速度。相反，由于增加了索引，反而降低了系统的维护速度和增大了空间需求。
• 对于那些只有很少数据值或者重复值多的列也不应该增加索引。
  这些列的取值很少，例如人事表的性别列，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度。
• 对于那些定义为text, image和bit数据类型的列不应该增加索引。
  这些列的数据量要么相当大，要么取值很少。
• 当该列修改性能要求远远高于检索性能时，不应该创建索引。（修改性能和检索性能是互相矛盾的）

索引类别

• 主键索引：一张表仅有一个主键索引，不允许重复，不允许为null

ALTER TABLE tableName ADD PRIMARY KEY(column);

• 唯一索引：数据列不允许重复，允许为null值，一个表可存在多个唯一索引。如果是组合索引，则索引列的值必须唯一。

CREATE UNIQUE INDEX indexName ON tableName('column'(length))
# or
ALTER TABLE tableName ADD UNIQUE (column);

• 普通索引：一张表允许创建多个普通索引，数据列允许重复，允许为null。

CREATE INDEX IndexName ON `TableName`(`字段名`(length));
# 或者
ALTER TABLE TableName ADD INDEX IndexName(`字段名`(length));

• 全文索引：它查找的是文本中的关键字，用于全文检索。

• 聚簇索引：聚簇索引不是单独的一种索引类型，而是一种数据存储方式。这种存储方式是依靠B+树来实现的，根据表的主键构造一棵B+树且B+树叶子节点存放的都是表的行记录数据时，方可称该主键索引为聚簇索引。聚簇索引也可理解为将数据存储与索引放到了一块，找到索引也就找到了数据。

• 非聚簇索引：数据和索引是分开的，B+树叶子节点存放的不是数据表的行记录。非聚簇索引查询时需要首先拿到主键索引，然后回表重新拿到数据。

索引下推

什么是索引下推

索引下推（Index Condition Pushdown，简称ICP），是MySQL5.6后的新特性，可以减少回表查询次数，提高查询效率。

索引下推原理

MySQL服务层负责SQL语法解析，生成执行计划等，并调用引擎层去执行数据的存储和检索。
索引下推 的下推 是将部分上层（服务层）负责的事情，交给下层（引擎层）去处理。

未使用ICP，MySQL的查询：

1. 存储引擎读取索引记录；
2. 根据索引中的主键值，定位并读取完整的行记录；
3. 存储引擎把记录交给Server层去检测该记录是否满足Where检索条件
   使用ICP，MySQL的查询：
4. 存储引擎读取索引记录（不是完整的行记录）；
5. 判断Where条件部分能否用索引中的列来做检查，条件不满足，则处理下一行索引记录；
6. 条件满足，使用索引中的主键去定位并读取完整的行记录（回表）；
7. 存储引擎把记录交给Server层，Server层判断该记录是否满足Where条件的其余部分。

索引下推使用条件

• 只能用于range、 ref、 eq_ref、ref_or_null访问方法；
• 只能用于InnoDB和 MyISAM存储引擎及其分区表；
• 对InnoDB存储引擎来说，索引下推只适用于二级索引（也叫辅助索引）;

索引下推的目的是为了减少回表次数，也就是要减少IO操作。对于InnoDB的聚簇索引来说，数据和索引是在一起的，不存在回表这一说。

• 引用了子查询的条件不能下推；
• 引用了存储函数的条件不能下推，因为存储引擎无法调用存储函数。

索引失效

• 当我们使用左或者左右模糊匹配的时候，也就是 like %xx 或者 like %xx% 这两种方式都会造成索引失效；

• 当我们在查询条件中对索引列使用函数，就会导致索引失效。

• 当我们在查询条件中对索引列进行表达式计算，也是无法走索引的。

• MySQL 在遇到字符串和数字比较的时候，会自动把字符串转为数字，然后再进行比较。如果字符串是索引列，而条件语句中的输入参数是数字的话，那么索引列会发生隐式类型转换，由于隐式类型转换是通过 CAST 函数实现的，等同于对索引列使用了函数，所以就会导致索引失效。

• 联合索引要能正确使用需要遵循最左匹配原则，也就是按照最左优先的方式进行索引的匹配，否则就会导致索引失效。

• 在 WHERE 子句中，如果在 OR 前的条件列是索引列，而在 OR 后的条件列不是索引列，那么索引会失效。