一、mysql索引结构

B+树：

B树是⼀个平衡的多叉树，一个节点可以有多个数据内容,这样就不会出现二叉树那样数据庞大的时候,树的高度比较高的情况,查询的次数就会少，B+树叶子节点间有指针相互链接,并且会维护了索引的顺序的,所以有顺序、有相邻的引用,这样在执行范围查找的时候,就可以左右移动,范围查找的效率就会高很多。所以数据庞大的时候，B+树被⼴泛使用,数据库、⽂件系统等场景。

哈希索引：

哈希索引就是采⽤⼀定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶⼦节点逐级查找，只需⼀次哈希算法即可⽴刻定位到相应的位置，速度⾮常快。

如果是等值查询，那么哈希索引明显有绝对优势，因为只需要经过⼀次算法即可找到相应的键值；

前提是键值都是唯⼀的。如果键值不是唯⼀的，就需要先找到该键所在位置，然后再根据链表往后扫描，直 到找到相应的数据；

如果是范围查询检索，这时候哈希索引就毫⽆⽤武之地了，因为原先是有序的键值，经过哈希算法后，有可能变成不连续的了，就没办法再利⽤索引完成范围查询检索；

哈希索引也没办法利⽤索引完成排序，以及like ‘xxx%’ 这样的部分模糊查询（这种部分模糊查询，其实本质上也是范围查询）；

在有⼤量重复键值情况下，哈希索引的效率也是极低的，因为存在哈希碰撞问题。

红黑树:

红黑树也可以查询很快,都是红黑树在数据很多的情况下,树的高度是很高的，所以也不用来做索引了。

普通二叉树这就更加不行了,高度不说了,它还不会平衡。

如果123456这样按照顺序添加,1永远是跟节点,依次增加就之后在树的右边加。

延伸阅读：

二、索引及其优缺点

索引本质：索引是数据结构。这些数据结构以某种方式指向数据，这样可以在这些数据结构的基础上实现高效查找算法。

索引是在存储引擎实现的，因此每种存储引擎的索引不一定完全相同，并且每种存储引擎不一定支持所有类型的索引。同时存储引擎可以定义每个表的最大索引数和最大索引长度。所有存储引擎支持每个表至少16个索引，总索引长度至少为256字节。

优点：

1、提高数据检索的效率，降低数据库的I/O成本

2、通过创建少数索引，可以保证数据库表中每一行数据的少数性

3、可以加速表和表之间的连接。对于有依赖关系的子表和父表联合查询时，可以提高查询速度

4、在使用分组和排序子句进行数据查询时，可以显著减少查询中分组和排序的时间，降低CPU的消耗

缺点：

1、创建索引和维护索引要耗费时间

2、索引需要占磁盘空间，存储在磁盘上

3、虽然索引大大提高了查询 速度，同时也会降低更新表的速度