date: 2019-05-25 16:53:22
常见索引模型
哈希表
- 插入很快，只需要在对应位置插入值即可 O(1)
- 等值查询也很快O(1)
- 区间查询只能全表扫描 O(N) ， 因为索引是无序的
哈希表适合无需区间查询的场景。
有序数组
- 等值查询和范围查询都很快
- 插入操作需要后移所有元素，消耗很大
有序数组索引适合静态存储引擎，如2017年某个城市的人口数据这类不会改动的数据。
排序树
- crud都有O(logN)的速度
- 为了尽量减少随机访问，增加数的叉数，降低树的高度；所以可以有二叉排序树，也可以有多叉排序树
InnoDB的索引模型
InnoDB使用了B+树索引模型
主键索引和非主键索引
主键索引的叶子节点存的是整行数据
非主键索引的叶子节点内容是主键的值
普通索引查询方式，则需要先搜索非主键索引树，得到主键的值，再到主键索引树搜索一次，这个过程称为回表。也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。
索引维护
三种情况
- 索引树叶子节点右侧追加，直接插入即可
- 插入叶子节点间，需逻辑上挪动后面的数据
- 数据页已满，需要申请新的数据页，然后挪部分数据过去，这个过程成为页分裂；这种情况下不仅影响性能，还会降低数据页的利用率
问题1：自增主键的意义？
尽量保证每次操作都是第一种情况，即有序插入，追加节点
问题2：如果有身份证号这种业务上能保证一致的列，能否直接设置为主键？
如果这个表中除了主键还有其他索引，那么不建议，因为这会导致其他非主键索引中存储的值会变长。
如果只有一个唯一索引，那就可以放心大胆的设置它为主键了，这样可以避免非主键索引的回表操作；这里描述的场景就是典型的kv场景。
覆盖索引
表T的结构如下
| id(主键) | k(索引) | s |
|---|---|---|
| 100 | 1 | aa |
| 200 | 2 | bb |
| 300 | 3 | cc |
| 500 | 5 | ee |
| 600 | 6 | ff |
| 700 | 7 | gg |
当我们执行select * from T where k between 3 and 5时，它的执行流程如下：
- 在k索引树上找到k=3的记录，取得 ID = 300；
- 再到ID索引树查到ID=300对应的R3；
- 在k索引树取下一个值k=5，取得ID=500；
- 再回到ID索引树查到ID=500对应的R4；
- 在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;
