data-structures - 紅黑樹 - 黑白树




红黑树与B树 (2)

我有一个项目,我必须在从兆字节到太字节的数据上实现快速搜索,插入和删除操作。 我最近一直在研究数据结构并对其进行分析。 具体而言,我想介绍3个案例并就此提出问题:

  1. 这些数据远远超过了内存可以处理的内容(样本范围为10-15太字节)。 在这种情况下,我会将数据结构存储在磁盘上。

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

  3. 数据不仅仅是空闲内存,并且假设它小于页面文件中可能连续数据块的大小。 因此,我将数据结构存储在磁盘上的文件中,并对文件进行内存映射。

我得出的结论是:

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

对于案例2,我应该使用红黑树来加快访问速度,因为数据存储在内存中,没有。 如果我使用B树,那么在更糟糕的情况下需要扫描的元素将少于我必须做的一个

对于案例3,我怀疑这个,页面文件在磁盘上使用本机OS I / O来操作文件,那么B Tree应该是更好的选择还是红黑树?

我想知道上述三个结论的正确位置和出错的地方,以及如何在三个不同的案例中改进绩效。

我使用的是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的幂级。)

要回答你的案件,

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

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


要了解这些之间的差异,请阅读以下2点:

1)“红黑树”是“自我平衡”“二进制搜索树”,每个节点都标有颜色(红色或黑色),并在其上定义了额外的操作以保持“平衡”

2)所有“红黑树”都是“二进制搜索树”,但所有“二进制搜索树”都不是“红黑树”







large-data