1.1、索引概述：
MySQL官方对索引的定义：索引（index）是帮助MySQL高效获取数据的数据结构（有效），在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据， 这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。简而言之：帮助MySQL高效的查询出数据的数据结构叫做索引。
一般来说，索引本身也很大，不可能全部都存储在内存中，因此索引一般都是以索引文件的形式存储在磁盘上。索引是数据库用来提高性能最好的方式。
1.2、索引优劣势
优势：
索引类似于书籍的目录，提高数据检索的效率，减少数据库IO的成本
通过索引列对数据进行排序，降低数据排序的成本，降低CPU的消耗
劣势：
实际上索引也是一张表，存储在磁盘上，该表保存了主键与索引字段，并指向实体类的记录。
虽然索引大大提高了查询的速度，但是降低了增删改的速度，对表进行update、insert、delete时，需要对索引文件进行更新
1.3、索引结构
索引是在MySQL的存储引擎中实现的，而不是服务层实现的。所以每种存储引擎的索引都是不一样的，也不是所有的存储引擎都支持所有的索引类型。MySQL目前提供了以下4种索引：
BTREE 索引 ： 最常见的索引类型，大部分索引都支持 B 树索引。
HASH 索引：只有Memory引擎支持 ， 使用场景简单 。
R-tree 索引（空间索引）：空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少，不做特别介绍。
Full-text （全文索引） ：全文索引也是MyISAM的一个特殊索引类型，主要用于全文索引，InnoDB从Mysql5.6版本开始支持全文索引。
MyISAM、InnoDB、Memory三种存储引擎对各种索引类型的支持
在平常，如果没有特殊的说明，都是使用B+树结构组织的索引。其中聚集索引、复合索引、前缀索引、唯一索引默认都是使用 B+tree 索引。
1.4、B-Tree索引
B树：
因为内存的易失性。一般情况下，我们都会选择将 user 表中的数据和索引存储在磁盘这种外围设备中。
但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。
另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。
如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。
如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。
为了解决平衡二叉树会出现多次磁盘IO的这个弊端，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的 B 树。
B 树（Balance Tree）即为平衡树的意思，下图即是一棵 B 树：
图中的每个节点称为页，页就是我们上面说的磁盘块，在 MySQL 中数据读取的基本单位都是页，所以我们这里叫做页更符合 MySQL 中索引的底层数据结构。
从上图可以看出，B 树相对于平衡二叉树，每个节点存储了更多的键值（key）和数据（data），并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的 B 树为 3 阶 B 树，高度也会很低。
基于这个特性，B 树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。
B树的查找：
步骤：
1、插入一个元素时，首先在B树中是否存在，如果不存在，即比较大小寻找插入位置，在叶子结点处结束，然后在叶子结点中插入该新的元素
2、如果叶子结点空间足够，这里需要向右移动该叶子结点中大于新插入关键字的元素，如果空间满了以致没有足够的空间去添加新的元素，则将该结点进行“分裂”，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中（当然，如果父结点空间满了，也同样需要“分裂”操作）
3、当结点中关键元素向右移动了，相关的指针也需要向右移。如果在根结点插入新元素，空间满了，则进行分裂操作，这样原来的根结点中的中间关键字元素向上移动到新的根结点中，因此导致树的高度增加一层
B+树：
根据上图我们来看下 B+ 树和 B 树有什么不同：
- n叉B+Tree最多含有n个key，而BTree最毒含有n-1个key。
- B+Tree的叶子节点保存所有的key信息，依key大小顺序排列。
- 所有的非叶子节点都可以看作是key的索引部分。
①B+ 树非叶子节点上是不存储数据的，仅存储键值，而 B 树节点中不仅存储键值，也会存储数据。
之所以这么做是因为在数据库中页的大小是固定的，InnoDB 中页的默认大小是 16KB。
如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快。
另外，B+ 树的阶数是等于键值的数量的，如果我们的 B+ 树一个节点可以存储 1000 个键值，那么 3 层 B+ 树可以存储 1000×1000×1000=10 亿个数据。
一般根节点是常驻内存的，所以一般我们查找 10 亿数据，只需要 2 次磁盘 IO。
②因为 B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。
那么 B+ 树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而 B 树因为数据分散在各个节点，要实现这一点是很不容易的。
有心的读者可能还发现上图 B+ 树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。
其实上面的 B 树我们也可以对各个节点加上链表。这些不是它们之前的区别，是因为在 MySQL 的 InnoDB 存储引擎中，索引就是这样存储的。
也就是说上图中的 B+ 树索引就是 InnoDB 中 B+ 树索引真正的实现方式，准确的说应该是聚集索引（聚集索引和非聚集索引下面会讲到）。
通过上图可以看到，在 InnoDB 中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。
MyISAM 中的 B+ 树索引实现与 InnoDB 中的略有不同。在 MyISAM 中，B+ 树索引的叶子节点并不存储数据，而是存储数据的文件地址。
1.5、hash索引
哈希索引基于哈希表实现。只有精确匹配索引所有列的査询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code),哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。
MySQL中，只有Memory引擎显式支持哈希索引。这也是Memory引擎表的默认索引类型，Memory引擎同时也支持B-Tree索引。值得一提的是，Memory引擎是支持非唯一哈希索引的，这在数据库世界里面是比较与众不同的。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。
因为索引只存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。
哈希索引包含以下缺点：
- 哈希索引只包含哈希值和行指针，而不存储数据值，所以无法通过索引来避免读取行。（当select只取索引值时）
- 哈希表中的哈希值是有序的，但导致索引值是无序的，所以无法用于排序
- 哈希索引不支持部分索引列匹配索引。因为哈希值是根据所有使用的索引列进行计算。所以当索引为(A,B)时，如果只使用A，索引无效。
- 哈希索引只支持等值查询。即 = 、 IN()、 <=>。不支持范围查询
- 当出现哈希冲突时，需要遍历对应链表的所有行指针，逐行比较。
- 如果哈希冲突很多时，一些索引维护操作的代价也会很高。例如当做对应的删除操作时，需要遍历对应链表的所有行指针，找到并删除对应行的引用。
因为这些限制，哈希索引只适用于某些特定的场合。而一旦适合哈希索引，则它带来的性能提升将非常显著。
Innodb引擎有一个特殊的功能叫“自适应哈希索引”。 当InnoDB注意到某些索引值被使用得非常频繁时，它会在内存中，基于B-Tree之上再创建一个哈希索引，这样就让B-Tree索引也具有哈希索引的一些优点，比如快速的哈希查找。这是一个完全自动的、内部行为，用户无法控制或配置，但是可以关闭。