【原创】二叉树、红黑树、B树、B+树总结

二叉树

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”，左子树和右子树同时也是二叉树。

二叉排序树

二叉排序树又叫二叉查找树或者二叉搜索树，它首先是一个二叉树，而且必须满足下面的条件：

• 若左子树不空，则左子树上所有结点的值均小于它的根节点的值；
• 若右子树不空，则右子树上所有结点的值均大于它的根结点的值
• 左、右子树也分别为二叉排序树
• 没有键值相等的节点（？可能是因为不好处理键值相等的节点到底是左节点还是右节点吧）

二叉树的缺点

如果元素递增，会退化成链表，因此产生了红黑树，红黑树可以有效地避免这种情况。

红黑树

参考：https://www.cnblogs.com/CarpenterLee/p/5503882.html
红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。具体来说，红黑树是满足如下条件的二叉查找树（binary search tree）：

• 每个节点要么是红色，要么是黑色。
• 根节点必须是黑色。
• 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
• 对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。

红黑树的缺点

随着元素的增加，树会逐渐增高。B 树可以避免这种情况。

B 树

参考： https://www.cnblogs.com/vincently/p/4526560.html

B树在横向上面扩展新的节点，从而容纳更多元素，由此可以降低树的高度。B树既要满足平衡二叉树的特点，又要让树变得不高。

B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

B+ 树的优点在于：
由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。