红黑树 VS B 树

Question

51

我有一个项目需要处理从几兆字节到几太字节的数据，需要实现快速的搜索、插入和删除操作。最近我一直在研究数据结构并对它们进行分析。具体来说，我想介绍3种情况，并就此提出问题:

我的结论是：

对于第1种情况，应使用B树以加快访问速度，因为它可以节省磁盘旋转产生的延迟。

对于第2种情况，应使用红黑树以加快访问速度，因为数据位于内存中，需要扫描的元素数目在最坏情况下比使用B树时要少。

对于第3种情况，我不确定，分页文件位于磁盘上，使用本机操作系统I/O来操作文件，所以在这种情况下，是B树还是红黑树更好呢?

我想知道上述三个结论的优缺点，并如何在这三种不同情况下提高性能。

我正在使用C++语言，使用自己从头开始设计的红黑树和B树。我使用Boost库进行文件映射。

更新1：正在阅读stackoverflow中的这篇文章。在其中获得了一些非常有价值的见解，让我感觉我在比较方面所做的工作可能存在问题。最受欢迎答案中发布了一个链接，http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

- swanar

2

你要进行什么样的搜索？是通过关键字进行简单搜索吗？那这个关键字长什么样子？ - svick

你的理解基本上是正确的。继续实现，如果遇到问题在这里问。 - nikhil

@svick 是的，我正在按键进行简单搜索，最常见的方式是，它们可以是离散的，或者是数值连续的一组不同的自然数，从1开始到像（2^8）-1这样的值。 - swanar

2个回答

1

Robert Sedgewick的实验数据（可在网上免费获取）显示，红色容量不断向黑树移动，并交换到黑树顶部，其二次成本与其他树算法相同。

红黑树算法遭受全局红色瀑布（红色喷泉）的影响。

B树和红黑树具有相同的基本二次交换成本，这与非常简单的静态列表排序完全相同。

为了可视化不可见的隐藏熵流，您必须将所有内容解释为广义的红-绿-黑树。 6-B树（或更大）中的每个分支都是这样分解的。

所有额外的容量必须被解释为绿色。中央节点必须是黑色的，最外层的节点必须被染成红色。

中央黑色节点是不变的支持（骨干），除非明确需要，否则不得触摸。最外层的红色节点必须为空，因为它们是主要的交换通道。

红色卡诺通道必须始终大于绿色通道；绿色通道超过1/2会使任何交换都不可能。

因为这是一个抽象的熵流，所以您必须忽略个别排列，并仅提取容量流；能量透明地通过随机粒子流动。

由于绿色容量凝结到根部，红色容量不断被绿色边界向上推到树顶，这就是全局红色瀑布。

B树换出通道是倒置的。您必须从顶部到根部递归地合并分裂2个垂直黑行以生成基本的Carnot换出流。对黑节点运动的强限制增加了额外的冗余红色运动成本。如果您尝试优化一个子系统，则熵成本自然流向另一个子系统。

二叉树的平方交换成本与交换抽象高度（体积）增长的成本相同，这是一个简单的重力。二叉树的形状与对数牛顿引力可视化完全相同。

如果您有一个非常大的静态列表，则交换成本为0。这样的列表总是与样本空间一样大。压缩大列表始终具有Shannon-Huffman熵成本。这是一个非常简单的隐藏的Carnot I / O成本。

如果将所有桶放在一起，您将获得一个非常简单的静态列表，这被称为Young图。这个静态列表太小了，所以它总是具有不变的交换成本。任何树都是一个非常简单的二维静态列表。压缩二维Young图的高度的成本始终是不变的。

树算法的主要成本并非算法成本（绿色成本）；它们的主要成本是额外的隐藏式 Carnot Swapout I/O，需要在大型列表压缩解压时进行本地完整排序（红色成本）。

- cheeseandtomato

二叉树具有基本的不对称性；因为头部总是较重，它会吸收更多的红色热量。黑色树顶始终保持凉爽，这是一个非常简单的热浴（红色热量吸收器）。 - cheeseandtomato

每个红吸收都向下移动一个黑洞，这将使红容量下降。 - cheeseandtomato

绿色容量必须移动到根，因为6-B-Tree算法尝试自动打包所有内容以压缩成本。此压缩会打包绿色容量并将其移动到根。绿色容量是一个自由粒子;换入成本不昂贵。 - cheeseandtomato

大宽度B树遭受非常简单的Foehn现象。由于交换通道变得越来越窄，它会产生大量的红色压缩。 - cheeseandtomato

这是有史以来最伟大的虚假回复。 - xy2

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

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

- tc. · Accepted Answer

红黑树或多或少等同于2-3-4树，它只是B树的一种类型。在进行B树节点值的二分查找时，最坏情况下的性能是相同的。

B树的明显缺点是浪费空间，但是根据所使用的语言/内存分配器，你可能会发现平均而言，2-3-4树比红黑树占用更少的空间。例如，在32位Java中，每个对象大约有8字节的开销。(这也很大程度上取决于分配器；如果我没记错，phkmalloc会将小的分配舍入为2的幂大小。)

回答你的问题：

磁盘延迟大致平均分配在寻道时间和等待磁盘旋转之间。
如果你做得对（特别是，如果节点适合于缓存行），B树应该能够胜过红黑树。
它不需要在页文件中是连续的；它只需要在进程的虚拟地址空间中是连续的。对于理智的操作系统来说，除非你的数据足够小以至于它基本上可以放入内存并且memcpy开销很大，否则它与第1种情况基本相同。

为了简单起见，我会选择一个B树，并在各种节点大小上运行一些基准测试。