data-structures - 红黑树与B树

我有一个项目，我必须在这个项目上实现对兆字节至TB级数据的快速搜索，插入和删除操作。我最近一直在研究数据结构并对其进行分析。具体来说，我想介绍3个案例，并提出以下问题:

数据远远超出了内存可以处理的范围(10-15 TB的采样范围)。在这种情况下，我会将数据结构存储在磁盘上。

与系统内存相比，数据相对较少，因此可以为提高速度而在内存本身中进行存储和操作。

数据大于可用内存，并假定小于分页文件中可能的连续数据块的大小。因此，我将数据结构存储在磁盘上的文件中，并对该文件进行内存映射。

我得出的结论是:

对于情况1，我应该使用B树来加快访问速度，因为它可以节省磁盘旋转产生的滞后

对于情况2，我应该使用Red Black Tree来加快访问速度，因为数据在内存中，否。如果使用B树，最坏情况下需要扫描的元素数量将少于我要做的

对于情况3，我对此表示怀疑，磁盘上的页面文件使用本机OS I / O对文件进行操作，那么B树是更好的选择还是Red Black树？

我想知道上述三个结论在哪里正确，哪里在哪里错误以及如何在这三种情况下改进性能。

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

更新1::正在阅读stackoverflow中的this帖子。得到了一些真正好的见解，使我感到我在案例中进行的比较类型可能是错误的。链接在投票最多的http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html中发布

最佳答案

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

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

为了回答您的情况，

磁盘延迟在寻道时间和等待磁盘旋转之间大致平均分配。

如果操作正确，则B树应能胜过红黑树(特别是如果节点适合高速缓存行，则B树应更快。)

它不必在页面文件中是连续的。它只需要在进程的虚拟地址空间中是连续的即可。对于理智的OS，它也与情况1几乎相同，除非您的数据足够小以至于大多数情况下它都可以容纳到内存中，并且memcpy开销很大。

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

关于data-structures - 红黑树与B树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6401039/