索引

索引是为了更快的查询数据。

索引常见的模型

哈希表是一个数组，通过哈希算法，将Key计算出数组中的一个确定的位置，再把Value放进数组中。
如果哈希冲突，则多个Value存在一个链表中。由于哈希表不是有序的，做区间查询，必须全部扫描一遍。
因此哈希表存储的索引，只适合等值查询。

有序数组在等值查询和范围查询场景中的性能就都非常优秀。有序数组按照字段值按顺序保存。

等值查询用二分法就能快速得到，其时间复杂度为 $O(log(n))$ 。

区间查询时，先用二分法查出大于等于小值得第一个数据，再遍历查出小于等于大值的最后一条数据。

但是在更新的时候，一旦向数组中间插入一条记录，则其后的所有数据都要进行后移操作。

二叉搜索树的特点是，一个父节点的左子树的所有节点的值均小于父节点的值，右子树的所有节点的值均大于父节点的值。

查询时的时间复杂度为 $O(log(n))$ 。

为了维护这棵树是平衡二叉树，更新的时间复杂度也是 $O(log(n))$ 。

一个二叉树，如果数据量很大，将导致树很高。从磁盘读取大量的数据块将会造成大量的IO延迟。为了让一个查询尽可能少的读磁盘，就必须让查询过程访问更少的数据块。

N叉树的每一个节点，有多个子节点，子节点间从左到右保证按照从小到大的顺序。大大减少了树的层高，提高了IO效率。

索引是在引擎层实现的，不同引擎的索引实现方式不同。在InnoDB中，表中的数据是根据主键顺序，以索引的形式存放的。每一个索引都对应一颗B+树。

根据叶子节点的内容，索引类型分为主键索引和非主键索引。

基于主键索引的查询，只需要搜索主键索引的这棵树。

基于普通索引的查询，需要先搜索普通索引的树，找到主键的值，再搜索主键索引的树，查出对应的数据。这个过程称为回表。

基于非主键的查询，需要多查一棵树，因此应尽量使用主键进行查询。

为了保证整棵树的平衡，每次更新数据的时候，都需要更新树的节点。如果所在页已满，则需要申请一个新的数据页，然后挪动部分数据。这个过程称为 页的分裂 。

当相邻的两个页，由于中间的一些数据的删除，为了提高空间的利用率，会自动合并这两页。这个过程称为 页的合并 。

为了提高索引维护的效率，为表建一个自增的字段作为索引。每次添加数据，都是向树里追加数据，不涉及挪动其他数据，也不会触发叶子节点的分裂。如果用业务字段作为主键，则往往不能保证其插入时的有序性，增加了写数据的成本。

基于普通索引查询时，如果只需要查询主键值，则不用通过主键回表查询其他数据。这种情况下，普通索引已经覆盖了查询需求，称为 覆盖索引。

覆盖索引可以减少树的搜索次数，显著提高性能。

例：一个高频的查询，根据身份证号码查询姓名字段。则建立一个（身份证号、姓名）的联合索引，比只建立一个身份证号码的普通索引，执行查询会更高效，可以覆盖索引，避免回表。
但维护索引是需要代价的，因此在建立冗余索引来支持覆盖索引时，需要权衡利弊。

在使用联合索引时，索引树中的项，是按照索引定义的字段值，从左到右的顺序排序的。根据这个原则，查询时，不需要使用全部索引定义的字段，即可按定义的字段顺序，从左向右依次搜索。

例：有一个联合索引的字段定义为（姓名，年龄）：

以下查询皆可命中索引：

where 姓名 like '张%';
where 姓名 like '张%' and 年龄 = 10;
where 姓名 like '张%' and 年龄 = 10 and 其他字段的条件; ## 姓名和年龄可以命中索引，其他字段无法命中。

以下查询无法命中索引：

where 姓名 like '%张';
where 年龄 = 10;
where 其他字段;

唯一索引的更新无法使用change buffer，因此如果更新的数据没有在内存中，需要从硬盘读入所在数据的页，增加了IO时间。
因此对于写多读少的表，使用普通索引配合change buffer，可以显著的提升性能。

如果更新操作后，马上伴随着查询，会直接merge change buffer，这种情况下，应该关闭change buffer。