索引是帮助mysql高效获取数据的排好序的数据结构。

索引数据结构

一、二叉树

当数据是有序递增的时候，二叉树退化为链表结构，查询效率低，比如查询数字5，需要查询5次。

二、红黑树

查询5的时候需要查询4次

B树

叶节点具有相同的深度，叶节点的指针为空；
所有的索引元素不重复
节点中的数据索引从左到又依次递增

查询5的话，需要查询3次。

四、B+树

非叶子节点不存储data，只存储索引（存在冗余），可以放更多的索引（mysql中用数据页存储，不存data，可以放更多的索引）。
叶子节点包含所有的索引
叶子节点用指针连接，提高区间之间的访问能力

查询5的话，查询2次就可以了，明显查询效率更高，而且叶子节点包含data，并且是有序的，而且有链表，范围查询效率也会很高。

Hash结构

对于一些索引，一次hash算法就可以定位
但是仅能满足“=”，“in”等，不支持范围查找
hash冲突还要再在链表上查找

B+树对比B树的优点：

1、非叶子节点不存储数据，那么每个数据页中可以放更多的索引，当数据量大的时候，可以更好的控制树的高度，而且将查询定位过程与加载数据过程分离，提高了查询效率；
2、叶子节点之间的链表相连的设计，提高了范围查询的效率。

数据可视化工具网址