索引，是数据库内资源定位的一种机制。正如你去一个学校找人，如果你只知道这个人的名字，可能是需要一间教室一间教室的去找。但是如果你还知道他在哪个年级哪个班，直接就找到了。
索引分类
按数据结构
Hash 索引
上图示，是 HashMap 的基本原理（JAVA 8之前），Hash Index 的原理在本质上是类似的，这里不做过多描述。需要注意的是，Hash Index(或者说哈希索引) 在 MEMEROY 存储引擎中是支持的。InnoDB 存储引擎中支持自适应哈希索引，用户仅能开启该特性，不能进行人工干预。
Hash 索引最主要的特点就是查询速度很快（时间复杂度为 O(1)），但是查询仅限于使用 =或<=> 操作符，无法使用 > 这样的操作符进行范围查询，也无法是哟能够 ORDER BY 这样的操作符进行排序。其所有 key 需要被加载到内中才能使用。
B+ 索引
B+ 索引，是 InnoDB 存储引擎中常见的搜索引擎。建立在 B+ 树和磁盘本身特性（IO查找）的基础上，提升查找速度。
如上图示（图片来源）。通过 B+ 树，快速定位到索引所定位的page，然后将该 page 加载到内存中，找到该值。
这里有几点需要注意：
- 在 InnoDB 中，数据按页加载到内存中，每一页 16KB。
- 为什么 B+ 树，而不是其它树。B+ 树很低，可以有效降低磁盘访问的平均次数。假设，以一个整型作为索引，另外每个索引中，还跟着 6B 的指向其它子树的指针，因此一个节点中，应可以存储索引个数（16KB/14B）1170。高度为4的时候，就可以存储 1170 的三次方（16亿）个索引。
- B+ 树中，根据叶子节点数据部分是主键索引还是具体数据块地址，可以分为聚集索引和非聚集索引（辅助索引或者二级索引）。
- 每张表中，仅有一个聚集索引，仅有一个主索引。应尽量使用主索引（加速查询查询速度），并尽量缩减主索引大小（扩大索引使用范围）。使用二级索引时，会引发回表。
- 分页，就会涉及页分裂和页合并的过程，这是影响索引速度的一个因素。当相邻两个页利用效率较低时，可能会触发页合并；如果页中已满，插入时就需要重新增加页，这也会涉及到数据的迁移。自增主键时，数据在页中不断追加。
另外补充两张图。
上图图片来源
按字段特性
主键索引
或者说聚集索引，唯一切不可重复的主键索引。
在 MySQL 中，如果没有设置主键，则会判断是否有符合条件的列作为索引（非空整型唯一索引）；如果没有，则会自动创建一个 6 字节的主键（该主键查不到）。
普通索引
非聚集索引，或者说二级索引，辅助索引。由用户创建的普通索引，在搜索时，会发生回表，最终通过主键索引查找数据。
前缀索引
索引过长，使得业内能够存储的记录表少，也容易导致页分裂，页数变多，可能导致树的高度增加。前缀索引，即是设置某列的前 n 的字节为索引。
按字段个数
单列索引
顾名思义，单列索引就是以某一列为索引。
联合索引
联合索引，或者说复合索引，使用多列构建索引。
联合索引在查找方式上，采用最左前缀匹配原则。在这种方式下，首先，会根据最左边列，构建索引树（B+ 树），只是在叶子节点上，保存的是所有参与索引的列以及对应的主键值.
我们知道，对于非聚集索引，在查询时，通常会进行回表查询。而对于联合索引，在回表查询之前，查询结果中包含了参与索引的所有列值，那么，如果你想查询的内容都包含在这写列值中，就没有必要进行回表查询，这，就是覆盖索引。
****索引条件下推****（Index Condition Pushdown (ICP) ），是对联合索引过程的另一种优化。这种方式下，将有效降低Server层和 Engine 层的交互次数，从而降低运行时间。
该功能是 MySQL 5.6 新增的优化功能，5.6后默认打开，当然，有也可以通过改变环境变量的方式关闭这个优化器开关：
1 | SET optimizer_switch = 'index_condition_pushdown=off'; |
当 ICP 关闭时，Server 层通过 Engine API 获取数据，再进行 Where 语句的判断；ICP 打开后，
在利用索引扫描的过程中，如果发现 where_cond 中含有这个 index 相关的条件，则将此条件记录在 handler 接口中，在索引扫描的过程中，只有满足索引与handler接口的条件时，才会返回到 server 层做进一步的处理，在前缀索引区分度不够，其它字段区分度高的情况下可以有效的减少 server & engine之间的开销，提升查询性能。—引文来自
参考链接
An Introduction to MySQL Indexes
8.3.9 Comparison of B-Tree and Hash Indexes
MySQL索引原理及慢查询优化
为什么磁盘存储引擎用 b+树来作为索引结构？
浅谈聚簇索引和非聚簇索引的区别
一文搞定联合索引
联合索引在B+树上的结构
漫画：什么是B-树？
漫画：什么是B+树？
MySQL 前缀索引
MySQL · 特性分析 · Index Condition Pushdown (ICP)