swa*_*nar 37 b-tree red-black-tree large-data data-structures file-mapping
我有一个项目,我必须在从兆字节到太字节的数据上实现快速搜索,插入和删除操作.我最近一直在研究数据结构并对其进行分析.具体而言,我想介绍3个案例并就此提出问题:
数据远远超过内存可以处理的内容(样本范围为10-15太字节).在这种情况下,我会将数据结构存储在磁盘上.
与系统的存储器相比,数据相对较少,因此可以在存储器本身中存储和操作以提高速度.
数据不仅仅是空闲内存,并且假设它小于页面文件中可能连续数据块的大小.因此,我将数据结构存储在磁盘上的文件中,并对文件进行内存映射.
我得出的结论是:
对于情况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
tc.*_*tc. 13
红色/黑色树或多或少等同于2-3-4树,这只是一种B树.如果您对B树节点值进行二进制搜索,则最坏情况下的性能是相同的.
B树的明显缺点是浪费空间,但根据所使用的语言/内存分配器,您可能会发现2-3-4树平均使用的空间比红黑树少.例如,在32位Java中,每个对象大约有8字节的开销.(这也很大程度上取决于分配器; IIRC phkmalloc将小分配用于2的幂级.)
为了回答你的案件,
为简单起见,我将使用B树并在各种节点大小上运行一些基准测试.