有没有关于可溢出数据结构的好资源或书籍，比如队列？
存储大型对象时，它可能会填满所有内存，但如果您可以将该队列结构中最常用的项目保留在内存中，其余的则保留在磁盘中（有点像分页）。
同样，这个问题也适用于链表、数组、哈希表等其他结构。
问问题
2242 次
3 回答
10
有缓冲树（PDF，0.6 MB）：
“......开发了一个有效的外部优先级队列和（一维）范围树和段树的批处理动态版本。”
和
“......允许我们以直接的方式从已知的内部算法设计有效的外部存储器算法，这样算法的所有 I/O 特定部分都隐藏在数据结构中。”
它是 Jeffrey Scott Vitter 所著的免费在线书籍“ Algorithms and Data Structures for External Memory ”（PDF，1 MB）中对该主题进行更广泛处理的一部分。
于 2009-10-03T03:53:36.620 回答
1
您正在寻找的可能是 I/O 高效算法的主题。谷歌搜索没有为我找到任何书籍，但此课程页面包含可能与您相关或不相关的文章列表。
您还应该查看B-trees 的 WikiPedia 页面，尤其是有关B-trees in filesystems的部分。
于 2009-10-03T04:10:20.723 回答
0
您的意思是找到与基于 RAM 的基本数据结构（例如，链表、堆栈、队列、优先级队列等）的有效的基于磁盘的类似物吗？如果是这样，下面的答案可能有帮助，也可能没有帮助。
我不完全确定您要做什么。通过队列，您是指 FIFO（先进先出）队列还是优先级队列？
为了处理 FIFO 队列和日志记录，也许您可以查看环形缓冲区和日志轮换。
为了处理在 RAM 中缓存数据以最大程度地减少磁盘访问，您最好将其留给操作系统，也可能不会更好。除非您正在开发 Windows 应用程序，否则最好以简单的方式简单地读写文件，因为操作系统应该足够好地执行读写缓存。然而，据我所知，Windows 有可怕的读/写缓存（我可能错了）。
也许查看 Linux 中的 VFS 子系统并研究http://lxr.linux.no/#linux+v2.6.31/Documentation/filesystems/vfs.txt会有所帮助，因为（我认为）这是 Linux 处理的部分缓存。
我不是队列和缓存方面的专家，但我确实知道一些事情。如果您可以提供有关您正在尝试做的事情的更多详细信息，也许有人可以帮助您磨练正确的解决方案。
于 2009-10-03T03:53:55.607 回答