从数据结构角度给MySQL中的索引分类
种类
以数据结构分类：
B-树索引（Balance Tree平衡多叉搜索树）：由于平衡二叉搜索树log2n的查询性能较低，所以B-树是M叉树，时间复杂度降为logMn，快了很多。
B+树索引（对比B树来记）：B+树 是 B树 的改进版。
- B+树 和 B树 的根本差距：就在于 B+树 仅在叶子节点存储数据，一改 B树 中每个节点既存索引又存数据的做法，因此 B+树 的实现相较 B树 会略有不同。（比如在B+树中 关键字数量=儿子数量M，并且关键字也会在子结点中存储，这样传递下去所有关键字都会在子结点中出现，叶子节点构成一个有序列表；B树 每个节点中 关键字数量=儿子数量M-1，节点中出现过的关键字在子结点中不会再出现）
- B+树的优点：B+树这种数据在叶节点中以有序链表相连的结构大大增加了范围查询的性能；根据局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用，B+树的结构非常有利于基于局部性原理的预读，IO一次会把一个数据页 读到内存（InnoDB 中的数据页16KB，磁盘页4KB，这得区分开来），这也大大提升了查询性能。
哈希索引：基于哈希表实现，不像B+树索引还能使用不完全的字段遵从最左前缀原则来使用索引，哈希表必须要精确匹配所有的列才能查询，引擎会通过 所有的索引列 计算一个哈希码，哈希表的键就是哈希码，对应的值就是指向数据行的指针，数据行存放在内存中读取非常快，在Memory引擎中的默认索引类型就是哈希索引，Memory在发生哈希冲突时会用拉链法拉个链表，InnoDB的自适应哈希索引则会在察觉到某些索引被频繁使用时创建哈希索引。
