B树比AVL树或红黑树更快吗？

Question

B树比AVL树或红黑树更快吗？

algorithmdata-structuresbinary-tree

69

我知道性能从来不是非黑即白的，通常情况下某个实现在X情况下更快，在Y情况下更慢等，但总体而言，B树比AVL或RedBlack树更快吗？虽然它们比AVL树（甚至可能比RedBlack树）更复杂，但它们是否更快（它们的复杂性是否值得）？

编辑： 我还应该补充说，如果它们比等效的AVL / RedBlack树（以节点/内容为基准）更快-为什么它们更快？

- fredrikholmstrom

9个回答

111

实际上，维基百科有一篇很棒的文章，展示了每个红黑树都可以轻松地表示为B树。以以下树形结构为例：

现在只需将其转换为B树（为了更明显，节点仍然是红/黑色的，这通常不是B树中的情况）：

与B树相同的树

（由于某种奇怪的原因，无法在此处添加图像）

对于任何其他RB-Tree也是如此。它来自于这篇文章：

http://en.wikipedia.org/wiki/Red-black_tree

引用这篇文章的话：

红黑树在结构上等同于一个4阶B树，最小填充因子为每个簇的33％值，最大容量为3个值。

我没有找到任何数据表明其中一种显着优于另一种。如果是这样的话，我想其中一种已经消失了。它们在存储多少数据以及从树中添加/删除节点的复杂程度方面有所不同。

更新：

个人测试表明，在搜索数据时，B-树比其他树结构更好，因为它们具有更好的数据局部性，因此CPU缓存可以更快地进行比较。 B-树的阶数越高（阶数是一个节点可以拥有的子节点数），查找速度就越快。另一方面，随着其阶数的增加，添加和删除新条目的性能会变差。这是由于在节点内添加值具有线性复杂度的事实引起的。由于每个节点都是一个排序数组，在向中间添加元素时必须在该数组中移动大量元素：新元素左侧的所有元素必须向左移动一个位置，或者新元素右侧的所有元素必须向右移动一个位置。如果在插入过程中一个值向上移动一个节点（在B-树中经常发生），则会留下一个空洞，该空洞也必须通过将左侧的所有元素向右移动一个位置或将右侧的所有元素向左移动一个位置来填充。这些操作（在C中通常由memmove执行）实际上是O（n）。因此，B-树的阶数越高，查找速度越快，但修改速度越慢。另一方面，如果您选择的阶数太低（例如3），则在实践中B-树与其他树结构相比没有太大的优势或劣势（在这种情况下，您也可以使用其他结构）。因此，我总是创建具有高阶数的B-树（至少为4、8及以上）。

文件系统通常基于B树，使用更高的阶数（阶数200甚至更高）-这是因为它们通常选择足够高的阶数，使得一个节点（当包含允许的最大元素数量时）等于硬盘扇区或文件系统簇的大小。这提供了最佳性能（因为硬盘一次只能写入整个扇区，即使只更改一个字节，也会重写整个扇区）和最佳空间利用率（因为驱动器上的每个数据条目都至少等于一个簇的大小或簇大小的倍数，无论数据实际大小如何）。由于硬件将数据视为扇区，文件系统将扇区分组到簇中，B树可以为文件系统提供比任何其他树结构更好的性能和空间利用率；这就是为什么它们在文件系统中如此受欢迎的原因。

当您的应用程序不断更新树时，从中添加或删除值时，相对于具有高阶的B树，红黑树或AVL树平均可能表现更好。查找稍微差一些，并且可能需要更多的内存，但是修改通常很快。实际上，红黑树甚至比AVL树更快地进行修改，因此AVL树在查找方面略微更快，因为它们通常不太深。

因此，像往常一样，这在很大程度上取决于您的应用程序。我的建议是：

1. 大量查找，少量修改：B树（具有高阶数） 2. 大量查找，大量修改：AVL树 3. 少量查找，大量修改：红黑树

一个替代所有这些树的选择是AA-Trees。正如这份PDF 论文建议的所述，AA-Trees（实际上是RB-Trees的子组）在性能上几乎与普通的RB-Trees相当，但它们比RB-Trees、AVL-Trees或B-Trees更容易实现。这里是完整实现，看看它有多小（主函数不是实现的一部分，实现的一半实际上是注释）。

正如PDF论文所示，Treap也是经典树实现的一个有趣的替代方案。Treap也是一个二叉树，但它不试图强制平衡。为了避免在不平衡的二叉树中出现最坏情况（导致查找变成O(n)而不是O(log n)），Treap向树中添加了一些随机性。随机性不能保证树是平衡的，但它也使得树极不平衡的可能性非常小。

