红黑树B树B+树区别及其适用场景

概述

红黑树B树B+树是我们经常听到的数据结构,在各大组件设计和实现使用的很多,我们只有根本上分析这几种树结构的区别,才能从根本上明白一些组件这样设计的原因.

红黑树

1.节点由红黑节点组成
2.根节点是黑色节点
3.叶子节点是黑色节点,并且值为null
4.一个节点是红色节点,那么它的子节点都是黑色节点
5.每个节点到叶子节点的所有路径，都包含相同数目的黑色节点
6.红黑树是一颗平衡二叉树

这个也是满足红黑树的规则的.我们可以好好想想为什么会有红黑树. 红黑树其实是属于平衡二叉树一种, 但是上图这种是不满足完全平衡二叉树严格的规则的(任意子树高度小于等于1), 红黑树就是牺牲一定平衡性,来提高插入,删除带来旋转操作性能

适用场景:
红黑树也是属于二叉树一种,意味着数据量大的时候,树的高度还是很高的,不适合io级别的操作,更适合内存级别的应用,比如像JDK HsahMap,TreeSet,像数据库底层结构不适合使用红黑树作为存储载体.

B树

1.m阶B树(B树中所有结点的孩子结点最大值称为B树的阶),如图是三阶B树
2.每个非叶子结点都包含m-1个数据元素和m个孩子节点
3.每个叶子结点都包含m-1个数据元素

注意: 通过保证每个节点的个数限制,当数据元素个数超过要求阈值,那么进行转向操作来保证树的平衡

适用场景:
已经对红黑树高度比较深已经做了改进,通过增加节点内部元素数量,变成一个n叉树来解决,这个树高度大大降低,对于像数据库组件就可以考虑用来存储,从而提高检索性能了,io操作是个耗时操作,高度降低,io次数大大减少

缺点:
全量数据还是保存在所有节点上,这样当节点大小固定时,一个节点存储的数据量并不多,依然可能导致树高度剧增.相比二叉树要好得多

B+树

B+树是B树变种,主要是为了更加迎合数据库组件需要,除了上面三个约束外,另外增加两个约束

1. 非叶子结点只存储索引关键字数据,不存全量数据
2. 叶子结点数据之间通过双向链表链接,方便范围检索

适用场景
相对于B树,有着更明显适用于数据库组件存储结构的特性,非叶子结点只存储检索关键字,大大提高了单个非叶子结点的数据量,从而进一步压缩树的高度,大大提高检索性能