常见的索引

常见三种哈希表、有序数组和搜索树

哈希表

哈希表索引是一种键-值(key-value)存储结构。如果key hash之后出现冲撞，value会拉出来一个链表。

哈希表这种结构适用于只有等值查询的场景

有序数组

按照字段递增的顺序进行排序。如果是等值查询使用二分法就可以快速得到，这个时间复杂度是 O(log(N))。

有序数组在等值查询和范围查询场景中的性能就都非常帮，但是对于插入成本太高了，每次插入都需要挪动后面所有的记录。有序数组只适合静态数据(不会变化)

搜索树

查找和更新的时间复杂度均为O(logN)，但对于机械磁盘读写来说，需要放弃二叉树而使用N叉树。

InnoDB的索引模型

索引类型分为主键索引和非主键索引。在InnoDB引擎中，索引的模型采用了B+树结构。每一个索引在InnoDB里面都对应一棵B+树

主键索引的叶子节点存储的都是整行数据。在InnoDB主键索引也被称为聚簇索引(clustered index)。

非主键索引的叶子节点都是放的是主键的值，在InnoDB非主键索引也被称为二级索引(secondary index)。

基于主键索引和普通索引的查询有什么区别？

  • 主键索引: 会拿着值直接搜索这棵 B+树。
  • 普通索引：拿着值去查询普通索引树查询出来主键ID。然后拿着ID再去主键索引数据搜索一次。这个过程称为回表。

基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

回表查询

回到主键索引树搜索的过程，我们称为回表。

普通索引叶子节点是存储的主键值。每次查询普通索引得倒主键值，在根据主键值查询主键索引，这个过程是回表查询。

如何避免回表查询？覆盖索引

覆盖索引

把查询字段在普通索引内包含，这样就会避免再去查询主键索引。

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

索引维护

B+ 树为了维护索引的有序性，在插入新值的时候需要必要的维护，往往需要挪到数据页的数据，会产生页分裂和页合并。

页分裂和页合并

页分裂：申请新的数据页，挪动部分数据从旧数据页到新数据页。不仅有性能问题，还会占用空间。

页合并：相邻两个页由于删除了数据，利用率很低之后，会将两个数据页合并。

自增主键

使用自增主键，每次插入新纪录都是追加，不涉及挪动其他记录，因此效率最高（性能），非主键索引占用的空间也最小（存储空间）。

主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。

从性能和存储空间方面考量，自增主键往往是更合理的选择。

最左前缀原则

B+ 树这种索引结构，可以利用索引的“最左前缀”，来定位记录。索引项是按照索引定义里面出现的字段顺序排序的。

当你的逻辑需求是查到所有名字是“张三”的人时，可以快速定位到 ID4，然后向后遍历得到所有需要的结果。

如果你要查的是所有名字第一个字是“张”的人，你的 SQL 语句的条件是”where name like ‘张 %’”。这时，你也能够用上这个索引，查找到第一个符合条件的记录是 ID3，然后向后遍历，直到不满足条件为止。

可以看到，不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

在建立联合索引的时候，如何安排索引内的字段顺序。

第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

第二原则是，如果不得不维护另外的索引，那么需要考虑存储空间的大小。

比如联合索引(a,b)，如果既有(a,b)联合索引，查询和a,b单独查询的时候，我们要建立(a,b)联合索引和(b)索引两个索引。如果b的字段比a的字段要大，就需要考虑一下空间了，就可以建立(b,a)联合索引,(a)两个索引。

索引下推

市民表的联合索引（name, age）为例。如果现在有一个需求：检索出表中“名字第一个字是张，而且年龄是 10 岁的所有男孩”。那么，SQL 语句是这么写的

1
mysql> select * from tuser where name like '张 %' and age=10 and ismale=1;

你已经知道了前缀索引规则，所以这个语句在搜索索引树的时候，只能用 “张”，找到第一个满足条件的记录 ID3。当然，这还不错，总比全表扫描要好。

使用前缀索引规则匹配索引的前几个字符值，然后再去过滤数据。

在 MySQL 5.6 之前，只能从 索引查询到匹配的值然后开始一个一个回表。到主键索引上找出数据行，再对比字段值。

而 MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

普通索引和唯一索引，应该怎么选择？

查询差别

普通索引，普通索引查询到满足的第一个条件，然后会在继续执行查询，直至到不满足查询条件为止。