- Mecki

8

我希望我能给这个回答 +10 分，它是这里最好的（当然，是在更新之后）。 - Luís Guilherme

4

确实，这是最佳答案。 - deft_code

4

这个答案简直太棒了，绝对是最好的答案。 - fthinker

1

我在大多数地方缺少的是关于密钥大小的讨论，即随着密钥增加到可能达到缓存行大小，您会期望缓存优势得到平衡。我看到很多基准测试依赖于插入整数或短字符串，这通常是实际使用的方式，但并不总是如此。 - wds

2

@harshitgupta 就像爱因斯坦所说的，这都是相对的。如果您相对地进行更多的查找 - 即从数据库中读取一次但在代码中进行多次（超过一次）查找 -> 这就是“大量查找”。 - KIC

显示剩余2条评论

27

没有什么阻止一个仅在内存中运行的B-Tree实现。实际上，如果键比较便宜，内存中的B-Tree可以更快，因为它将多个键打包在一个节点中，这将在搜索期间导致较少的缓存未命中。请参见此链接进行性能比较。引用一句话：“速度测试结果很有趣，并表明对于包含超过16,000个项的树，B+树明显更快。”（B+树只是B-树的一种变体）。

- zvrba

这将直接放入我的书签文件夹中。 - Konrad Rudolph

2

答案有点弱，但链接是黄金的。 - deft_code

15

这个问题虽然有点老，但我认为它仍然值得关注。Jonas Kölker和Mecki提供了非常好的答案，但我不认为这些答案涵盖了整个故事。事实上，整个讨论都错了 :-).

当条目相对较小（整数、小字符串/单词、浮点数等）时，关于B-树所说的是正确的。当条目变大时（超过100B），差异变得更小/无关紧要。

让我总结一下B-树的主要特点:

它们比任何二叉搜索树（BSTs）更快，因为它们具有内存局部性（减少了缓存和TLB失效）。
如果条目相对较小或条目大小不同，则B-树通常更节省空间。自由空间管理更容易（您可以分配更大的内存块），每个条目的额外元数据开销更低。B-树会浪费一些空间，因为节点并不总是满的，但它们最终仍然比二叉搜索树更紧凑。
大O性能（O（logN））对于两者都是相同的。此外，如果在每个B-树节点中进行二进制搜索，甚至会得到与BST中相同数量的比较（这是一个很好的数学练习来验证这一点）。如果B-树节点大小合理（1-4倍缓存行大小），在每个节点内进行线性搜索仍然更快，因为硬件预取。您还可以使用SIMD指令来比较基本数据类型（例如整数）。
B-树更适合压缩：每个节点有更多的数据可压缩。在某些情况下，这可能是一项巨大的优势。只需想象一下用于构建索引的关系型数据库表中的自动递增键。 B-树的前导节点包含连续的整数，非常容易压缩。
当存储在二级存储器上时（需要进行块IO时），B-树显然要快得多。

在理论上，B-树有很多优点，几乎没有缺点。那么是否应该只使用B-树以获得最佳性能呢？

答案通常是NO——如果树适合存储在内存中的话。在关键性能问题上，您需要一个线程安全的类似树形的数据结构（简单地说，多个线程可以完成比单个线程更多的工作）。使B-树支持并发访问比使BST支持并发访问更具问题性。使树支持并发访问最直接的方法是在遍历/修改节点时锁定它们。在B-树中，您需要锁定更多的每个节点条目，导致更多的串行化点和更多的争用锁。

所有版本的树（AVL、Red / Black、B-Tree和其他）都有无数个变体，它们之间的差异在于它们如何支持并发性。大学课程教授或从一些入门书籍中阅读的基本算法几乎从未在实践中使用。因此，很难说哪棵树的表现最好，因为没有关于每棵树背后准确算法的正式协议。我建议将提到的树更多地视为遵守某些树状不变量的数据结构类，而不是精确的数据结构。

以B-树为例。几乎从不使用原始B-树——您无法使其扩展得很好！最常用的B-树变体是B+ -Tree（广泛应用于文件系统、数据库）。 B+-Tree和B-Tree之间的主要区别：1）您不在树的内部节点中存储条目（因此，在修改存储在内部节点中的条目时，您不需要在树的高处写入锁定）；2）您在同一级别的节点之间有链接（因此，在执行范围搜索时，您不必锁定节点的父节点）。

希望这可以帮助你。

- Radu

9

谷歌的工程师最近发布了他们基于B树实现的STL容器。他们声称，与基于红黑树实现的标准STL容器相比，他们的版本更快且占用更少的内存。

更多详细信息请点击这里

