索引是一种数据结构，可以帮助mysql高效获取数据。索引存储在文件系统中，存储形式跟存储引擎相关。比如下面的innodb和myisam存储索引的形式就不同。
模型演示：
innoDB 和myisam存储引擎的数据存储文件形式如下 eg:
innodb是聚簇索引形式，他的数据和索引均存储在.idb文件中，而myisam存储的是非聚簇索引，他的数据和索引分开存储，分别存放在.MYD 和 .MYI文件中，当然这两个存储引擎表结构都存放在 .frm文件中，对innodb来讲，不是所有的索引都存放在.idb文件中，你比如说二级索引，他是存储于其他的文件中。
一、hash索引
hash索引：存储引擎会给每行的索引列计算一个hash码，hash索引会把hash码保存到索引中，索引表会保存指向每行的指针。
存储为kv对形式，底层 数组+链表
缺点：
1 hash冲突，会导致某个链表特别长，可以采取使用扰动函数（做高位运算时，将高位右移，做运算后结合亦或），让链表尽量分散均匀些。
2 存储hashmap的时候，要把整体的数据都放到内存。最大容量1<<30 ，是比较占用内存的。
3 等值查询很快，但是工作中范围查询比较多，hash里面数据是无序存储的，所以范围查找的话，hash效率极低。
memory 默认为hash索引，
1 memory存储引擎主要作用于缓存，所以不担忧hash占内存；
2 设计比较公正的hash算法 ；
3 使用等值查询，即使是范围查询也没关系，因为是在内存操作。内存比磁盘的查询效率高。
二、二叉树，红黑树
二叉树，红黑树 他们每个节点里只放一个值，获取的数据量较多时，会导致树的深度过深，io次数变多，影响数据读取效率。
mysql innodb存储引擎，默认每次取16k数据，每个节点放一个值，要放很多，树的高度会变深，io量也会变大，性能变低。
磁盘io读取速度是固定的，想提高io效率，只能通过减少io量或者减少io次数
1） 减少io次数
2 ）减少io的大小(io量)
所以不提倡用全表扫描的形式查询数据，这样io量比较大。
1、二叉树左边节点小于根节点，右边节点大于根节点。如果出现递增或者递减，就容易变成一个链表了。
2、avl树：平衡树，左子树和右子树高度差不超过1，查询性能非常高，为了保持平衡，要不断做旋转
3、红黑树：最高子树不超过最低子树的两倍，根节点为黑色，每个路径里不能有两个连续的红色节点。不过他的插入和查询得到了一个平衡。
4、 b树：每个节点增加数据量，多叉，树的深度就不那么高了
而且选择b+树也有多叉的原因。
三、 b树，b+树
b-tree 和b+tree里每个节点放的是值的集合（degree:阶，单个节点放多个数据元素 如果degree=5 ,则最多一个节点放4个数据）
b树的每个叶子和节点存放的元素都有数据。
b+树只有最下面一层的叶子存放了数据，其他叶子节点只存放了指针和id，这样，相同节点大小的情况下，b+tree能存放的数据更多，io次数比b树少了好几个数量级
innodb每次读取一个磁盘块，该数据块大小16k，即每次获取4个叶子，磁盘预读长度为4，阶数为5
比如节点里每组指针和 id 存储 占用10字节 , 按mysql每次能获取16k大小的数据作为每个叶子节点的大小 去计算，这个b+树最多存储数据量为 1600*1600*1600=4096 000 000，
由此可知，索引越小越好，innodb获取数据的磁盘块16k,索引占用空间小的话，就能容纳更多的数据。
那么索引列特别长，又有实际需要在这个列上创建索引，那可以创建前缀索引。
innodb，myisam 存储引擎默认索引结构b+树 ， 而memory存储引擎默认hash索引。
总结：b+tree是b-tree的改造：
1 首先b+teee增加了顺序访问指针，每个叶子都存储了指向相邻叶子的指针，而且叶子间数据的存储是有序的；范围查找的时候，b-tree要从根部获取所有节点做范围查找，而b+tree只需要获取两个叶子节点，从底层叶子节点开始做范围查找，效率很高。
2 b-tree所有节点都保存了数据，导致叶子节点保存的指针数量变少，如果想保存更多的数据，只能增加树的高度，io次数也会变多。而b+tree中中间节点不保存数据，相同条件下，b+tree能存储更多的指针，那么树的高度也不会太高，io量少，查询效率大大提高
innodb和myisam的索引结构，默认都是b+tree形式，因为底层叶子是双向链表，所以查找数据的方式不止 从根节点向下随机查找这一种方式，还有一种方式就是从底层叶子节点开始对主键的范围查找和分页查找，至于选取哪种方式，这就是优化器的事情了。
之所以没选二叉树，红黑树，hash做默认索引存储结构，而是选择b+tree做默认索引存储结构小结如下：
红黑树 随着数据量的增加树的高度会变大，io代价大。
二叉树 树高度不均匀，不能自平衡，索引速度由数据决定（树的高度），io代价大。
hash 查询速度快，但是没有顺序，io复杂度高
综上，mysql 的索引默认使用b+tree索引，索引是基于存储引擎的，mysql默认5.5版本之后默认使用innodb存储引擎，他一个显著的特点是支持事务，mysql5.5版本之前默认存储引擎是myisam（默认索引是btree），当然innodb也支持hash索引，不过是自适应的，查询数据量比较大的时候，innodb存储引擎会在b+tree索引基础上增加自适应hash，大大提高查询速度。
首先查库慢的瓶颈主要是io量。
回表：非主键索列orderId 获取数据，先根据orderId的b+tree找到数据获取对应的主键，然后根据主键的b+tree获取数据，过程就是回表。一般二级索引(辅助索引) 会用到回表查询。
索引覆盖：不需要回表查询 eg:select id from tabName where orderId='asdfadsfdaf'
最左匹配原则：基于组合索引，eg: a,b创建了一个组合索引，要想使用这个索引，必须要有a,同时b可以有也可以没有，where b=bb and a=aa 也会使用该索引，因为优化器帮忙处理了（优化器有两种：CBO 基于成本的优化，效率更高； RBO基于规则的优化，数据库一般都默认选择CBO的优化 ），优化器会把b和a的位置调换。这个最左匹配原则指的就是创建联合索引的时候，想用这个索引，一定要把左边的字段值放到条件里进行查询。
索引下推: 还是组合索引 a,b , 直接在存储引擎层根据a,b获取数据（直接从磁盘筛选获取数据），不需要server层做任何的数据筛选。
没有索引下推的时候，首先通过存储引擎拉取数据（根据 a 做筛选）,然后到mysql server服务层（ 根据 b ）进行数据的筛选。
1索引下推是在磁盘上做数据筛选，因为数据是按顺序存储的，所以这方面的性能影响可以忽略，但是io量大大减少，从而提高性能
2 innodb存储引擎整体架构分两部分：内存架构，磁盘架构。
3谓词下推：关联做投影查询，两种形式：1先做关联，再做投影查询， 2 先做投影查询，再做关联查询，推荐方式2，高并发情况下io量少。
主键索引，唯一索引（他们关系到数据的组织形式）；普通索引，全文索引， 组合索引
ext
二级索引就是非主键索引的统称 ,主键索引 primary key