BST(非平衡),AVL,红黑树,B+树的区别与应用

本文出自kelvin.ink
转载请注明出处

问题要点

这个问题要探究的要点是:


1. 这四种树的定义的了解
2. 这些树的主要区别,特性
3. 每种树的具体应用场景是什么,为何它适合于这种场景,为什么不用其他树代替

事实上Knuth Donald在《计算机编程艺术》中已经对这些树都作了非常深刻的说明,建议想要深入探究的读者可以自行找到这本书进行阅读。Google books有这本书的影印版。可以搜索6.2.2Binary Tree Search找到相应的章节。本文在此基础上结合其他资源对这个问题进行简要说明,并尽量保证self contained。

简明定义

我们先回顾一下这几种树的定义,为继续下一步的讨论建立共识。

二叉搜索树(BST)

简明BST递归定义(Knuth Donald):


对于任意一个节点均满足:
1. 所有位于左子树的节点值均比该节点值小
2. 所有位于右子树的节点值均大于等于该节点值
3. 所有左子树和右子树也必须是BST

AVL

简明AVL定义(Knuth Donald):

对于任意一个节点均满足:


1. 左子树和右子树的高度差小于等于1

红黑树

简明RBTREE定义(Knuth Donald):


1. 每个节点要么是红色,要么是黑色
2. 根节点是黑色
3. 所有叶节点(NIL)都是黑色
4. 如果一个节点是红色,那么它的两个孩子都是黑色
5. 从任意一个节点出发,到达其后代NIL节点的路径中都包含相同个数的黑节点

B+树

定义Branch Factor: b 为一个节点可以拥有的最大子节点的个数,那么:


1. 对于根节点,如果整棵树的节点个数大于1,那么根节点的子节点数量大于等于2
2. 对于内部节点,其子节点个数m必须满足 b/2 <= m <= b
3. 对于叶节点,其子节点个数m必须满足 b/2 <= m <= b
4. 每个节点内部的key值是已经排序的
5. 叶节点之间以linked list方式相连并且是有序的
6. 从根节点到叶节点的路径长度均相同

推荐阅读


BST: https://en.wikipedia.org/wiki/Binary_search_tree
AVL: https://en.wikipedia.org/wiki/AVL_tree
RBTREE: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
B+TREE: https://en.wikipedia.org/wiki/B%2B_tree

树的特性

基于上面对各种树的定义,我们可以推出它们的一些相关特性,本节我们将会罗列并解析这几种树的一些相关特性。

复杂度

我们先比较一下它的在进行各种操作时的复杂度:
Complexity

上面表格每个单元格显示的是平均复杂度/最差复杂度。我们可以看到除了BST外,其他树在查找,插入和删除操作时的复杂度均为O(logn),因为它们都是平衡树,而BST不是。相同的渐近复杂度并不意味着它们毫无区别,毕竟它们可能会相差数倍的关系。接下来我们会描述这些树的一些具体特性,并突出它们的主要区别。

1
//Todo

树的应用

BST

通常情况下非平衡的BST都仅仅当作一种概念,很少有实际场景会使用这种结构,因为查找在最差的情况下会出现O(n)的时间复杂度。虽然如此,我们依然可以了解一下它能够实现点什么,即使我们实际应用不会这么做。

BST可以实现:

  • 排序
  • 优先队列

BST排序的实现是把输入的元素一个个插入到BST,然后进行一次中序遍历,平均复杂度为O(nlogn)。优先队列(min)的实现是从根节点出发一直向左找到最小节点,平均复杂度为O(logn),最差状况为O(n),显然它在时间复杂度上是比不上min-heap的。

AVL

AVL是历史上出现的第一种平衡二叉树,它现在的很多应用都已经被红黑树代替。主要原因是它的平衡限制比较红黑树严格,在插入或者删除节点的时候很容易违反平衡限制条件,造成频繁的树结构调整和重新平衡。AVL限制对每个节点左子树和右子树的高度相差不超过一,所以它是高度平衡的二叉树,因而在进行查找的时候效率很高。而红黑树的平衡限制比AVL要弱,甚至左右子树的高度差等于2倍,所以红黑树的查找效率比AVL要低。但是,红黑树不需要频繁重平衡(得益于其宽松的限制条件),所以在插入删除较频繁的环境中红黑树胜出。

红黑树

红黑树虽然定义复杂,但是它的限制条件是相对AVL宽松的。所以在进行插入删除操作的时候出现违反限制条件的状况较少,因而重平衡操作出现的机会比AVL少。基于上述原因,许多需要进行频繁删插操作的场景都使用来红黑树:

  • Linux epoll
  • C++ STL(sert, map)
  • Completely Fair Sheduler

B+树

B+树主要应用于文件系统中,最大的原因是它高度平衡,branch factor较大,这样可以减少磁盘IO。

B+树主流应用:

  • 数据库索引(SQL Server, PostgreSQL, SQLite)
  • 文件系统(NTFS XFS, NSS, JFS)

树的区别

比较AVL与红黑树的优缺点

在前面已经比较过了这两者的优缺点,为了突出它们的区别,特意把上面一段文字复制到本问题下:

AVL是历史上出现的第一种平衡二叉树,它现在的很多应用都已经被红黑树代替。主要原因是它的平衡限制比较红黑树严格,在插入或者删除节点的时候很容易超出平衡限制条件,造成频繁的树结构调整和重新平衡。AVL限制对每个节点左子树和右子树的高度相差不超过一,所以它是高度平衡的二叉树,因而在进行查找的时候效率很高。而红黑树的平衡限制比AVL要弱,甚至左右子树的高度差等于2倍,所以红黑树的查找效率被AVL要低。但是,红黑树不需要频繁重平衡(得益于其宽松的限制条件),所以在插入删除较频繁的环境中红黑树胜出。REF

同时我们看看Knuth对于AVL的评价:
Knuth AVL Tree Comment

为何数据库索引使用B+树而不是红黑树(或其他)

要理解这个问题,我们先分析一下数据库的性质。数据库的数据被分割为多个Page以文件的形式储存在磁盘上的。因此我们每次进行数据库查询其实是在做Disk IO,而Disk IO是时间开销较大的操作(关键!)。而数据库在进行索引lookup的时候每次access一个page都是一次IO。因此我们需要选择一种能够尽量少做Disk IO的数据结构来构建索引。B+树之所以被选中主要是因为它的branch factor较大,树高较小。因而在进行索引搜索的时候需要进行的IO数量也较其他树的数量小,所以是最合适的做索引的数据结构。基于上述原因,在应用场景需要选树的时候我们都会做如下的思考:基于内存操作的我们考虑红黑树,AVL和BST,基于磁盘操作的我们优先考虑B或B+树。REF

我们在这边引用一段Knuth对于B+树的精彩评价来佐证我们的观点:
Knuth B+ Tree Comment

References:

Key References
Knuth Donald(1997) 6.2.2:Binary Tree Searching. The Art of Computer Programming
Ben Pfaff https://web.stanford.edu/~blp/papers/libavl.pdf