- Konstantin Chernov

2

对于某些应用程序而言，B树比BST快得多。您可以在这里找到的树：

http://freshmeat.net/projects/bps

非常快速。它们还使用的内存比普通BST实现要少，因为它们不需要每个节点2或3个指针的BST基础设施，以及一些额外的字段来保持平衡信息。

- Ciprian Niculescu

0

此外，红黑树的高度为O(log[2] N)，而B树的高度为O(log[q] N)，其中 ceiling[N]<= q <= N。因此，如果我们考虑B树中每个键数组的比较（如上所述固定），则B树的时间复杂度<=红黑树的时间复杂度。（对于大小等于块大小的单个记录相等的情况，两者时间复杂度相等）

- mohit

0

它们都具有相同的渐近行为，因此性能更多地取决于实现而不是使用哪种类型的树。某些树结构的组合可能实际上是最快的方法，其中B树的每个节点恰好适合缓存行，并且使用某种二叉树在每个节点内部进行搜索。自己管理节点的内存也可能使您实现更大的高速缓存局部性，但代价非常高。

就我个人而言，我只使用我正在使用的语言的标准库中的任何内容，因为这需要很多工作，而获得的性能提升非常小（如果有的话）。

从理论上讲... RB树实际上与B树非常相似，因为它们模拟2-3-4树的行为。AA树是一种类似的结构，它模拟2-3树。

- Jørgen Fogh

0

它们在不同的情况下被使用 - 当树节点需要在存储中保持在一起时，通常因为存储是磁盘页，所以重新平衡可能非常昂贵时使用B树。当您没有此约束时，使用RB树。因此，如果您想要实现（例如）关系数据库索引，则B树可能会更快，而如果您想进行内存搜索，则RB树可能会更快。

- anon

3

红黑树在内存搜索中不会更快。那个时代已经过去了。 - Stephan Eggermont

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jonas Kölker · Accepted Answer

肖恩的文章（目前被接受的）包含了几个错误的观点。抱歉肖恩，我不是故意无礼；我希望我能说服你，我的陈述是基于事实的。

它们在使用情况上完全不同，因此不可能进行比较。

它们都用于维护一组具有快速查找、插入和删除的完全排序项。它们具有相同的接口和相同的意图。

红黑树通常是内存结构，用于提供对数据的快速访问（理想情况下为O(logN)）。[...]

始终为 O(log n)

B树通常是基于磁盘的结构，因此比内存中的数据慢。

胡说八道。当您将搜索树存储在磁盘上时，通常会使用B树。这是真的。当您将数据存储在磁盘上时，访问速度比内存中的数据慢。但是存储在磁盘上的红黑树也比存储在内存中的红黑树要慢。

您正在进行不恰当的比较。真正有趣的是比较内存中的B树和内存中的红黑树。

[另外：与红黑树相反，B树在I/O模型中理论上是高效的。我已经对排序进行了实验测试（并验证了）I/O模型；我希望它也适用于B树。]

B树很少是二叉树，节点可以有许多子节点。

要清楚的是，B树节点的大小范围是树的一个参数（在C ++中，您可能希望使用整数值作为模板参数）。

B树结构的管理在数据变化时可能会非常复杂。

我记得它们比红黑树简单易懂（和实现）得多。

B树试图最小化磁盘访问次数，以便数据检索是相当确定的。

看到需要4个B树访问来查找数据库中的一些数据并不罕见。

在大多数情况下，我会说内存中的RB树更快。

因为查找是二进制的，所以很容易找到东西。 B树每个节点可以有多个子节点，因此在每个节点上，您必须扫描该节点以查找适当的子节点。这是O（N）操作。

每个节点的大小是一个固定参数，因此即使进行线性扫描，它也是O（1）。如果我们在每个节点的大小上进行大O分析，则通常保持数组排序，因此它是O（log n）。

在RB树上，它将是O（logN），因为您只进行了一次比较，然后进行了分支。

您正在比较不同的事物。 O（log n）是因为树的高度最多为O（log n），就像B树一样。

此外，除非您对红黑树进行恶意分配技巧，否则可以合理推测B树具有更好的缓存行为（它访问数组，而不是散布在各处的指针，并且具有较少的分配开销，进一步增加了内存局部性），这可能有助于在速度竞赛中获胜。

我可以指出实验证据表明，B树（具有特定大小参数32和64）在小型大小方面与红黑树非常有竞争力，并且在n的适度大值方面表现优异。请参见http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html B树更快。为什么？我推测这是由于内存局部性、更好的缓存行为和更少的指针追踪引起的（如果不是相同的事情，则在某种程度上重叠）。