红黑树，b+树分别用于什么场景，为什么

红黑树属于“黑平衡”的二叉树，虽然牺牲了一定的平衡性，但是add、remove *** 作要由优于AVL树也就是说RB-Tree的“统计性能”更佳！Java中TreeSet，TreeMap的底层都是基于RedBlackTree红黑树的；

B+树主要用在文件系统以及数据库做索引。比如磁盘存储、文件系统、MySQL数据库

    二叉树：当不平衡时，单边增长，可能退化为线性

    红黑树：数据量大时，深度不可控

    AVL树：相比较与红黑树，严格平衡，但是增删情况下，通过旋转再平衡的开销过大，适合查找场景多的应用

    Hash： 不支持范围查找

    平衡的多路查找树，一个结点存放多个元素。

与红黑树相比，在相同的的节点的情况下，一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到)。B/B+树上 *** 作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成，而CPU的速度非常快，所以B树的 *** 作效率取决于访问磁盘的次数，关键字总数相同的情况下B树的高度越小，磁盘I/O所花的时间越少。

    m阶：节点中，子节点数的最大值（子节点数，不是结点存放元素）

1. 树中每个结点最多m个子树（最多m-1个关键字，两个子树夹一个关键字）

2. 根节点最少有1个关键字

3. 非根结点最少m/2个子树（m/2 - 1个关键字）

4. 每个关键字排序

5. 所有的叶子结点位于同一层

6. 每个结点都存有索引和数据

（1）简介

B+树是应文件系统所需而产生的一种B树的变形树（文件的目录一级一级索引，只有最底层的叶子节点（文件）保存数据）非叶子节点只保存索引，不保存实际的数据，数据都保存在叶子节点中。所有的非叶子节点都可以看成索引部分！

（2）B+树的性质(下面提到的都是和B树不相同的性质)

1. b+树有两种类型的结点：

1.1 内部结点（索引结点，非叶结点）： 只存索引，不存数据

1.2 叶子结点 （存数据）

2. 内部结点 和 叶子结点的 key递增排序

3. 每个叶结点存有相邻叶结点的指针

4. 父结点存有右孩子第一个元素索引

1.磁盘io代价低：b+树的非叶结点只存储索引，不存储数据，单一结点能存放的索引数更多，树更矮胖

2. b+树查询效率稳定：所有查询必须到叶节点

3. b+树叶子节点为有序表，效率更高，支持范围查询。

红黑树是处于二叉树和平衡二叉树之间的一种折中方案的算法。说起来红黑树也算是比较难理解的一个数据结构了吧，因为其本身的增删节点，除了左旋右旋还需要变色的复杂 *** 作。

为什么有平衡二叉树这种适合适合查找的数据结构在，还需要红黑树呢？还是先从二叉树说起。

二叉查找树的特点就是 左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大。

二叉树的查询颇有 二分查找 的思想，如果查询一个节点，n 个节点的二叉查找树，正常的情况下，查找的时间复杂度为 O（logn）。为什么说是正常情况，因为上面的树其实不只是二叉树而且还是平衡二叉树。

那如果不正常的情况下，二叉树是啥样的呢？下面是一种退化为类似链表的二叉树的极端情况。这样的二叉查找树的查找时间复杂度顿时变成了 O(n)，类似于在做全表扫描，为了避免这种情况的发生，平衡二叉树在这种情况下登场了。平衡二叉树除了具有二叉树的全部特性外，加了一个规则，就是每个节点的左子树和右子树的高度差至多等于1。

嗯，这样的话就不会出现一棵链表了。平衡二叉树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了。这样平衡二叉树对于有 n 个节点的平衡树，最坏的查找时间复杂度也为 O(logn)。平衡二叉树通过 构建、插入、删除、左旋、右旋 等 *** 作来达到平衡。

MySQL索引中 B树和B+树是基于平衡二叉树的进一步改进 。B+树索引按照存储方式的不同分为 聚集索引 和 非聚集索引。

二叉树的算法实现 其实就是要插入的节点都开始和根节点比，小的放节点左边大的右边，如果位置上已经有节点了就再迭代，把当前节点作为根节点来判断放左右，直到有空位置为止。

有了平衡二叉树这么优秀的结构为什么还需要红黑树，因为平衡二叉树要求 每个节点的左子树和右子树的高度差至多等于1 ，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树规则，进而我们都需要通过 左旋 和 右旋 来进行调整，使之再次成为一颗符合要求的平衡树。如果频繁增删就会带来性能问题。所以红黑树出现了。

红黑树特性：

1、具有二叉查找树的特点。

2、根节点是黑色的；

3、 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据 。

4、 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的。

5、 每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。（限制了高度）

下面是两棵红黑树的例子（黑色的空叶子节点没有画出）：

上面的例子似乎有点平衡二叉树的味道，但它并不是必须满足平衡二叉树的深度差不超过1的条件，如下面的例子。

红黑树的这种特点，使得它能够在最坏情况下，也能在 O(logn) 的时间复杂度查找到某个节点。但与平衡树不同的是，红黑树在插入、删除等 *** 作， 不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整。 意思是查效率相当，但改效率高于平衡树，这也是我们为什么大多数情况下使用红黑树的原因。只不过据说单单在查找方面的效率的话，平衡树会比红黑树快点。

综上，可以说 红黑树是一种不大严格（没有深度差要求）的平衡树 。也可以说是一个折中方案。

那么红黑树如何进行左旋，右旋和变色来达到平衡呢 ?笔者也还没完全吃透，不过理解了上面的这些应该也够驰骋沙场了。

参考文献：

腾讯面试题：有了二叉查找树、平衡树为啥还需要红黑树？

红黑树旋转

---