最近，Python小新 参加了一个微信面试

你还参加过哪些奇葩的面试，欢迎留言分享你的经验。

Python小新 发了他 MySql 微信面试情况

既然 MySql 索引是每个面试官必问的话题之一

今天我们一起聊聊 MySql 索引那些“八卦”

什么是索引？

索引其实是一种数据结构，能够帮助我们快速的检索数据库中的数据

① 索引好比新华字典的目录，我们可以根据笔画、拼音查找

② 索引也像图书馆书的编号，根据编号找到对应的分类

索引是为提高数据查询速度而存在的

是“以空间换时间”（索引存储占用磁盘空间，但提高查询效率）

如果合理设计和使用索引的 MySQL 是一辆兰博基尼的话

那么没有设计和使用索引的 MySQL 就是一辆 ofo 小黄车

MySql 索引的数据结构是什么？

MySql 索引主要有两种数据结构：

① Hash

只有 Memory（ Memory 表只存在内存中，断电会消失，适用于临时表）存储引擎显示支持 Hash 索引，是 Memory 表的默认索引类型。

② B+Tree

B+Tree 是 MySql 使用最频繁的一个索引数据结构，是 Innodb 和 Myisam 存储引擎模式的索引类型。

为什么 MySql 在 Innodb 和 Myisam 存储引擎中使用 B+tree，而不用 Hash、有序数组、二叉树、B-Tree？

Hash 把数据的索引以 key-value 组织起来，每个键只对应一个值，而且是散列的方式分布。因此当查找某一条记录的时候，速度非常快，但是他并不支持范围查找和排序等功能，如果出现大量重复的 value ，Hash 将为解决 Hash 冲突而耗费很多时间，只适用于只有等值查询的场景。

Hash表

有序数组在等值查询和范围查询场景中的性能都非常优秀。用二分法就可以快速找到（时间复杂度为 O (logN)）。但是如果要往中间插入一条数据，则必须挪动后面的所有记录，成本较高。因此，有序数组只适用于静态存储引擎，即数据表一旦建立后不再会修改。

有序数组

无论是二叉树还是红黑树，在数据量大的情况下，树的高度比较高，会增加磁盘 IO。

二叉树

红黑树

B+Tree 的高度在1-3之间，大大减少磁盘I/O读取

B+Tree 所有索引数据都在叶子节点上，并且增加了顺序访问指针,每个叶子节点都有指向相邻叶子节点的指针，提高区间查询效率。

B-Tree 和 B+Tree 有什么区别？

注意：B-Tree，读“BTree”，不要读成“B减Tree”

B-Tree

B+Tree

在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。

InnoDB 和 MyISAM 存储引擎索引的异同？

① InnoDB 和 MyISAM 存储引擎索引的数据结构都是 B+Tree

② MyISAM 索引实现

MyISAM 索引文件和数据文件是分离的，索引文件的 data 域保存记录所在页的地址（物理存储位置），通过这些地址来读取页，进而读取被索引的行数据。MyISAM 的索引方式也叫做 “非聚集” 的。

I、主键索引

II、辅助索引

在 MyISAM 中，主索引和辅助索引在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复

② InnoDB 索引实现

InnoDB 表数据文件本身就是一个索引结构，树的叶节点 data 域保存了完整的数据记录，这种索引叫做聚集索引。

I、主键索引

因为 InnoDB 的数据文件本身要按主键聚集，所以 InnoDB 要求表必须有主键 (MyISAM 可以没有)，如果没有显式指定，则 mysql 会自动选择一个可以唯一标识数据记录的列作为主键。如果不存在这种列，则 mysql 自动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为 6 个字节，类型为长整型。

II、辅助索引

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

什么是索引回表？

第一遍先通过辅助索引定位到主键值 id，然后第二遍再通过聚集索引定位到具体行记录，这就是所谓的回表查询，即先定位主键值，再根据主键值定位行记录，性能相对于只扫描一遍聚集索引树的性能要低一些。

什么是索引覆盖？

如果一个索引覆盖（包含）了所有需要查询的字段的值，这个索引就是覆盖索引。

因为索引中已经包含了要查询的字段的值，因此查询的时候直接返回索引中的字段值就可以了，不需要再到表中查询，避免了对主键索引的二次查询，也就提高了查询的效率。

什么是联合索引，什么是“最左匹配原则”？

联合索引是指对表上的多个列进行索引。在 mysql 建立联合索引时会遵循最左前缀匹配的原则，即最左优先，在检索数据时从联合索引的最左边开始匹配。

