algorithm - 在没有虚拟内存分页的情况下使用 3GB 可用空间访问 30GB 信息？

Question

我有一个简短的问题:

我们如何在没有虚拟内存或压缩的情况下使用 3GB 的可用空间来访问大约 30GB 的数据？这更像是一个数据结构问题。

谢谢

Answer 1

您应该以某种方式模仿分页机制。

一种方法是散列¹。

将所有数据散列到 bin 中，并将这些 bin 存储在磁盘中。在您的主内存 (RAM) 中，您将只保存一个指向磁盘的指针数组。一旦你需要一个地址，你就可以通过访问 RAM 并从 hash(address)

位置获取指针来知道它在磁盘上的位置

您当然可以优化它以将一部分数据保留在内存中 - 使用 principle of locality - 并希望获得命中 - 并避免从磁盘重新加载 block 。

---

(1) 散列不必复杂或均匀分布。我相信使用地址的 MSb 会很好 - 并且实际上会更好地模拟分页机制。