关于MySQL索引的一些个人理解（部分参考MySQL45讲）

概述

写了 MySQL索引的数据结构、覆盖索引、最左前缀法则，索引下推以及我遇到的一到面试题。

索引是什么

索引的出现就是为了提高查询效率，如同书的目录

索引的数据结构

哈希表

是一种key-value的结构，相同key值用拉链法
在等值查询的场景下效率非常高，
对于有序的数组，范围查询使用有序数组效率可以以达到O(log(N))，但是，维护一个有序的数组成本太高，需要不断移动数据，所以有序数据只适合静态的存储引擎。

二（N）叉树

使用二叉树的时候，可能会导致树过高，索引不仅在内存中，还要写到磁盘上。每次查询都要经过很多不需要的节点，访问的数据快过多，过于耗时。
所以可以使用N叉树，可以减少读磁盘！在InnoDB中，N为1200，树高为4，则可以存储120012001200，有17亿的数据。

InnoDB：B+树

每一个索引在InnoDB中都对应一棵B+树。
主键索引的叶子结点存了整行数据，主键索引又称聚簇索引。
非主键索引的叶子节点是主键值。非主键索引也被称为二级索引。

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

对于主键查询，直接搜索ID这颗B+树
而非主键索引找到ID再到ID索引书搜索，这个过程称为回表。

• 为什么使用bigint递增主键？

这样的插入是追加操作，不会需要挪动其他记录，不也不会出发也子节点的分裂。
而且假设我们用varchar做主键，例如雪花算法要19个字节（不同的编码方式不同），而bigint 也只要8个字节，主键的长度短了带来了叶子结点的减少，普通索引占的空间也少了。

• 为什么用B+树？

1. 树不高，能够存书大量数据
2. B+树的非叶子节点单页能存储更多的关键字，一次读入内存的关键字越多，磁盘的随机 I/O 读取次数就越少。减少单次查询的磁盘访问次数。（内存存放了更多的key，数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。）
3. B+树可以很好的支持单点查询，范围查询，有序性查询（叶子结点链表）。
4. B+树查询效率更稳定，必然是O(logN)，

• 为什么不用B树？

1. B树叶子结点要存放数据，深度变大，I/O次数增多，查询性能降低

覆盖索引

查索引的时候都会回表，这样就要查两次索引，如何优化索引从而避免回表？
那就是使用覆盖索引。
覆盖索引已经包含了查询结果，不需要回表，减少了搜索次数，显著提高了查询性能。

• 如何权衡是否需要添加覆盖索引？

如果是一个高频的请求，联合索引就有意义，减少了语句的执行时间，但是索引的维护有代价。

最左前缀法则

这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。（比如 like 张%，可以先找到张xx）
但是如果（a，b),在a字段上使用张%，b字段就失效了。（mysql 会一直向右匹配直到遇到范围查询（>、<、between、like）就停止匹配。范围列可以用到索引，但是范围列后面的列无法用到索引。即，索引最多用于一个范围列，因此如果查询条件中有两个范围列则无法全用到索引----------为什么呢，以为索引是按字典序排列的，第一有序不能保证之后的也有序。）

• 如何选择索引？

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

比如(a,b）的联合索引同时满足(a,b)和（a），但是（b）不满足

索引下推

举一个例子
现在有(a,b)的联合索引，但是要查a、b、c数据
然后a用 张%，显然b会失效。
5.6之前的版本 在匹配完张后，所有的数据会直接回表。
5.6之后的版本 在匹配完张，会得到b（联合索引中有），和要查的b值比较，如果错误直接丢弃，就减少了回表的次数

一道面试题

之前面试百度遇到下面这道题，我全程可能应该…
（a,b,c）字段有索引（a），索引（b）和索引（a，b，c）
查询条件的是a和b的时候，走两个单独的索引快，还是走联合索引快？
这里不知道内部优化是什么样的，但是联合索引肯定是不需要回表的，显然是后者快。

测试600w条数据，毋庸置疑使用联合索引

删除联合索引，留下单列索引，直接变成全表扫描，
带上查询条件之后，虽然用到了索引，但仍然是全表扫描，效率极差
综上所述，覆盖索引yyds！