algorithm - B-tree 比 AVL 或 Red Black-Tree 更快？

Question

<分区>

Answer 1

Sean 的帖子(目前被接受的帖子)包含几个不正确的声明。对不起肖恩，我不是有意无礼；我希望我能让你相信我的陈述是基于事实的。

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

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

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

总是 O(log n)

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

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

您在这里比较苹果和橘子。真正有趣的是内存中 B 树和内存中红黑树的比较。

[顺便说一句:与红黑树相反，B 树在 I/O 模型中在理论上是高效的。我已经通过实验测试(并验证)了用于排序的 I/O 模型；我希望它也适用于 B 树。]

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

需要说明的是，B树节点的大小范围是树的一个参数(在C++中，您可能希望使用整数值作为模板参数)。

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

我记得它们比红黑树更容易理解(和实现)。

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

这是真的。

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

有数据吗？

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

有数据吗？

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)。如果我们对每个节点的大小进行 big-oh，请注意您通常会保持数组排序，因此它是 O(log n)。

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 树一样。

此外，除非你对红黑树玩一些讨厌的分配技巧，否则推测 B 树具有更好的缓存行为似乎是合理的(它访问一个数组，而不是散布在各处的指针，并且分配更少开销甚至更多地增加内存局部性)，这可能有助于它在速度竞赛中。

我可以指出实验证据表明 B 树(大小参数具体为 32 和 64)在小尺寸方面与红黑树非常有竞争力，甚至在 n 值适中时也优于红黑树。参见 http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

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