、索引是帮助mysql高效获取数据的数据结构
2、索引存储在文件系统中
3、索引的文件存储形式与存储引擎有关
二叉树链接:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
mysql解释说明:https://www.cnblogs.com/yycc/p/7338894.html

二叉树,二分查找
AVL树:通过左旋右旋来维持平衡
红黑树(二叉平衡树)
B+树:degree(阶),指一个元素最多含有degree-1个元素
注意:在B+树上有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点,而且所有叶子节点(即数据节点)之间是一种链式环结构,因此可以对B+Tree进行两种查找运算;一种是对于主键的范围查找和分页查询,另一种是从根节点开始,进行随机查找

聚簇索引:数据和索引是绑定在一起的,比如innoDB引擎
非聚簇索引:数据和索引是分开的,比如MyISAM引擎
mysql InnoDB B+Tree 叶子节点直接放置数据
1、InnoDB是通过B+Tree 结构对主键创建索引,然后叶子节点中存储记录,如果没有主键,那么会选择唯一键,如果没有唯一键,那么会生成一个6字节的row_id来作为主键
2、如果创建索引的键是其他字段,那么在叶子节点中存储的是该记录的主键,然后再通过主键索引找到对应的记录,叫做回表,而不需要回表的叫做索引覆盖(extra using index)

mysql MyISAM B+Tree 叶子节点放的是地址,根据地址再查找数据

id name age gender job
where name=? and age=?
给name和age添加一个索引 (name,age)
如果索引列包含的是多个列,那么就称之为联合索引(组合索引)

在包含多个列的查询过程中,会依靠先查第一列,再查第二列,叫做最左匹配

where name=? and age=?
where name=?
where age=? 不做组合索引
where age=? and name=?

索引下推(ICP) :index condition pushdown
(name,age)
不使用索引下推:先根据name列的值把所有的数据都拉取到server层,在server层对age做过滤
使用索引下推:根据name,age两个字段把满足要求的数据拉取到server层,取出对应的数据

如果没有索引下推优化(或称ICP优化),当进行索引查询时,首先根据索引来查找记录,然后再根据where条件来过滤记录;在支持ICP优化后,MySQL会在取出索引的同时,判断是否可以进行where条件过滤,也就是说提前执行where的部分过滤操作,在某些场景下,可以大大减少回表次数,从而提升整体性能。

MRR(multi-range read):多范围查询
回表:先根据普通索引查询到主键值,根据主键值去主键索引拉取需要的整行数据
根据name查询id之后,id是无序的,根据无序的一个列表去主键B+树上查询数据,随机查找
当返回无序的id之后,先将这些id进行排序,当排序完成之后在查询就不是随机的了