## **索引结构** MySQL中常用的索引结构（索引底层的数据结构）有：B-TREE ，B+TREE ，HASH 等。 ### **B-TREE** B-树就是B树，多路搜索树，树高一层意味着多一次的磁盘I/O，下图是3阶B树  B树的特征： * 关键字集合分布在整颗树中； * 任何一个关键字出现且只出现在一个结点中； * 搜索有可能在非叶子结点结束； * 其搜索性能等价于在关键字全集内做一次二分查找； * 自动层次控制； ### **B+TREE** B+树是B-树的变体，也是一种多路搜索树 B+树的特征：  所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的； 不可能在非叶子结点命中； 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层； 每一个叶子节点都包含指向下一个叶子节点的指针，从而方便叶子节点的范围遍历。 更适合文件索引系统； ### **HASH** 哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。  Hash索引仅仅能满足"=",“IN"和”<=>"查询，不能使用范围查询。也不支持任何范围查询，例如WHERE price > 100。 　　 由于Hash索引比较的是进行Hash运算之后的Hash值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的Hash算法处理之后的Hash值的大小关系，并不能保证和Hash运算前完全一样。