data-structures - 红黑树与B树

Question

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

1. 数据远远超出内存一次性处理的能力(样本范围为 10-15 TB)。在本例中，我会将数据结构存储在磁盘上。

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

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

我得出的结论是:

对于情况 1，我应该使用 B 树来实现更快的访问，因为它可以节省磁盘旋转产生的延迟

对于情况 2，我应该使用红黑树来加快访问速度，因为数据位于内存中，而不是内存中。在最坏的情况下需要扫描的元素数量将少于我使用 B 树时必须扫描的元素数量

对于情况3，我对此表示怀疑，页面文件位于磁盘上，使用 native 操作系统I/O来操作文件，所以B树是更好的选择还是红黑树？

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

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

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

Answer 1

红/黑树或多或少相当于2-3-4树，它只是B树的一种。只要您对 B 树节点值进行二分搜索，最坏情况下的性能是相同的。

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

为了回答您的案例，

1. 磁盘延迟大致均匀地分布在寻道时间和等待磁盘旋转之间。
2. 如果操作正确，B 树应该能够胜过红黑树(特别是，如果节点适合缓存行，B 树应该更快。)
3. 它不需要在页面文件中连续；它只需要在进程的虚拟地址空间中是连续的。对于正常的操作系统，它也与情况 1 几乎相同，除非您的数据足够小，几乎可以放入内存并且 memcpy 开销很大。

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