我知道性能永不是黑色和白色，往往一个实施更快的情况下的X和较慢的情况下Y，等，但在一般的 - 是B树更快然后AVL或RedBlack-树？他们是相当复杂实现再AVL树（甚至RedBlack树？），但他们的更快的（不其复杂性回报）？

I know that performance never is black and white, often one implementation is faster in case X and slower in case Y, etc. but in general - are B-trees faster then AVL or RedBlack-Trees? They are considerably more complex to implement then AVL trees (and maybe even RedBlack-trees?), but are they faster (does their complexity pay off) ?

编辑：我还要补充一点，如果他们更快则相当于AVL / RedBlack树（按节点/含量） - 为什么的是他们更快？

I should also like to add that if they are faster then the equivalent AVL/RedBlack tree (in terms of nodes/content) - why are they faster?

推荐答案

肖恩的岗位（目前公认的一种）是完全的无稽之谈。对不起肖恩，我没有冒犯;我希望我能说服你，我的发言是基于事实。

Sean's post (the currently accepted one) is full of nonsense. Sorry Sean, I don't mean to be rude; I hope I can convince you that my statement is based in fact.

他们在其使用情况完全不同，所以它不可能做一个对比。

They're totally different in their use cases, so it's not possible to make a comparison.

他们都用于维护一组全序项目进行快速查找，插入和删除。它们具有相同的接口和相同的意向。

They're both used for maintaining a set of totally ordered items with fast lookup, insertion and deletion. They have the same interface and the same intention.

RB树一般在内存中的结构用于提供快速访问（最好是O（logN）的）数据。 [...]

RB trees are typically in-memory structures used to provide fast access (ideally O(logN)) to data. [...]

总是的O（log n）的

always O(log n)

B树通常磁盘为基础的结构，因此本身就比存储器内数据更慢。

B-trees are typically disk-based structures, and so are inherently slower than in-memory data.

废话。当存储在磁盘上查找树，通常使用B树。这是非常真实的。当存储在磁盘上的数据，它的速度慢于内存中的数据访问。但是，存储在磁盘上红黑树的也的比存储在内存中的红黑树要慢。

Nonsense. When you store search trees on disk, you typically use B-trees. That much is true. When you store data on disk, it's slower to access than data in memory. But a red-black tree stored on disk is also slower than a red-black tree stored in memory.

你比较苹果和桔子在这里。什么是真正有趣的是在内存中的B树和红黑树在内存中的比较。

You're comparing apples and oranges here. What is really interesting is a comparison of in-memory B-trees and in-memory red-black trees.

[作为题外话：B树，而不是红黑树，是在I / O模型理论上高效。我已经实验测试（和验证）的I / O模型进行排序;我希望它的B树以及工作。]

[As an aside: B-trees, as opposed to red-black trees, are theoretically efficient in the I/O-model. I have experimentally tested (and validated) the I/O-model for sorting; I'd expect it to work for B-trees as well.]

B树很少二叉树，孩子的节点可以具有的数量通常是一个大数。

B-trees are rarely binary trees, the number of children a node can have is typically a large number.

需要明确的是，B树节点的尺寸范围是树的参数（在C ++中，您可能需要使用一个整数值作为模板参数）。

To be clear, the size range of B-tree nodes is a parameter of the tree (in C++, you may want to use an integer value as a template parameter).

B树结构的管理是相当复杂的，当数据发生变化。

The management of the B-tree structure can be quite complicated when the data changes.

我记得他们是非常简单的了解（和实施），比红黑树。

I remember them to be much simpler to understand (and implement) than red-black trees.

B树尽量减少磁盘的访问次数，使得数据检索是合理确定性

B-tree try to minimize the number of disk accesses so that data retrieval is reasonably deterministic.

这是非常真实的。

这并不罕见必要像4 B-tree访问查找在很数据库中的数据位。

It's not uncommon to see something like 4 B-tree access necessary to lookup a bit of data in a very database.

得到的数据？

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

In most cases I'd say that in-memory RB trees are faster.

得到的数据？

由于查找是二进制的它很容易找到的东西。 B树可以每个节点有多个孩子，所以每个节点上，你必须扫描节点来寻找合适的孩子。这是一个O（N）操作。

Because the lookup is binary it's very easy to find something. B-tree can have multiple children per node, so on each node you have to scan the node to look for the appropriate child. This is an O(N) operation.

每个节点的大小是固定的参数，所以即使你做线性扫描，这是O（1）。如果我们大哦，在每个节点的大小，请注意您通常保持数组排序所以它的O（log n）的。

The size of each node is a fixed parameter, so even if you do a linear scan, it's O(1). If we big-oh over the size of each node, note that you typically keep the array sorted so it's O(log n).

在一个RB树它会为O（logN）的，因为你正在做一比较，然后跳转。

On a RB-tree it'd be O(logN) since you're doing one comparison and then branching.

你比较苹果和桔子。将O（log n）的是，因为树的高度是至多为O（log n）的，正如它为B-树

You're comparing apples and oranges. The O(log n) is because the height of the tree is at most O(log n), just as it is for a B-tree.

此外，除非你玩肮脏分配把戏与红黑树，它似乎是合理的推测，B-树有更好的缓存行为（它访问数组，而不是到处散落的所有指针，并有少分配开销增加内存局部性甚至更多），这可能会帮助它在速度竞赛。

Also, unless you play nasty allocation tricks with the red-black trees, it seems reasonable to conjecture that B-trees have better caching behavior (it accesses an array, not pointers strewn about all over the place, and has less allocation overhead increasing memory locality even more), which might help it in the speed race.

我可以指向实验证据表明，B树（与尺寸参数32和64，特别是）与红黑树为小尺寸的竞争非常激烈，而且比它倒手，即使中等大小的n值。请参阅http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

I can point to experimental evidence that B-trees (with size parameters 32 and 64, specifically) are very competitive with red-black trees for small sizes, and outperforms it hands down for even moderately large values of n. See http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

B树更快。为什么？我猜想，这是由于内存位置，更好的缓存行为和更少的指针追逐（这是，如果不是同样的东西，重叠在一定程度上）。

B-trees are faster. Why? I conjecture that it's due to memory locality, better caching behavior and less pointer chasing (which are, if not the same things, overlapping to some degree).