内存映射 - 部分基于磁盘的算法

Question

是否有任何良好的资源或书籍的泄漏数据结构，也就是说，一个队列？

当存储大对象可以装满了所有的记忆，但是如果你能保持，也就是说，该队列结构在内存中的最常用的项目，并在磁盘上其余的（有点像分页）。

同样，这个问题适用于其他结构，诸如链表，数组，哈希表等。

Answer 1

您正在寻找的可能是I/O高效算法的主题。 谷歌搜索没有为我提供任何书籍，但这course page包含文章的列表，这些文章可能与您相关，也可能不相关。

你也应该看看WikiPedia page for B-trees，特别是关于B-trees in filesystems的部分。

Answer 2

还有就是Buffer Tree（PDF，0.6 MB）：

” ......开发出一种高效的外部优先级队列和 配料的（一维）范围树 的动态版本和段树“。

和

” ......让我们来设计从已知的内部算法有效外部存储器算法 以简单的方式， 这样的算法，所有的I/O特定部位是隐藏在数据结构中的“ ”。

它被提及作为更广泛的治疗免费提供的在线 书“Algorithms and Data Structures for External Memory” 由杰弗里·斯科特·维特（PDF，1 MB）的 主题的一部分。

Answer 3

你的意思是找到有效的基于磁盘的类似物的根本基于RAM的数据结构（例如，链表，栈，队列，优先级队列等）？如果是这样，下面的答案可能会有帮助，也可能没有帮助。

---

我不完全确定你要做什么。通过队列，你是指FIFO（先进先出）队列还是优先队列？

对于FIFO队列和日志记录处理，也许你可以看看环缓冲区和日志旋转。

对于缓存的数据存储在RAM处理，以尽量减少磁盘访问，您可能会或可能不会是最好留下操作系统。除非你正在开发一个Windows应用程序，否则只需简单地读取和写入文件和从文件写入文件就可以更好，因为操作系统应该足够好地执行读写缓存。但是，据我所知，Windows有可怕的读/写缓存（我可能是错的）。

也许看着Linux中的VFS子系统和学习http://lxr.linux.no/#linux+v2.6.31/Documentation/filesystems/vfs.txt将有所帮助，因为（我认为）这是处理缓存的Linux的一部分。

我不在队列和缓存方面的专家，但我知道关于它的一些东西。如果你能提供你想要做的更多细节，也许有人可以帮助你磨练正确的解决方案。