红黑树与B+树的对比

发表于 | 分类于 | 本文总阅读量

红黑树和B+树是两种比较重要的高级数据结构。接下来我们来对二者做一个对比分析。

红黑树

1
2
3
4
5
6
7
红黑树的五个性质：
一般的，红黑树(一棵自平衡的排序二叉树)，满足以下性质，即只有满足以下性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

B+树

1
2
3
4
5
6
7
一个m阶的B+树具有如下几个特征：

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B树

1
2
3
4
5
6
7
8
9
10
11
一个m阶的B树具有如下几个特征：

1.根结点至少有两个子女。

2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

对比分析

数据结构 查询性能 插入性能 删除性能 优点 缺点 适用场景
红黑树 O(logN) O(logN) O(logN) 增删查性能高，相对平衡二叉树简单 树的深度相对B树高 用在内部排序，即全放在内存中的，如：STC的map；hashtable冲突到一定程度链表改为红黑树；epoll监听句柄
平衡二叉树 O(logN) O(logN) O(logN) 增删查性能高 维护平衡的旋转逻辑复杂 暂无
B+树 与树高有关，不超过节点数 同查询 同查询 完美支持磁盘预读 性能相比红黑树差 数据库索引
B-树 与树高有关，不超过节点数 同查询 同查询 支持磁盘预读 节点存储数据，相比B+树占用空间大 数据库索引

参考资料

  1. 红黑树的定义与运用场景
  2. 平衡二叉树、B树、B+树、B*树、LSM树简介