AVL树

• 平衡二叉查找树，规则如下：
• 左右子树的高度差小于等于1。
• 其每一个子树均为平衡二叉树。

红黑树

• 节点分为红色或者黑色。
• 根节点必为黑色。
• 叶子节点都为黑色，且为 null。
• 连接红色节点的两个子节点都为黑色(红黑树不会出现相邻的红色节点)。
• 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点。
• 新加入到红黑树的节点为红色节点。（因为插入的节点一定是红色节点，否则一定会破坏“任意节点到叶子节点的路径中黑节点个数相同”的规则）

红黑树示例如下：

红黑树插入时不用旋转的情况

当插入的节点父节点是黑色时，什么都不用动。
当插入节点的父节点和叔父节点是红色时。可以通过变色来解决，如下图所示：

最终对不符合规则的部分仅通过变色处理就可平衡：

B树

多路查找树，每个节点存储key和数据，所有节点组成这个树，叶子节点指向null。

B+树

也是一种多路查找树，但是只有叶子节点存储data。其余节点只存储查找的键。且B+树每个叶子节点都包含指向下一个叶子节点的指针，即所有叶子节点都连在一起。

AVL和红黑树

AVL追求严格的平衡，所以AVL的查找效率更高。但是AVL在处理由于添加和删除的时候带来的失衡的时候，要花费更高的代价。
红黑树的旋转操作非常局部化，次数极少（插入最多两次，删除最多三次），而且红黑树的变色操作不会影响其他线程的查询操作，即不需要在对红黑树变色的时候锁住。红黑树能达到logn的高度，但不需要严格规定左右子树高度差相差不超过1.
所以红黑树的查询性能略逊于AVL，但是综合增删改查而言，综合性能优于AVL。所以也可以回答为什么HashMap中不使用AVL，因为增删改的操作是比较频繁的。

B树和红黑树

B树是多路查找树，理论上查找时间复杂度肯定是高于二叉树的。但是对于数据库中的检索，需要关心另一个问题，即磁盘IO。
不同于AVL和红黑树的比较，AVL和红黑树的比较可以说是基于树的所有节点都在内存中去比较查找效率的。但是对于数据库的数据来说，树是存储在磁盘上的。每经过一个树的节点都需要进行磁盘IO。在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况。所以我们希望经过尽可能少的节点就到叶子节点，即树要尽可能矮，所以使用多路查找树。B树可以有几十到上千个子女，降低了树的高度。

B树和B+树

同样回到B树和红黑树比较的场景中，再次重复我们在磁盘查找时希望达到的目标：希望经过尽可能少的节点，因为每经过一次节点都需要磁盘IO。
此时引出B+树，B+树只有叶子节点存储数据，其余节点只存放查找的关键字和叶子节点的指针，所以叶子节点外的节点所占空间更小。一个块中可以存放更多节点，因此可以降低树的高度，因为一个内部节点可以指向更多叶子节点。
另外一个重要的点是B+树中每个叶子节点都包含指向下一个叶子节点的指针。所有叶子节点都是通过指针连接在一起，而B树不会。叶子节点之间通过指针来连接，范围扫描将十分简单，而对于B树来说，则需要在叶子节点和内部节点不停的往返移动。有了这个特点，B+树遍历更加高效，方便扫库。而B树还必须用中序遍历的方式按序扫库，B+树直接在叶子节点中扫就可以了。这是数据库使用B+树最主要的原因。

总结：

1) B+的磁盘读写代价更低
B+的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

2) B+tree的查询效率更加稳定
由于非叶子结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。对于B树而言，在内部节点的数据，可直接得到，不必根据叶子节点来定位。

3) B+树解决了B树遍历性能低下的问题
B+树只需要遍历叶子节点就可遍历整个数