MySQL索引
索引
索引的出现就是为了提高查询效率，就像书的目录一样。
索引的常见模型
哈希表
是一种键值存储的数据结构，当哈希值冲突时可以用一个链表解决。
优点是新增数据时候执行很快，只需要追加就可以。但是由于不是有序的，对于区间查询是很慢的，必须要全表扫描。
有序数组
有序数组在等值查询和范围查询场景中的性能都非常优秀。
查询时可以用二分法，时间复杂度是 O(log(N))。
缺点是数据更新速度很慢，插入一条数据需要把此条记录后面的数据都往后挪动一位。
有序数组只适用于静态存储引擎。
二叉树
搜索速度是O(log(N))，当然为了维持查询复杂度就需要保持这是一颗平衡二叉树，更新的时间复杂度也是O(log(N))。
由于索引不只存储在内存中，还要写到磁盘上，所以大多数数据库使用多叉树。而这个多叉N取决于数据块的大小。
以InnoDB的一个整数字段索引为例，这个N差不多是1200。这树高4的时候，可以存储1200的3次方个值，17亿。
其他模型
这些模型都是不断迭代不断优化的产物或者解决方案，跳表、LSM树等数据结构也被用于引擎设计中。
数据库的底层存储核心就是基于这些数据模型的，对于一个数据库，我们需要先关注他的数据类型，才能从理论上分析出这个数据库的适用场景。
InnoDB的索引模型
在MySQL中索引是存储引擎层实现的，并没有统一的索引标准，不同引擎的索引工作方式不一样。
InnoDB中表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。
InnoDB使用B+树索引模型，数据都是存储在B+树种，每一个索引对应一颗B+树。
假设有一个主键为id，其中一个字段为k，并且k建立索引。那么在这两颗树中，主键索引的叶子节点存储的是整行数据，而k索引中叶子节点只存储主键id。
所以根据叶子节点的数据内容，索引的类型分为主键索引和非主键索引。
那么，基于主键索引和非主键索引的查询有什么区别呢？
- 如果条件是id，那么只需要遍历id这棵树。
- 如果条件是k，就需要先根据k树查询id，再根据id查询数据。这个过程称为回表。
索引维护
B+树为了维护有序性，插入元素时需要做必要的维护。
- 插入数据在最后，追加就可以
- 插入数据在中间，需要逻辑上移动后面的数据
- 如果插入的数据页满了，需要新申请一个数据页，挪动部分数据过去，称为页分裂，整体空间利用率降低大约50%
- 删除数据后可能需要做页合并，分裂的逆过程
自增主键的插入数据模式，符合了递增插入的场景，而且也不会触发叶子节点的分裂。
而自定义主键往往不容易保证有序插入，写入成本相对较高。
存储空间方面，长整型8字节，显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间就越小。
所以大多数场景中自增主键往往是更合理的选择。
自定义主键使用场景：只有一个索引且该索引唯一。这是典型的KV场景。
覆盖索引
如果执行select ID from T where k between 3 and 5，只需要查id的值，id已经在k索引树上了，就不需要回表，索引k已经覆盖了查询需求，称为覆盖索引。可以减少查询次数，显著提高性能。
最左前缀原则
不只是索引的全部定义，只要满足最左前缀，就可以利用索引加速。可以是联合索引的最左N个字段，也可以是字符索引的最左M个字符。
在建立联合索引的时候如何安排索引内字段顺序？
主要看的是索引的复用能力。如果通过调整顺序，可以少维护一个索引，那么这个顺序就是需要优先考虑采用的。
索引下推
可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。
普通索引和唯一索引的选择
查询过程
假设执行的语句是select id from T where k=5。
- 对于普通索引来说，查到满足条件的记录后，需要查找下一个记录，直到不满足
k=5条件的记录 - 对于唯一索引来说，由于唯一性，找到后就停止
那么对性能的影响呢？微乎其微。
更新过程
change buffer
当需要更新一个数据页时，如果数据页在内存中就直接更新。如果不在内存中，不影响数据一致性的前提下，InnoDB会将这些操作缓存在change buffer中，就不需要从磁盘中读入这个数据页了。下次查询需要访问这个数据页时，将数据页读入内存，然后执行change buffer中与这个页相关的操作。
将 change buffer 中的操作应用到原数据页，得到最新结果的过程称为merge。除了访问这个数据页触发外，系统后台线程会定期merge，数据库正常关闭也会执行。
什么条件下可以使用change buffer？
对于唯一索引来说，所有更新操作都需要判断这个操作是否违反唯一性，必须要将数据页读入内存中才能判断，如果已经到了内存中就没必要使用change buffer。
唯一索引的更新不能使用change buffer，实际上也只有普通索引可以使用。
chenge buffer使用场景
因为merge的时候是真正进行数据更新的时刻，而change buffer的主要目的就是记录的变更动作缓存下来，所以在merge之前记录的变更越多收益越大。
反过来，假设一个业务的更新模式是写入后马上会做查询，会立即出发merge过程。这样随机访问IO的次数不会减少，反而增加了change buffer的维护代价。
索引的选择
这两类索引在查询能力上是没有差别的，主要考虑的是更新对性能呢的影响。
由于唯一索引用不上change buffer优化机制，因此如果业务可以接受的情况下，可以先考虑非唯一索引。
内容主要来自极客时间