索引和数据都是存在磁盘里的，而每次读数据其实是读某个“磁块”，也可以简单的理解为“分页”，一个“磁块”内包含有很多数据，读取一次磁盘就是一次IO操作
sql执行过程
InnoDB索引结构/方法
1.hash
特点：key-value形式的索引结构
优点：速度快、时间复杂度底 O(1)
缺点：不适合范围查询，不满足一些的业务需求
2.二叉树
特点：左子树小于根节点，右子树大于根节点
优点：适合范围查询、时间复杂度 O(log2n)，取决于树的高度
缺点：在一定情况下，会退化成链表结构
退化：
3.二叉平衡树
特点：相较于二叉树，增加了自平衡的效果，左右子树高度相差最大不超过1
优点：避免了二叉树退化成链表的情况
缺点：如果数据量多，插入数据的时候平衡树也是一个很耗时的操作，而且树的高度也不会很低，每查一个节点就是一次IO
4.B树
特点：相当于多叉树，保留了右>左
优点：空间利用率大大提高(假若，p1、p2为指针占4byte，key为bigint占8byte，一个节点的大小很明显是有限的，但是从磁盘读取一页的大小是16K,所以二叉树的空间利用率相较于多叉树是很低的)
缺点
缺点：做范围查询效率较低
5.B+树
特点：相较于B树，它的数据都存在了子节点，而且子节点之间做成了双向链表,左边<key<=右边
优点：改进了B+树范围查询效率差的不足，子节点之间的双向指针减少了范围查询带来的磁盘IO
6.B树和B+树的对比
B树的索引项分布在整棵树，B+树的最底层叶子结点包含所有的索引项，所以如果要查找上图中key为17的数据。对于B树来说，查找到磁盘块2就可以返回数据了，对于B+树则需要找到磁盘块6中。
下面详细说一下，如果要查询值为15(等值查询)的数据，B+树的查询路径
第一次磁盘IO，将磁盘块1加载到内存中。在内存中从头遍历比较，发现15<28,磁盘根据p1寻址到磁盘块2
第二次磁盘IO，将磁盘块2加载到内存中。在内存中从头遍历比较，发现10<15<17,磁盘根据p2寻址到磁盘块5
第三次磁盘IO，将磁盘块5加载到内存中。在内存中从头遍历比较，发现15=15,取出data，如果data存储的是行记录，则取出data，查询结束。如果存储的是磁盘地址，说明不是最后节点，里面存储的还是磁盘地址，需要继续向下遍历
如果是查28的话
第一次磁盘IO，将磁盘块1加载到内存中。在内存中从头遍历比较，发现28=28,磁盘根据p2寻址到磁盘块3(如果是B树，在这一步已经返回结果了)
第二次磁盘IO，将磁盘块3加载到内存中。在内存中从头遍历比较，发现28<36,磁盘根据p1寻址到磁盘块7
第三次磁盘IO，将磁盘块7加载到内存中。在内存中从头遍历比较，发现28=28,取出data，如果data存储的是行记录，则取出data，查询结束。如果存储的是磁盘地址，说明不是最后节点，里面存储的还是磁盘地址，需要继续向下遍历
对于等值查询，只有一个B树存在中间返回的情况的区别。但是对于范围查询的话，B+树就比B树的性能好太多了，因为B+树是双向链表，叶子结点是有序的。所以mysql索引都是B+树。
索引的使用
组合索引
哪些字段创建：我们可以把常用的字段设置成组合索引
怎么创建：区分度高的字段可以放在最左边
为什么要创建：如果创建了一个{id,name,code}的组合索引，相当于创建了{id},{id,name},{id,name,code}三种索引，节约了磁盘空间，减少了插入数据的维护成本
之后怎么使用：注意最左匹配原则，按顺序来，因为组合索引查找的时候就是按序来的。也就是说索引创建是{id,name,code}，使用必须也是这个顺序，不按顺序的话就不会走索引
最左前缀原则：
顾名思义是最左优先，以最左边的为起点任何连续的索引都能匹配上，
注：如果第一个字段是范围查询需要单独建一个索引
注：在创建联合索引时，要根据业务需求，where子句中使用最频繁的一列放在最左边。这样的话扩展性较好，比如 userid 经常需要作为查询条件，而 mobile 不常常用，则需要把 userid 放在联合索引的第一位置，即最左边
————————————————
版权声明：本文为CSDN博主「深寒色的猫丶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Abysscarry/article/details/80792876
覆盖索引
哪怕使用了组合索引，仍然少不了找到主键再去回表，还是要遍历两颗索引树。
仍然以id,code,name为例，这种组合不光经常出现在where、order by中，而且经常出现在select后面，所以对于以下例子，我们可以建一个{animal_type,sex,animal_species}索引，这样在遍历组合索引树的时候，我们所需要的数据也都正好是索引的key，不需要再去遍历主键索引树了。
这种叫做覆盖索引，减少回表操作
// 查询动物类别、性别、种类
select animal_type,sex,animal_species from animal where animal_type = '哺乳动物' and sex= '雄性' and animal_species ='虎类';
1
2
in索引
当表中数据量小，而且in中的数据包含了大部分数据时，是不会走索引的，因为此时全表扫描和索引的效率差不多
当表中数据量大的话，是会走索引的。
————————————————
带你看懂MySQL执行计划
浅入浅出MySQL 和 InnoDB
mysql中key 、primary key 、unique key 与index区别
深入浅出数据库索引原理
MySQL数据库索引，索引的原理，创建索引实战，索引的增删改查
多个单列索引和联合索引的区别详解
从一条查询sql执行过程了解mysql索引
mysql BTree和B+Tree详解
为什么索引可以让查询变快，你有思考过吗？
