肖恩（Sean）的帖子（目前接受的帖子）包含多项不正确的声明。抱歉，肖恩，我不是无礼的。希望我能说服您我的陈述是事实。

它们的用例完全不同，因此无法进行比较。

它们都用于通过快速查找，插入和删除来维护一组完全有序的项目。它们具有相同的界面和相同的意图。

RB树通常是用于提供对数据的快速访问（理想情况下为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（log
n）。

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

您正在比较苹果和桔子。O（log n）是因为树的高度最多为O（log n），就像B树一样。

另外，除非您对红黑树玩弄讨厌的分配技巧，否则可以合理地推测出B树具有更好的缓存行为（它访问数组，而不是遍布各处的指针，并且分配开销较少，从而增加了内存本地性），这可能有助于在速度竞赛中发挥作用。

我可以指出一些实验证据，即B树（大小参数分别为32和64）与小尺寸的红黑树竞争非常激烈，并且即使n的值较大，其性能也优于B树。参见http://idlebox.net/2007/stx-
btree/stx-btree-0.8.3/doxygen-
html/speedtest.html

B树更快。为什么？我猜想这是由于内存局部性，更好的缓存行为和更少的指针追逐（如果不是同一件事，它们在某种程度上会重叠）。