● 联合索引数据结构

简单分析一下上图，idx_t1_bcd 索引上有 [b,c,d] 三个字段 (注意：若是 InnoDB 类的聚簇索引表，idx_t1_bcd 上还会包括主键 a 字段)，不包括 [a,e] 字段。idx_t1_bcd 索引，首先按照 b 字段排序，b 字段相同，则按照 c 字段排序，以此类推。记录在索引中按照 [b,c,d] 排序，但是在堆表上是乱序的，不按照任何字段排序。

● 联合索引 (a,b,c)

联合索引 (a,b,c) 实际建立了 (a)、(a,b)、(a,b,c) 三个索引

我们可以讲组合索引想成书的一级目录、二级目录、三级目录，如index(a,b,c)，相当于a是一级目录，b是一级目录下的二级目录，c是二级目录下的三级目录。要使用某一目录，必须先使用其上级目录，除了一级目录除外。

所以：

where a=1 and c=1只使用了一级目录，c在三级目录，没有使用二级目录，那么三级目录就没法使用

where a=1 and b=1只使用了一级目录、二级目录。

注意：这两个查询语句都会用到索引 (a,b)，mysql 创建联合索引的规则是首先会对联合合索引的最左边的，也就是第一个字段 a 的数据进行排序，在第一个字段的排序基础上，然后再对后面第二个字段 b 进行排序。其实就相当于实现了类似 order by a b 这样一种排序规则。

有人会疑惑第二个查询语句不符合最左前缀匹配：首先可以肯定是两个查询语句都包含索引 (a,b) 中的 a、b 两个字段，只是顺序不一样，查询条件一样，最后所查询的结果肯定是一样的。既然结果是一样的，到底以何种顺序的查询方式最好呢？此时我们可以借助 mysql 查询优化器 explain，explain 会纠正 sql 语句该以什么样的顺序执行效率最高，最后才生成真正的执行计划。

● 联合索引的优势？

① 减少开销

建一个联合索引 (a,b,c) ，实际相当于建了 (a)、(a,b)、(a,b,c) 三个索引。每多一个索引，都会增加写操作的开销和磁盘空间的开销。对于大量数据的表，使用联合索引会大大的减少开销！

② 覆盖索引

对联合索引 (a,b,c)，如果有如下 sql 的，那么 MySQL 可以直接通过遍历索引取得数据，而无需回表，这减少了很多的随机 io 操作。减少 io 操作，特别的随机 io 其实是 dba 主要的优化策略。所以，在真正的实际应用中，覆盖索引是主要的提升性能的优化手段之一。

③ 效率高

索引列多，通过索引筛选出的数据越少。有 1000W 条数据的表，有如下 sql:select from table where col1=1 and col2=2 and col3=3, 假设假设每个条件可以筛选出 10% 的数据，如果只有单值索引，那么通过该索引能筛选出 1000W10%=100w 条数据，然后再回表从 100w 条数据中找到符合 col2=2 and col3= 3 的数据，然后再排序，再分页；如果是联合索引，通过索引筛选出 1000w10% 10% *10%=1w，效率提升可想而知！

● 索引是建的越多越好吗？

答案是否定的

① 数据量小的表不需要建立索引，建立会增加额外的索引开销

② 不经常引用的列不要建立索引，因为不常用，即使建立了索引也没有多大意义

③ 经常频繁更新的列不要建立索引，因为肯定会影响插入或更新的效率

④ 数据重复且分布平均的字段，因此他建立索引就没有太大的效果

例如性别字段，只有男女，不适合建立索引

⑤数据变更需要维护索引，意味着更多的索引意味着更多的维护成本

⑥ 更多的索引也需要更多的存储空间

什么是索引下推？

（Index Condition Pushdown，ICP）全称是索引条件下推

● 联合索引(name,age)

● 根据前面说的 “最左匹配原则”，该语句在搜索索引树的时候，只能匹配到名字第一个字是‘张’的记录（即记录 ID3），接下来是怎么处理的呢？当然就是从 ID3 开始，逐个回表，到主键索引上找出相应的记录，再比对 age 和 ismale 这两个字段的值是否符合。

● 但是！MySQL 5.6 引入了索引下推优化，可以在索引遍历过程中，对索引中包含的字段先做判断，过滤掉不符合条件的记录，减少回表字数。

欢迎阅读其他 MySql “未解之谜”系列文章 >>>

Python 之 MySql“未解之谜”07-- 不懂事务，面试官全程黑脸