索引

mysql

1、索引底层-B+Tree

1.1 概念

• B+树是为磁盘或其他存取设备设计的一种平衡查找树，所有记录节点按照键值大小顺序存放在同一层的叶节点上，各叶节点通过指针进行链接，先来看一个B+树的结构图。

1.2 特征

• 非叶节点只存关键字以及索引下一层节点的指针
• 所有叶节点在同一层，包含全部关键字和指向记录的指针，并且按照关键字从小到大顺序链接，可以看到相比一般二叉树，B+树的单个节点能存储更多信息，减少了磁盘 IO 的次数，从而提升了查找速度，而且叶节点形成有序链表，非常适合进行范围查询。
• InnDB的主键索引叶节点上直接存储了行记录，行记录按物理顺序存储，也叫做聚簇索引，普通索引叶节点上存储的是主键索引值，称之为辅助索引。因此如果使用普通索引查询会走两遍索引：先通过辅助索引找到主键索引值，再到主键索引中检索获取记录行，这个过程叫回表,

1.3 一个 B+Tree索引可以索引多少行数据

• 以InnDB为例，最小存储单元页大小为16k，假设索引主键为bigint型，长度为8字节，InnDB中的指针长度为6字节，这样一个索引项大小为14字节，一个16k大小的节点可以存下的索引项是16k/14=1170，即一个节点能够索引1170个子节点。由于InnDB主键索引叶节点存储了记录全部信息，如果一行记录大小为1k，一个叶节点的记录数就为16k/1k=16，对于一个高度为3的B+树，能够索引记录数是1170*1170*16=21902400条，所以高度为3的B+树索引就足够索引千万级的数据了。
• 一次页查找就代表一次IO，因此通过主键索引只需要3次IO即可找到对应数据，如果是通过辅助索引查询则需要6次IO访问得到最终的数据页。

2、索引分类

2.1 按照物理结构划分

• 聚簇索引
  
  • 指索引的键值的逻辑顺序与表中相应行的物理顺序一致，即每张表只能有一个聚簇索引，也就是我们常说的主键索引；
• 非聚簇索引
  
  • 索引的逻辑顺序则与数据行的物理顺序不一致。

2.2 按照应用方式划分

• 普通索引：MySQL 中的基本索引类型，没有什么限制，允许在定义索引的列中插入重复值和空值，纯粹为了提高查询效率。通过 ALTER TABLE table_name ADD INDEX index_name (column) 创建；
• 唯一索引：索引列中的值必须是唯一的，但是允许为空值。通过 ALTER TABLE table_name ADD UNIQUE index_name (column) 创建；
• 主键索引：特殊的唯一索引，也成聚簇索引，不允许有空值，并由数据库帮我们自动创建；
• 组合索引：组合表中多个字段创建的索引，遵守最左前缀匹配规则；
• 全文索引：只有在 MyISAM 引擎上才能使用，同时只支持 CHAR、VARCHAR、TEXT 类型字段上使用。

3、索引的优缺点

• 优点：
  
  • 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
  • 可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
  • 可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。
  • 在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。
  • 通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。
• 缺点：
  
  • 创建和维护索引需要耗费时间，这种时间随着数据量的增加而增加，这样就降低了数据的维护速度。
  • 索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间。如果要建立聚簇索引，那么需要的空间就会更大。

4、索引设计原则

• 选择唯一性索引：
  
  • 唯一性索引的值是唯一的，可以更快速的通过该索引来确定某条记录。
• 为常作为查询条件的字段建立索引：
  
  • 如果某个字段经常用来做查询条件，那么该字段的查询速度会影响整个表的查询速度。因此，为这样的字段建立索引，可以提高整个表的查询速度。
• 为经常需要排序、分组和联合操作的字段建立索引：
  
  • 经常需要 ORDER BY、GROUP BY、DISTINCT 和 UNION 等操作的字段，排序操作会浪费很多时间。如果为其建立索引，可以有效地避免排序操作。
• 限制索引的数目：
  
  • 每个索引都需要占⽤用磁盘空间，索引越多，需要的磁盘空间就越大，修改表时，对索引的重构和更新很麻烦。
• 小表不建议索引（如数量级在百万以内）：
  
  • 由于数据较小，查询花费的时间可能比遍历索引的时间还要短，索引可能不会产生优化效果。
• 尽量使用数据量少的索引：
  
  • 如果索引的值很长，那么查询的速度会受到影响。此时尽量使用前缀索引。
• 删除不再使用或者很少使用的索引。

5、最左匹配原则

• 顾名思义，最左优先，以最左边为起点任何连续的索引都能匹配上。同时遇到范围查询（>、<、between、like）就会停止匹配。
• 如建立 (a,b,c,d) 索引，查询条件 b = 2 是匹配不到索引的，但是如果查询条件是 a = 1 and b = 2 或 a=1 又或 b = 2 and a = 1 就可以，因为优化器会自动调整 a,b 的顺序。
• 再比如 a = 1 and b = 2 and c > 3 and d = 4，其中 d 是用不到索引的，因为 c 是一个范围查询，它之后的字段会停止匹配。

• 上图可以看出 a 是有顺序的（1、1、2、2、3、3），而 b 的值是没有顺序的（1、2、1、4、1、2）。所以 b = 2 这种查询条件无法利用索引。
• 同时我们还可以发现在a值相等的情况下，b值又是按顺序排列的，但是这种顺序是相对的。所以最左匹配原则遇上范围查询就会停止，剩下的字段都无法使用索引。例如a = 1 and b = 2 a,b字段都可以使用索引，因为在a值确定的情况下b是相对有序的，而a>1and b=2，a字段可以匹配上索引，但b值不可以，因为a的值是一个范围，在这个范围中b是无序的。

6、覆盖索引

• 在 B+ 树的索引中，叶子节点可能存储了当前的键值，也可能存储了当前的键值以及整行的数据，这就是聚簇索引和非聚簇索引。 在 InnoDB 中，只有主键索引是聚簇索引，如果没有主键，则挑选一个唯一键建立聚簇索引。如果没有唯一键，则隐式的生成一个键来建立聚簇索引。
• 当查询使用聚簇索引时，在对应的叶子节点，可以获取到整行数据，因此不用再次进行回表查询。
• 查询的字段被使用到的索引树全部覆盖到。

• 例子：

  • 假设你定义一个联合索引

    CREATE INDEX idx_name_age ON user(name,age);

  • 查询名称为 liudehua 的年龄：

    mysql> select name, age from user where name = 'liudehua';

    上述语句中，查找的字段 name 和 age 都包含在联合索引 idx_name_age 的索引树中，这样的查询就是覆盖索引查询。

7、索引下推

• 索引下推（Index condition pushdown） 简称 ICP，在 Mysql 5.6 版本上推出的一项用于优化查询的技术。
• 在不使用索引下推的情况下，在使用非主键索引进行查询时，存储引擎通过索引检索到数据，然后返回给 MySQL 服务器，服务器判断数据是否符合条件。而有了索引下推之后，如果存在某些被索引列的判断条件时，MySQL 服务器将这一部分判断条件传递给存储引擎，然后由存储引擎通过判断索引是否符合 MySQL 服务器传递的条件，只有当索引符合条件时才会将数据检索出来返回给 MySQL 服务器。索引条件下推优化可以减少存储引擎查询基础表的次数，也可以减少 MySQL 服务器从存储引擎接收数据的次数。
• 索引覆盖是查询条件中正好被使用到的索引树全部覆盖到从而不再回表，索引下推是查询条件中有已经建立好索引的条件（不是唯一键），一般还需要至少回表一次。