小编swa*_*nar的帖子

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

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

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

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

我得出的结论是:

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

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

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

我想知道上述三个结论在哪里正确,哪里出错,以及如何在三个不同的案例中改进绩效.

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

Update 1 ::正在阅读stackoverflow中的这篇文章.得到了一些真正好的见解,让我觉得我在案例中所做的比较类型可能有问题.最受欢迎的答案中发布了一个链接http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html