AVL树、B树、B+树以及红黑树的区别

有了AVL树为什么还要B树？

虽然AVL树很平衡，但由于它仍是二叉树，所以其高度仍可能较高，不利于磁盘IO（磁盘IO次数与树高度成正比）。而在同样多节点情况下，B树比AVL矮胖得多，大大减少了IO次数，提高了效率。

有了B树为什么还要B+树？

B+树中所有非叶结点仅起素引作用,每个素引项只含有对应子树的最大关键字和指向该子树的指针,不含有对应数据的存储地址。因此B+树比B树更矮胖，每次IO就能够读取更多的关键字,使得磁盘IO次数更少,查找速度更快。
B+树增删时，对树的拓扑结构的改变更小，因此效率更高。
B+树的叶子结点被组织为一个链表，这利于数据库的范围查询（直接顺序遍历），而B树则只能通过树型遍历进行范围查询。

有了B树为什么还要红黑树？

B树在磁盘上，而红黑树往往在内存里（比如STL库的map）。磁盘IO的速度比内存操作的速度慢得多。所以读取磁盘时我们应该偏向降低IO次数（即降低树高度）来提高效率；而在内存中，B树较低高度带来的好处就被它频繁且复杂的旋转操作所抵消了，此时我们希望尽可能少地改变树的拓扑结构，而红黑树就能做到这点。

有了AVL树为什么还要红黑树？

AVL树的平衡条件过为苛刻，因此需要频繁地进行旋转操作：比如在删除节点后，可能会从删除位置一直旋转到根节点，因此它高频旋转带来的劣势也同样抵消了其优越的平衡性。红黑树的“适度平衡”——任意一个结点左右子树的高度,相差不超过 2倍”——降低了动态操作时调整的频率。对于一棵动态查找树,若插入和删除操作比较少,查找操作比较多,则采用 AVL树比较合适,否则采用红黑树更合适。但由于维护这种高度平衡所付出的代价比获得的效益大得多,红黑树的实际应用更广泛。

下面两张图直观展示了红黑树的优越特性：

也就是说，红黑树只需要经过最多三次旋转即可完成插入和删除，而AVL树和B树的旋转操作则可能一直回溯到根节点！
以上是个人理解，欢迎指正。