date: 2019-05-25 16:53:22

常见索引模型

哈希表

• 插入很快，只需要在对应位置插入值即可 O(1)
• 等值查询也很快O(1)
• 区间查询只能全表扫描 O(N) ， 因为索引是无序的

哈希表适合无需区间查询的场景。

有序数组

• 等值查询和范围查询都很快
• 插入操作需要后移所有元素，消耗很大

有序数组索引适合静态存储引擎，如2017年某个城市的人口数据这类不会改动的数据。

排序树

• crud都有O(logN)的速度
• 为了尽量减少随机访问，增加数的叉数，降低树的高度；所以可以有二叉排序树，也可以有多叉排序树

InnoDB的索引模型

InnoDB使用了B+树索引模型

主键索引和非主键索引

• 主键索引的叶子节点存的是整行数据

• 非主键索引的叶子节点内容是主键的值

普通索引查询方式，则需要先搜索非主键索引树，得到主键的值，再到主键索引树搜索一次，这个过程称为回表。也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

索引维护

三种情况

• 索引树叶子节点右侧追加，直接插入即可
• 插入叶子节点间，需逻辑上挪动后面的数据
• 数据页已满，需要申请新的数据页，然后挪部分数据过去，这个过程成为页分裂；这种情况下不仅影响性能，还会降低数据页的利用率

问题1：自增主键的意义？

尽量保证每次操作都是第一种情况，即有序插入，追加节点

问题2：如果有身份证号这种业务上能保证一致的列，能否直接设置为主键？

如果这个表中除了主键还有其他索引，那么不建议，因为这会导致其他非主键索引中存储的值会变长。

如果只有一个唯一索引，那就可以放心大胆的设置它为主键了，这样可以避免非主键索引的回表操作；这里描述的场景就是典型的kv场景。

覆盖索引

表T的结构如下

当我们执行select * from T where k between 3 and 5时，它的执行流程如下：

1. 在k索引树上找到k=3的记录，取得 ID = 300；
2. 再到ID索引树查到ID=300对应的R3；
3. 在k索引树取下一个值k=5，取得ID=500；
4. 再回到ID索引树查到ID=500对应的R4；
5. 在k索引树取下一个值k=6，不满足条件，循环结束。

在这个过程中，回到主键索引树搜索的过程，我们称为回表。可以看到，这个查询过程读了k索引树的3条记录（步骤1、3和5），回表了两次（步骤2和4）。

问题：如何避免回表过程？

执行语句select ID from T where k between 3 and 5，因为要查询的ID的值已经在k的索引树上了，所以不再需要回表。

在这个查询里面，索引k已经“覆盖了”我们的查询需求，我们称为覆盖索引

Tips：利用覆盖索引优化性能

市民信息表中，有身份证号和姓名两个字段，如果有高频需求是根据身份证号查询姓名，那我们可以考虑给身份证号和姓名建立联合索引，以便利用覆盖索引提高查询性能。

最左前缀

基本概念

当已经有了(a,b)这个联合索引后，一般就不需要单独在a上建立索引了

如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的

考虑空间

如果既有联合查询，又有基于a、b各自的查询呢？查询条件里面只有b的语句，是无法使用(a,b)这个联合索引的，这时候你不得不维护另外一个索引，也就是说你需要同时维护(a,b)、(b) 这两个索引。

这时候，我们要考虑的原则就是空间了。比如上面这个市民表的情况，name字段是比age字段大的 ，那我就建议你创建一个（name,age)的联合索引和一个(age)的单字段索引。

索引下推

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

举个栗子

假设现在有联合索引（name, age），执行select * from tuser where name like '张%' and age=10 and ismale=1;

无索引下推执行流程

有索引下推执行流程