algorithm - 红黑树作用 - 红黑树详解




B树比AVL或RedBlack-Tree更快? (6)

我知道性能永远不会是黑白的,通常一种实现在X情况下更快,在Y情况下更慢,等等。但一般来说 - B树比AVL或RedBlack-Trees快吗? 它们比AVL树(甚至可能是RedBlack-trees?)要复杂得多,但它们更快 (它们的复杂性是否得到回报)?

编辑:我还想补充一点,如果它们比等效的AVL / RedBlack树更快(就节点/内容而言) - 为什么它们更快?


它们是在不同情况下使用的 - 当树节点需要在存储中保持在一起时使用B树 - 通常因为存储是磁盘页面,因此重新平衡可能很昂贵。 如果没有此约束,则使用RB树。 因此,如果要实现(比方说)关系数据库索引,B树可能会更快,而RB树可能会更快(例如)内存搜索。


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

就个人而言,我只是使用标准库中的任何内容来处理我正在使用的语言,因为这对于非常小的性能提升(如果有的话)来说是很多工作。

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


对于某些应用,B树明显快于BST。 您可以在这里找到的树木:

http://freshmeat.net/projects/bps

非常快 它们也比常规BST实现使用更少的内存,因为它们不需要每个节点有2或3个指针的BST基础结构,还有一些额外的字段来保存平衡信息。


此外......红黑树的高度为O(log [2] N),而B树的高度为O(log [q] N),其中ceiling [N] <= q <= N. 因此,如果我们考虑在B树的每个关键数组中进行比较(如上所述固定)那么B树的时间复杂度<=红黑树的时间复杂度。 (单个记录的大小等于块大小的大小)


肖恩的帖子(目前接受的帖子)包含几个不正确的声明。 对不起肖恩,我不是故意粗鲁; 我希望我能说服你,我的陈述是基于事实。

它们的使用情况完全不同,因此不可能进行比较。

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

RB树通常是内存中结构,用于为数据提供快速访问(理想情况下为O(logN))。 [...]

总是 O(log n)

B树通常是基于磁盘的结构,因此本质上比内存数据慢。

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

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

[旁白:B-trees,而不是红黑树,在I / O模型中理论上是有效的。 我已经通过实验测试(并验证了)I / O模型进行排序; 我希望它也适用于B树。]

B树很少是二叉树,节点可以拥有的子节点数通常很大。

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

当数据发生变化时,B树结构的管理会非常复杂。

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

B-tree尝试最小化磁盘访问次数,以便数据检索具有合理的确定性。

那是真的。

在非常数据库中查找一些数据所需的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值也优于它。 见http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

B树更快。 为什么? 我猜想这是由于内存局部性,更好的缓存行为和更少的指针追逐(如果不是相同的东西,在某种程度上重叠)。


谷歌最近发布了他们的STL容器实现,这些容器基于B树。 他们声称,与通过红黑树实现的标准STL容器相比,它们的版本更快,占用的内存更少。 更多细节here





binary-tree