问题标签 [disk-based]

我正在运行一些动态编程代码（试图强力反驳 Collat​​z 猜想 =P），并且我正在使用 dict 来存储我已经计算过的链的长度。显然，它在某个时候耗尽了内存。有没有什么简单的方法可以使用 a 的某些变体，dict当它用完空间时，它会将自身的一部分分页到磁盘？显然它会比内存中的字典慢，并且最终可能会占用我的硬盘空间，但这可能适用于其他不是那么无用的问题。

我意识到基于磁盘的字典几乎是一个数据库，所以我使用 sqlite3 手动实现了一个，但我没有以任何聪明的方式做到这一点，而是让它一次查找数据库中的每个元素......它慢了大约 300 倍。

创建我自己的一组字典，一次只在内存中保留一个，并以某种有效的方式将它们分页是最聪明的方法吗？

我正在寻找一种用于缓存大量数据的解决方案。

相关问题，但针对不同语言：

• Python 基于磁盘的字典
• 磁盘支持的 STL 容器类？

用不同的术语关闭问题：

• 在 C# 中寻找一个简单的独立持久字典实现

我不需要（或不想为此支付任何费用）持久性、事务、线程安全等，并且想要使用不比 List<> 或 Dictionary<> 复杂得多的东西。

如果我必须编写代码，我会将所有内容保存为临时目录中的文件：

在我的情况下，索引将是一个int（并且它们应该是连续的或足够接近）并且数据将是一个string，因此我可以摆脱同时处理POD并且宁愿超轻并做到这一点。

用法是我有一个 3k 文件序列（如文件 #1 到 #3000），总计 650MB，需要为序列中的每个步骤做一个差异。我希望总数大致相同或更多，我不想将所有这些都保存在内存中（更大的情况可能会出现在我无法做到的情况下）。

许多人为我的问题提出了不同的解决方案。然而，似乎没有一个针对我的小利基。我正在查看磁盘支持缓存的原因是因为我预计我当前的使用将占用我可用地址空间的 1/3 到 1/2。我担心更大的箱子会完全耗尽空间。我不担心踩踏、持久性或复制。我正在寻找的是使用最少代码、最少占用空间、最少内存开销和最低复杂性的最小解决方案。

我开始认为我过于乐观了。

我偶然发现了 WB on-disk B-tree library：

http://people.csail.mit.edu/jaffer/WB

它似乎对我的目的很有用（在不适合内存的非常大的统计计算期间将数据交换到磁盘），但我想知道它有多稳定。阅读手册，它似乎令人担忧地“研究” - 有些部分标记为 [未实施] 等。但也许手册已经过时了。

那么，这个库有用吗？我最好看看 Tokyo Cabinet、MemcacheDB 等吗？

顺便说一句，我正在使用 Java。

我需要存储一个大哈希集，最多可以包含大约 2 亿个 40 位值。将其存储为 2 亿个 64 位值是可以接受的（尽管有 2 亿 * 16 位丢失）。

要求是：

• 很小的内存占用（磁盘空间不是问题，内存是）

• 快速contains(long l)和add(long l)方法（比 SQL 快得多）

• 嵌入式

• 免费且没有令人讨厌的许可（没有 Berkeley DB）。LGPL 很好。

• 没有误报也没有误报，所以像基于磁盘的布隆过滤器之类的东西不是我想要的

SQL不是我在这里所追求的。

因为我真的认为我更喜欢这样的快速（注意解决方案比 SQL 解决方案快得多）：

基于磁盘的快速哈希表？

Google 有这样的 Java API 吗？

我只使用“键”的快速基于磁盘的键/值对实现会起作用吗？

或者是其他东西？

我宁愿不重新发明轮毂。

是否存在具有以下特性的基于文件系统的键值存储的有效 Java 实现：

1. 通过唯一 ID 存储、覆盖和检索字节数组（可能由存储分配）
2. 没有内存缓存（读取意味着从文件系统读取，写入意味着立即写入文件系统）
3. 总数据大小高达几 TB
4. 存储对象数量高达数亿
5. 可管理数量的文件系统对象（在文件系统级别移动/复制/删除整个存储）

Berkeley DB JE 会这样做吗？