1,什么是索引
索引是一个排好序的列表，在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址。在数据库十分庞大的时候，索引可以大大加快查询的速度，这是因为使用索引后可以不用扫描全表来定位某行的数据，而是先通过索引表找到该行数据对应的物理地址然后访问相应的数据。
在 MySQL 中，索引是在存储引擎层而不是服务器层实现的。这意味着我们所讨论的索引准确来说是 InnoDB 引擎或 MyISAM 引擎或其它存储引擎所实现的。
2，索引的分类
1）从存储结构划分
btree索引（B+tree,B-tree）
哈希索引
full-index全文索引
Rtree
2）从应用层次上划分
普通索引：一个索引只包含单列
ALTER TABLE table_name ADD INDEX index_name (column );复制
主键索: 引即主索引，根据主键建立索引，不允许重复，不允许空值；
主键：数据库表中一列或列组合（字段）的值，可唯一标识表中的每一行。
加速查询 + 列值唯一（不可以有null）+ 表中只有一个
ALTER TABLE table_name ADD PRIMARY KEY pk_index(col);复制
唯一索引：索引列的值必须唯一，但允许有空值
用来建立索引的列的值必须是唯一的，允许空值。唯一索引不允许表中任何两行具有相同的索引值。比方说，在 employee 表中职员的姓 name 上创建了唯一索引，那么就表示任何两个员工都不能同姓。
ALTER TABLE table_name ADD UNIQUE index_name(col);复制
复合索引：一个索引包含多个列
用多个列组合构建的索引，这多个列中的值不允许有空值。
多列值组成一个索引，专门用于组合搜索，其效率大于索引合并。
ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3');复制
在对多列组合建立索引时，会遵循「最左前缀」原则。
最左前缀原则：顾名思义，就是最左优先，上例中我们创建了 (col1, col2, col3) 多列索引,相当于创建了 (col1) 单列索引，(col1, col2) 组合索引以及 (col1, col2, col3) 组合索引。
3）从表记录的排列顺序和索引的排列是否一致划分
a，聚集索引：表记录的排列顺序和索引的排列顺序一致
b，非聚集索引：表记录的排列顺序和索引的排列顺序不一致
3，聚集索引与非聚集索引
1）简括
聚集索引：以主键创建的索引
非聚集索引：以非主键创建的索引
2）详解
聚集索引
聚集索引表记录的排列顺序和索引的排列顺序一致，所以查询效率快，因为只要找到第一个索引值记录，其余的连续性的记录在物理表中也会连续存放，一起就可以查到
缺点
新增慢，为了保证表中记录的物理顺序和索引顺序一致，在记录插入的时候，会对数据页重新排序
非聚集索引
索引的逻辑顺序与磁盘上行的物理存储顺序不同，非聚集索引在叶子节点存储的是主键和索引列，当我们使用非聚集索引查询数据时，需要拿到叶子上的主键，再去表中查询主键的数据，这就是回表
3）聚集索引与非聚集索引的区别
•聚集索引在叶子节点存储的是表中的数据
•非聚集索引在叶子节点存储的是主键和索引列
4，索引底层的数据结构
Mysql innodb的存储结构
Innodb中将文件存储分为了四个级别：Pages, Extents, Segments, and Tablespaces
其中innodb引擎最基本的存储结构是页（记录都存在页里面）
每个数据页可以组成一个双向链表
而每个数据页中的记录又可以组成一个单向链表
•每个数据页都会为存储在它里边的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录
•以其他列（非主键）作为搜索条件：只能从最小记录开始依次遍历单链表中的每条记录
参考：
MySQL · 引擎特性 · InnoDB 数据页解析
http://mysql.taobao.org/monthly/2018/04/03/
MySQL Innodb 数据页结构分析
https://www.cnblogs.com/bdsir/p/8745553.html
对于没有进行优化的sql语句，默认的操作：
1，定位到记录所在的页
•需要遍历双向链表，找到所在的页
2，从所在的页内中查找相应记录
•由于不是根据主键查询，只能遍历所在页的单链表
哈希索引
类似使用哈希表来实现快速查找，与hashmap一样，value = get(key) O(1)时间复杂度一步到位
定义：
哈希索引采用一定的哈希算法。只需要一次哈希算法即可立刻定位到相应的位置，速度非常快。本质就是把键值换算成新的哈希值，根据哈希值来定位
局限性：
哈希索引没有办法利用索引完成排序
不能进行多字段查询
在有大量重复键值的情况下，哈希索引的效率也是极低的
不支持范围查询
在 MySQL 中，只有 Memory 存储引擎显式的支持哈希索引，而innodb是隐式支持哈希索引的。
b树
BTree 实际上是一颗多叉平衡搜索树。从名字可以看出，BTree 首先是一颗多叉搜索树，这意味着它是具有顺序的；其次 BTree 还是平衡的，这意味着它的左右子树高度差小于等于1。
b树的特点：
•关键字分布在整颗树的所有节点任何一个关键字出现且只出现在一个节点中
•搜索有可能在非叶子节点结束
•其搜索性能等价于在关键字全集内做一次二分查找
BTree 相较于其它的二叉树结构，对磁盘的 I/O 次数已经非常少了。但是在实际的数据库应用中仍有些问题无法解决。
一是无法定位到数据行。通过 BTree 可以根据主键的排序定位出主键的位置，但是由于数据表的记录有多个字段，仅仅定位到主键是不够，还需要定位到数据行。虽然这个问题可以通过在 BTree 的节点中存储数据行或者增加定位的字段，但是这种方式会使得 BTree 的深度大幅度提高，从而也导致 I/O 次数的提高。
二是无法处理范围查询。在实际的应用中，数据库范围查询的频率非常高，而 BTree 只能定位到一个索引位置。虽然可以通过先后查询范围的左右界获得，但是这样的操作实际上无法很好的利用磁盘预读的局部性原理，先后查询可能会造成通过预读取的物理地址离散，使得 I/O 的效率并不高。
三是当数据量一大时，BTree的高度依旧会变得很高，搜索效率还是会大幅度的下降。
b+树
B+Tree 一看就是在 BTree 的基础上做了改进，是一种带有顺序索引的 B+Tree，与最基本的 B+Tree 的区别就在于叶子节点是否通过指针相连。一般数据库中常用的结构都是这种带有顺序索引的 B+Tree。
b+树基本特点
•非叶子节点的子树指针与关键字个数相同
•非叶子节点的子树指针P[i]，指向关键字属于[k[i],k[i+1]]的子树（区间是前闭后开）
•为所有叶子节点增加一个链指针
•所有关键字都在叶子节点出现
b+树的特性
所有的关键字都出现在叶子节点的链表中，且链表中的关键字是有序的
搜索只在叶子节点命中
非叶子节点相当于是叶子节点的索引层，叶子节点是存储关键字数据的数据层
相对 B 树，B+树做索引的优势
•B+树的磁盘读写代价更低。B+树的内部没有指向关键字具体信息的指针，所以其内部节点相对B树更小，如果把所有关键字存放在同一块盘中，那么盘中所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相应的，IO读写次数就降低了。
•树的查询效率更加稳定。B+树所有数据都存在于叶子节点，所有关键字查询的路径长度相同，每次数据的查询效率相当。而B树可能在非叶子节点就停止查找了，所以查询效率不够稳定。
•B+树只需要去遍历叶子节点就可以实现整棵树的遍历
5，MyISAM引擎的索引
主键索引
MyISAM的索引文件（.MYI）和数据文件（.MYD）文件是分离的，索引文件仅保存记录所在页的指针（物理位置），通过这些指针来读取页，进而读取被索引的行
树中的叶子节点保存的是对应行的物理位置，通过该值，存储引擎能顺利地进行回表查询，得到一行完整记录
同时，每个叶子也保存了指向下一个叶子节点的指针，方便叶子节点的范围遍历
辅助索引
在 MyISAM 中，主键索引和辅助索引在结构上没有任何区别，==只是主键索引要求key 是唯一的，而辅助索引的 key 可以重复==。
6，Innodb存储引擎索引
主键索引
InnoDB 主键索引中既存储了主健值，又存储了行数据。
辅助索引
对于辅助索引，InnoDB 采用的方式是在叶子节点中保存主键值，通过这个主键值来回表查询到一条完整记录，因此 按辅助索引检索其实进行了二次查询，效率是没有主键索引高的。
7，索引的三个优点与三大缺点
优点
索引大大减少了服务器需要扫描的数据量
索引可以帮助服务器避免排序和临时表索引可以将随机 I/O 变成顺序 I/O
索引本身以表的形式存储，因此会占用额外的存储空间；
缺点
索引表的创建和维护需要时间成本，这个成本随着数据量增大而增大；
构建索引会降低数据的修改操作（删除，添加，修改）的效率，因为在修改数据表的同时还需要修改索引表；
