红黑树与B树

我有一个项目，我必须在数据范围从兆字节到兆字节的范围内实现快速搜索，插入和删除操作。我一直在研究最近的数据结构并分析它们。作为具体的，我想对引进3例，提出问题：红黑树与B树

的数据比什么内存可以一气呵成处理（10-15 TB的样本范围）等等。在这种情况下，我会将数据结构存储在磁盘上。
与系统的内存相比，数据相对较少，因此可以在存储器本身中存储和操作以提高速度。
数据不仅仅是空闲内存，并且假定它小于分页文件中可能的连续数据块的大小。因此我将数据结构存储在磁盘上的一个文件中，并执行文件的内存映射。

我已经得出的结论是：

对于情况1，I应，因为它节省了由磁盘旋转产生滞后使用B树以便更快地访问

对于情况2，I应该使用红色黑色树来更快地访问数据，因为数据在内存中并且没有。在最坏的情况下需要扫描的元素将少于我使用B树时必须要做的一个元素

对于案例3，我对此有疑问，页面文件在磁盘上使用本机OS I/O对文件进行操作，那么B树应该是更好的选择还是红黑树？

我想知道上述三个结论是正确的，哪里出了问题，以及如何在三个不同的情况下改进性能。

我使用的是C++语言，带有一个红黑树和一个B树，两者都是我从头开始设计的。我正在使用Boost库进行文件映射。

更新1 ::通过this通过阅读文章在stackoverflow。得到了一些真正的好的见解，这让我觉得我在案例中所做的比较类型可能是错误的。答案最多的一个链接发布了http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

来源

2011-06-19 swanar

你要做什么样的搜索？按键简单搜索？钥匙是怎么样的？ – svick

你或多或少正确。继续执行，如果遇到问题，请在此处询问。 – nikhil

@svick是的我正在按键进行简单的搜索，以最一般的方式，他们可能是一个谨慎的，或以数字连续的顺序，从1开始的不同的自然数集合表示一个值，如（2^8）-1 – swanar

红色/黑色树或多或少等同于2-3-4树，它只是一种B型树。如果您执行B树节点值的二进制搜索，最差情况下的性能是相同的。

B树的明显缺点是浪费空间，但根据所使用的语言/内存分配器，您可能会发现2-3-4树平均使用的空间少于红黑树。例如，在32位Java中，每个对象大约有8个字节的开销。（这也很大程度上取决于分配器; IIRC phkmalloc向上舍小分配到功率的-2的尺寸）

要回答你的情况下，

磁盘延迟大致均匀寻道时间之间的分裂并等待磁盘旋转。
如果你做得对，B树应该能够胜过红黑树（特别是，如果节点适合缓存线，B树应该更快。）
它不需要在页面文件中连续;它只需要在进程的虚拟地址空间中连续。对于理智的操作系统，它与案例1几乎完全相同，除非数据足够小以至于大部分都适合内存，memcpy开销很大。

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

来源

2011-06-19 15:40:11

非常感谢投入;即使数据集很大，你是否会建议使用2-3-4树？如果节点大小与磁盘中的页面大小相似，不是更好吗？虽然 – swanar

我确实说过“在各种节点尺寸上运行一些基准测试”，但您确实有支持2-3-4树作为红黑树替代品的优势。仅使用B树的优点是可以运行一些基准并根据自己的喜好进行调整。您还可能想要考虑数据局部性（即，如果您的密钥是字符串，则可能希望将这些字符串保留在节点附近）。如果分页速度很慢，那么您肯定希望节点至少与页面大小一样大，但可能会更大（假设您的磁盘没有预读）。然后对于SSD的答案是不同的... –

非常感谢您的帮助！ – swanar

为了理解这些差异，下面2个点读：

1）A“红 - 黑树”是“自动平衡”，“二进制搜索树”，与每个节点标有颜色（ 2）所有“红黑树”均为“二元搜索树”，但所有“二元搜索树”均不是“二元搜索树”红黑树“

来源

2016-03-09 18:28:20

这个解释使得它听起来好像BST和B-Tree一样。比较不在RBT和BST之间，它在RBT和B-Tree之间。 RBT和B-Tree都是BST。 RBT和B-Tree都是平衡的。 –

回答

相关问题