MySQL主要提供2种方式的索引：B-Tree（包括B+Tree）索引，Hash索引。
B树索引具有范围查找和前缀查找的能力，对于N节点的B树，检索一条记录的复杂度为O(LogN)。
哈希索引只能做等于查找，但是无论多大的Hash表，查找复杂度都是O(1)。
显然，如果值的差异性大，并且以等于查找为主，Hash索引是更高效的选择，它有O(1)的查找复杂度。如果值的差异性相对较差，并且以范围查找为主，B树是更好的选择，它支持范围查找。
B树属于二叉平衡树，平衡树就是任何一个节点的左右节点高度差距不能超过1的树，这才是绝对平衡的树。
平衡树比较好的算法是AVL，它通过左旋、右旋及其组合的操作可以保证树绝对平衡。
下面是AVL算法中的全部旋转操作：
平衡树处在任何一个左边的不平衡状态都可以通过相应的旋转操作转移到右边的平衡状态。
数据库采用的B树只在叶子节点记录信息，非叶子节点记录的是范围信息，这是与一般搜索树不同的地方（一般搜索树非叶子节点也记录信息）。
这是一个B+树的结构，InnoDB的索引都采取了这种形式，它在B-树的基础上为每个叶子节点加了一个指针指向下一个叶子节点，这样可以快速的进行范围查找。
BTREE和Hash的区别
1、Hash 索引，其检索效率非常高，索引的检索可以一次定位。BTREE 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问
2、Hash 索引仅仅能满足"=",“IN"和”<=>"查询，不能使用范围查询。
3、Hash 索引无法被用来避免数据的排序操作
4、Hash 索引不能利用部分索引键查询。
5、Hash 索引在任何时候都不能避免表扫描。
6、Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。