唯一索引，由于索引的唯一性，查询到第一个满足的条件就会终止查询。

严格来说，唯一索引的搜索过程比较快，因为”回表”的数据记录少，但是在实际操作中，这两种索引的带来的消耗几乎相等，差别微乎其微。

更新差别

普通索引的更新，会使用到change buffer；

唯一索引的更新，不会使用到change buffer;

什么是change buffer？

change buffer是内存中的一块区域，它保存在Innodb的buffer pool中，它在磁盘上也有对应的持久化空间，在系统表空间ibdata中。通过参数 innodb_change_buffer_max_size 来动态设置。这个参数设置为 50 的时候，表示change buffer 的大小最多只能占用 buffer pool 的 50%。

当需要更新一个数据的时候，如果数据页在内存有这条消息就直接更新，而如果这个数据页不在内存，innoDB就会直接更新操作缓存的change buffer，下次访问磁盘上的数据页的时候，就会把数据页加载到内存中，然后执行 change buffer 中与这个页有关的操作。通过这种方式，有两个好处：

  • 如果能够将更新操作先记录在 change buffer，减少读磁盘，语句的执行速度会得到明显的提升
  • 数据读入内存是需要占用 buffer pool 的，所以这种方式还能够避免占用内存，提高内存利用率

应用change buffer中与该数据页相关的操作的这个过程，我们称之为数据页的merge操作，merge操作在以下的场景下会触发

  • 访问数据页时候
  • 后台线程每秒都会merge
  • 数据库正常启停
为什么唯一索引不能使用change buffer？

唯一索引在做insert或者update的时候，需要判断索引记录的唯一性，而判断唯一性必须要在内存中判断，所以数据页会被加载到内存中，如果数据页已经加载到了内存中，那么当然是直接更新内存更快了。

唯一索引的更新就不能使用 change buffer，实际上也只有普通索引可以使用。

唯一索引和普通索引在更新差别
更新记录在内存中

普通索引:就会更新数据的范围直接在数据页上插入

唯一索引:会多一步check操作。会check更新的数据范围是否存在这个值。

当记录在内存中的时候，这俩差别不大，仅仅是唯一索引多了一步判断唯一性的操作。这个判断，仅仅会消耗很小一部分cpu的资源。

更新记录不在内存中

  • 对于唯一索引来说，需要将数据页读入内存，判断到没有冲突，插入这个值，语句执行结束；

  • 对于普通索引来说，则是将更新记录在 change buffer，语句执行就结束了。

普通索引利用了change buffer，减少了磁盘上的随机访问，对性能的提升比较明显。

change buffer使用场景

在一些写多读少的业务中，change buffer能够发挥很好的作用。它可以将多次对磁盘的操作，合并成一次merge操作，从而提高MySQL的性能，一次性merge的操作越多，收益就越大。但是需要注意，如果你的数据写入之后。立马会读取(也就意味着需要从磁盘读取到内存)，那么建议不要使用change buffer，因为在这种情况下，使用change buffer不会减低IO次数，反而多了change buffer的维护开销。

change buffer和redo log的交互

当我们要更新一条普通索引记录的时候：

  • 如果这条记录在内存中，那么直接更新内存；

  • 如果该记录没有在内存中，那么就需要更新change buffer

  • 更新完change buffer之后，MySQL会在redo log中记录下change buffer的修改，

  • 事务就算完成了，后续binlog落盘，redo log commit

  • 当需要读取不在内存中的记录时，会将该数据页从磁盘加载到内存，然后应用change buffer中的修改，也就是merge操作

MySQL 为什么有时候会选错索引？

优化器逻辑

选择索引就是优化器的工作，优化器会选择一个扫描的行数少，意味着访问磁盘数据的次数越少，消耗的 CPU 资源越少。

优化器还会结合是否使用临时表、是否排序等因素进行综合判断，简单的查询语句并没有涉及到临时表和排序，所以 MySQL 选错索引肯定是在判断扫描行数的时候出问题了。

如何解决MYSQL选错索引

  • 如果是MYSQL索引信息统计错误，则可以使用 analyze table table_name 命令来解决。

  • 可以使用 force index(index_name) 来强制使用某索引。
    例如： select * from t force idnex(a) ; t为表名，a为索引名

  • 可以选择新建合适的索引，或者将错误的不重要的索引删除。

  • 可以修改SQL语句，诱导MYSQL使用正确的索引。