本文主要以面试题为主梳理索引知识脉络
解决如下几个问题
- 索引是什么, 为什么要引入索引
- 有哪些索引的实现方式, 他们的优缺点是什么
- InnoDB的索引模型
- 主键索引与非主键索引的区别
- 选用什么作为主键, 为什么要用自增id 作为主键
...
如何实现索引? 实现索引的方式
Hash表
1.1 Hash 冲突 怎么处理
1.2 无法解决范围查询, 适用于等值查询的场景有序数组
2.1 有序数组的优点, 等值查询与范围查询性能优秀
2.2 查询记录成本太高, 只适用于静态存储二叉树
3.1 二叉树特点: 左节点<父节点<右节点
3.2 查询复杂度 ologn
3.3 维持平衡, 插入复杂度也是o(lgn)
3.4 二叉与多叉树，尽可能少的读取磁盘, 使用多叉树。至于多少叉，则取决于数据块的大小。扩展更多..
4.1 跳表
4.2 LSM树
InnoDB的索引模型
- 主键索引与非主键索引的区别
1.1 主键索引的叶子节点存储的是整行数据
1.2 非主键索引的叶子节点存储的是主键的值
通过非主键索引的查询需要多查询一颗B+树；应该尽量使用主键索引。 - 索引维护
2.1 页分裂
如果插入不是有序的，容易造成页分裂。
2.2 页合并
2.3 由页分裂引出的为何要有自增主键
自增主键，每次都是递增插入, 都是追加操作，不涉及挪动其他记录，不会触发叶子节点的分裂。
另外使用自增主键，可以使得普通索引的叶子节点占用空间越小。
重建索引可以使得索引更紧凑更利用空间。
覆盖索引
非主键索引查询结果（只查询自增id）已经满足了查询需求,不需要回表查询。
回表查询: 通过非主键索引查询到的结果，只是主键id，还需要根据主键id
联合索引使用技巧
联合索引中存在查询结果，就不需要进行回表
最左前缀原理，可以是联合查询的最左N个字段，也可以字符串最左M个字符串
由于索引使用的是B+树结构, 所以可以利用最左前缀来定位记录。
在建立索引的时候，如何安排索引的顺序
2.1. 通过调整索引顺序可以少维护一个索引
2.2. 空间（既有各自的查询，又有联合查询的时候）索引下推
MySQL5.6 引入: 在索引遍历过程中，对索引包含的字段先做判断，直接过滤掉不满足条件的记录，
减少回表次数。
