数据库中的数据一般是放在磁盘里面，存取数据的时候就要访问磁盘，物理访问过程：盘片旋转，磁臂移动 两个过程。盘片旋转到指定位置之后，移动磁臂开始进行数据的存取。如果使用顺序查找，查询数据的时候就要从头到尾查询一遍，如果所查询的数据靠近数据尾端，效率久会很低，当然，这种方式也是最低效率的。因此，出现了二叉树。

二叉树

二叉树是一种非常重要的数据结构，它同时具有数组和链表各自的特点：它可以像数组一样快速查找，也可以像链表一样快速添加。但是它也有自己的缺点：删除操作复杂。

二叉树在插入数据时也存在一个很大的缺点：

在使用二叉树插入节点时：一个节点的左节点的关键值必须小于此节点，右节点必须大于或者等于此节点。

通过上面定义可以发现：如果插入的数据是有序的，二叉树就会形成一个分支的树结构，远远增加了树的深度。因而为了提高效率稳定性，形成了平衡二叉树：

平衡二叉树：

平衡二叉树用平衡因子差值来判断是否平衡，并旋转二叉树。平衡因子：左右子树高度差。平衡二叉树里平衡因子不能超过1，否则旋转。

缺点：

平衡二叉树虽然达到了稳定，但是由于不停的旋转，时间方面浪费了很多，从而效率又降了下来。

那么怎样才能稳定的同时，旋转的次数少？         再次升级-->红黑树

红黑树：

定义：

1、每个节点要么是红色，要么是黑色。

2、根节点必须是黑色。

3、红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。

4、对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。

红黑树旋转的关键逻辑是：确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。例如：节点A，左子树高度X，右子树高度Y， X-Y<=min(X,Y);如果当 X-Y > min(X,Y)，然后开始旋转。

在java中TreeSet的数据结构底层就是用的红黑树

红黑树虽然解决了稳定、时间浪费的问题，但是，我们一开始就说了，数据库中的数据一般是存在磁盘上的，如果考虑到磁盘IO的影响，当数据量过大，就有可能不能一次性读取到内存中；反复的从磁盘到内存，效率就又会降低！

读取磁盘次数过多，读取浪费就太多，这也是MySql不使用红黑树作为索引的原因

B树

多路存储能力

考虑到磁盘IO,内存的影响，所以产生了B树。B树：每个节点上都存有key和value，所以每次读取数据时，只需把相应的节点读取到内存中即可，而不需把整个树都读取到内存。等价于有关键字的二分查找，所以B树解决了红黑树存在的问题。

问题：

B树虽然解决了磁盘读取到内存效率降低的问题，但是由于B树的每一个节点上都存有数据，那么就会造成空间浪费，范围查找还是没有解决。那应该怎么解决呢?再次升级-->B+树！

B+树：

B+树中所有的数据都存在叶子节点中，并且叶子节点中还加了指针形成了链表，其他的都是索引，增加了系统的稳定性以及遍历以及查找效率。

MySql索引采用B+树        为什么MySql中索引采用B+树？

通过应用场景，我们可以知道。再通过MySql查询数据时，我们通常查询的不只是一条数据，大多数情况下都是多条数据。如果采用B树，查询多条时，可能需要跨层获取数据，所以，B+树中叶子节点之间增加了指针形成了链表结构，查询多条数据时更加的快速，因此MySql中索引采用了B+树，提高了效率！

hash比B+树更快，为什么MySql没有采用hash?

如果查询一条数据的话，hash确实比B+树快。但是正如我们上面所说，我们查询数据时通常是多条的，这时候由于B+树索引有序并且还有链表相连，而且数据库中的索引一般在磁盘，数据量大的时候，B+树可以允许数据分批，同时树的高度比较低，也提高了查询效率，所以多数据时B+树会更快。