正确的数据结构用于（此特定的）过期缓存？

Question

我需要从一个非常大，高度相互关联的数据集中读取数据，这些数据相当局限，而且读取也相当昂贵。特别：

数据集的大小为2gig-30gigs，因此我必须将文件的各个部分映射到内存中才能读取。与我在算法中所做的其余工作相比，这是非常昂贵的。通过分析，我发现大约60％的时间都花在读取内存上，因此这是开始优化的正确位置。
当处理该数据集的一部分时，我必须遵循其内部的链接（将其想象为类似于链表），尽管不能保证这些读取接近顺序，但它们的位置相当合理。这意味着：
例如，假设我们一次处理2兆的内存。如果您将2兆的数据读取到内存中，则我随后必须进行的读取操作中大约有40％将位于相同的2兆的内存中。大约20％的读取将是其余数据中的纯随机访问，而另外40％的链接很有可能链接回到指向该段的2meg段。

从对问题的了解和剖析中，我相信向程序引入缓存将大有帮助。我想要做的是创建一个缓存，其中包含N个X内存块的N个块（N和X是可配置的，因此我可以对其进行调整），在必须映射另一部分内存之前，我首先要检查它。此外，缓存中存储的内容越长，我们在短期内请求该内存的可能性就越小，因此最早的数据将需要过期。

毕竟，我的问题很简单： 哪种数据结构最适合实现这种性质的缓存？

我需要非常快速的查找以查看给定地址是否在缓存中。对于缓存的每个“未命中”，我都希望使它的最旧成员过期，并添加一个新成员。但是，我计划尝试对其进行调整（通过更改缓存的数量），以使70％或更多的读取被命中。

我当前的想法是使用AVL树（用于搜索/插入/删除的LOG2 n）将是最安全的（不退化的情况）。我的另一个选择是稀疏哈希表，以便在最佳情况下查找将为O（1）。从理论上讲，它可以退化为O（n），但实际上，我可以将碰撞保持在较低水平。这里的问题是查找和删除哈希表中最旧的条目需要多长时间。

是否有人对这里最好的数据结构有什么想法或建议，为什么？

Answer 1