MySQL 索引

本文主要以面试题为主梳理索引知识脉络
解决如下几个问题

1. 索引是什么, 为什么要引入索引
2. 有哪些索引的实现方式, 他们的优缺点是什么
3. InnoDB的索引模型
4. 主键索引与非主键索引的区别
5. 选用什么作为主键, 为什么要用自增id 作为主键
   ...

如何实现索引? 实现索引的方式

1. Hash表
   1.1 Hash 冲突 怎么处理
   1.2 无法解决范围查询, 适用于等值查询的场景

2. 有序数组
   2.1 有序数组的优点, 等值查询与范围查询性能优秀
   2.2 查询记录成本太高, 只适用于静态存储

3. 二叉树
   3.1 二叉树特点: 左节点<父节点<右节点
   3.2 查询复杂度 ologn
   3.3 维持平衡, 插入复杂度也是o(lgn)
   3.4 二叉与多叉树，尽可能少的读取磁盘, 使用多叉树。至于多少叉，则取决于数据块的大小。

4. 扩展更多..
   4.1 跳表
   4.2 LSM树

InnoDB的索引模型

1. 主键索引与非主键索引的区别
   1.1 主键索引的叶子节点存储的是整行数据
   1.2 非主键索引的叶子节点存储的是主键的值
   通过非主键索引的查询需要多查询一颗B+树；应该尽量使用主键索引。
2. 索引维护
   2.1 页分裂
   如果插入不是有序的，容易造成页分裂。
   2.2 页合并
   2.3 由页分裂引出的为何要有自增主键
   自增主键，每次都是递增插入, 都是追加操作，不涉及挪动其他记录，不会触发叶子节点的分裂。
   另外使用自增主键，可以使得普通索引的叶子节点占用空间越小。
   重建索引可以使得索引更紧凑更利用空间。

覆盖索引

非主键索引查询结果（只查询自增id）已经满足了查询需求,不需要回表查询。
回表查询: 通过非主键索引查询到的结果，只是主键id，还需要根据主键id

联合索引使用技巧

1. 联合索引中存在查询结果，就不需要进行回表

2. 最左前缀原理，可以是联合查询的最左N个字段，也可以字符串最左M个字符串
   由于索引使用的是B+树结构, 所以可以利用最左前缀来定位记录。
   在建立索引的时候，如何安排索引的顺序
   2.1. 通过调整索引顺序可以少维护一个索引
   2.2. 空间（既有各自的查询，又有联合查询的时候）

3. 索引下推
   MySQL5.6 引入: 在索引遍历过程中，对索引包含的字段先做判断，直接过滤掉不满足条件的记录，
   减少回表次数。