红黑树

什么是红黑树？

是一个特殊的AVL（平衡二叉搜索树）,需要遵守几个条件

1、根节点得是黑色的

2、连续两个红色节点不能连续

3、根节点到每个子节点遇到的黑色节点数量相同

特点：

1、根节点是黑色的

2、最大长度为2*（log（n+1））

B树

2-3树是B树的一种特例，二叉搜索树搜索效率高，但是为了保持平衡需要的代价太大，所以人想出了一个结点允许多个值的数据结构-B树

特点：

1、所有叶子子结点在同一层上面，和平衡二叉树比层数低，磁盘io少，加快了查询插入速度

2、每个节点的元素从小到大排列

操作系统索引表也用了b+树

B+树

特点：

1、所有叶子节点都在同一层，并且中间结点是他的子结点的最大或者最小值，最大值在根节点中

2、所有数据都在子结点上面，子结点包括了所有信息，每个元素不保存数据只用来索引，查询稳定，所有子结点都链接起来，导出全部数据方便

3、非叶子节点只有key，没有value，叶子节点有key，value

B树和B+树的区别，为什么mysql会选b+树

卫星数据：指索引元素所指向的数据记录，比如数据库中的某一行。

1、B+树的中间节点没有卫星数据，同样大小的磁盘页可以容纳更多的节点元素。意味着，数据量相同的情况下，B+树的结构比B树更加矮胖，因此查询时IO次数更少，B+树更加的矮胖一点，磁盘IO操作少，查询速度比B快

2、数据库扫库更加方便，范围查询更加方便，查询一段区别的数据比B树方便

3、查询性能更加稳定，B+树得每次查到叶子结点，B树可能查到中间结点查到数据就终止

hash比B+树快,为什么还选B+树

因为只选一个数据是hash块，但是范数据量大无法一次装入内存，范围查询的话是B+树快