一、基本概念：
索引：索引是帮助MySQL高效获取数据的有序的数据结构，在数据之外，数据库系统害维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。
优点：索引可以提高数据检索效率 降低数据库的io成本，通过索引对数据进行排序，降低数据排序成本，降低CPU的消耗。
缺点：索引列会占用空间，索引大大提高了查询效率但是也降低了更更新表的速度，如对表进行INSERT,UPDATE,DELETE时，效率降低。
二、索引结构
MySQL的索引是在存储引擎层实现，不同的存储引擎会有不同的索引结构，主要包含以下几种：
B+Tree索引：最常见的索引类型，大部分引擎都支持B+Tree索引
Hash索引：底层的数据结构使用哈希表实现的，只支持等值匹配，不支持范围查询
R-Tree（空间索引）：空间索引是MylSAM引擎的一个特殊引擎类型，主要用于地理空间类型数据
Full-text（全文索引）：通过建立倒排索引，快速匹配文档
本文我们主要探讨B+Tree索引和Hash索引
1.B+树的索引结构
在探讨B+Tree索引之前 我们先来简单看一下B-Tree的结构
B-Tree树（多路平衡查找树）
以一颗最大度数为5阶的为例（每个节点最多存储4个key,5个指针）如图：
我们可以看到B树的每个节点下面都有数据
B-Tree树的演变过程：
如图，假如现在有五阶的B树，现在里面有四条数据
如果我再加入一条数据 1200 那么B树就会变成如下所示：
我们再依次加入 1234，1500 会变成如下：
此时我们再插入 1000 B数变成如下：
再添加多条数据
由此可见，B树是中间数向上分裂，并且数据是挂在每个ID下面
这就是B树的基本结构
下面我们再来看一下B+树的结构
我们以一颗最大度数为4的的B+树为例，如下图：
我们可以看到B+树上面的分叶节点是没有数据的，数据都是挂在最下面的叶子节点，并且在叶子节点中形成了一个单向链表
下面我们看一下B+树的演变过程：
如图，假如现在有五阶的B+树，现在里面有四条数据：
如果我再加入一条数据 890 那么B树就会变成如下所示：
此时我们可以看到B+树也是向上分裂，但向上分裂的同时数据还保留在叶子节点
我们再依次加入 1234，2345 会变成如下：
B+树相对于B树的区别：B+树 叶子节点会形成单项链表，非叶子节点只是起到索引的作用
在MySQL索引中的B+树对上面所展示的B+树的基础上 增加了一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+树，提高了区间访问的性能。
最终如图所示：
2.Hash索引结构
Hash索引就是采用Hash算法将键值换算成新的Hash值，映射到对应的槽位上，然后存储在Hash表中
如图所示：
如果数据量过大，通过Hash算法 算出的多个结果都指向同一个存储位置，那么会产生哈希冲突，我们可以通过链表来解决，如图：
Hash索引的特点，查询效率高，无法按照范围查询。
在mysql中，支持Hash索引的是Memory引擎，而innoDB中具有自适应hash功能，hash索引是存储引擎根据B+Tree索引在指定条件下自动构建的。
为什么mysql会使用B+树索引结构：
1.相对于二叉树，层级更少，搜索效率更高
2.相对于B树，无论是叶子节点还是非叶子节点，都会保存数据，这样导致一页中存储的键值减少，指针跟着减少，同样保存大量数据，只能增加树的高度，导致性能降低
3.相对于Hash，虽然Hash查询效率通常比B+树高，但是B+树通用性更强，hash只适合做等值查询
