索引的三种实现模型
1）哈希表，是一种以key-value存储数据的结构，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这方法是，拉出一个链表。
优点：增加新的 User 时速度会很快，只需要往后追加。
缺点：因为不是有序的，哈希索引做区间查询的速度是很慢的。
2）有序数组，按一个顺序递增存储，适合静态存储数据
优点：支持范围查询
缺点：新增记录的时候，需要挪动后面所有的记录，成本比较大
3）二叉搜索树，所有的左子树都小于父节点，右子树都大于父节点，为了维护查询效率，需要保持树的平衡，就是平衡二叉树。为了尽量减少访问数据节点的次数，会需要使用N叉树。以innodb整数索引为例,N差不多是1200，树高是4的话，可以存1200的3次方，相当于17亿。树根和第一层一般是放在内存中，那么访问一个数据只需要去磁盘读2次。
Innodb的索引模型
在innodb中，表都是根据主键顺序以索引形式存放的，每一个索引在innodb中就是一棵B+树。
根据叶子节点的内容，索引分为主键索引和非主键索引。
1）主键索引，叶子节点存的是主键对应的整行数据，主键索引也被称为聚簇索引；如果以主键查询，则只需要搜索主键这棵B+树
2）非主键索引，叶子节点存的是主键的值（索引+主键），非主键索引也被称为二级索引；如果以非主键查询，则先搜索这个索引的B+树找到主键，再搜索主键B+树获取数据。也就是说非主键索引则需要多搜索一次B+树。
索引的维护
为了维护索引的有序性，插入新值的时候需要挪动后面的数据。
1）如果叶子节点的页还没有满，则把后面的数据往后挪，插入新增的数据
2）如果叶子节点的页已经满了，则需要申请新页，把原本页的内容分一半到新的页，称为页分裂，空间利用率会下降
3）如果删除数据，页的利用率很低，则会发生页合并，就是页分裂的逆向过程。
自增主键的使用
1）自增主键使用的时候，如果插入数据，都是追加数据，不会发生页分裂；如果使用业务字段，一般不能保证有序插入，则写数据的成本相对偏高
2）自增主键一般可以定义bigint也就是8个字节，但是用业务字段，则可能需要20个字节以上。主键索引的长度越小，则普通索引的叶子节点越小，索引占用的空间越小
所以从性能和存储的角度，自增主键的使用往往是更优的选择。
特殊情况：
只有一个索引，且是唯一索引，那么就可以作为主键；这样只用搜索主键这棵树，避免搜索两棵树。
覆盖索引
回表：在非主键索引上搜索，又回到主键索引上查找需要的数据，称为回表。
如果索引已经包含了需要select where的内容，则不需要回表，则称为覆盖索引，这是常用的一种优化查询性能的办法。
可以将一些非常高频的查询字段，作为联合索引，比如用户信息表，有ID 姓名和其他字段，ID是主键，如果经常有通过ID查询姓名的需求，则可以通过建立ID和姓名的联合索引。增加了一个索引的空间，换来了搜索的高效。
覆盖索引不能只覆盖要查询的列，同时必须将WHERE后面的查询条件的列都覆盖
最左前缀原则
B+树种，不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。
1）如果可以通过调整索引顺序，减少一个索引。比如（a，b）索引（a），那么只要创建（a ，b）这个索引就行了。
2）如果不满足最左前缀，则需要考虑空间。挑选相对较短的字段做索引。
索引下推
在最左前缀的规则下，MYSQL 5.6之前只能根据找到的主键一个一个回表，而5.7之后引入索引下推优化，在索引遍历的过程中，对索引包含的字段预先进行判断，减少回表次数。
其他
1.select * from T where k in(1,2,3,4,5)，需要树搜索5次2.select * from T where k between 1 and 5，需要树搜索1次
