我有一个巨大的文件 (~16TB),其中包含映射到 8 字节值的 8 字节键的列表。(2^40 对,每对 16 个字节)。
我现在想优化该文件,以便可以有效地搜索它。我目前已对文件进行排序并对其执行二进制搜索。这需要 30 次读取才能完成,但这些读取高度分布在文件周围,尤其是在开始时。
我知道我可以将 10 步后剩下的整个二分搜索分区加载到 16GB 内存中,并在那里继续搜索。但是,我的可用内存量可以忽略不计,因此这不是一个选择。
有没有一种方法可以安排磁盘上的数据,以便搜索文件所需的访问从一开始就紧密结合在一起?这将允许我加载需要读入内存的整个“范围”的值,以减少read
总调用次数,并减少随机访问次数。
在初始构建之后,文件永远不会改变,因此插入和删除是不相关的,并且构建任何类型的索引都允许花费很长时间。此外,密钥(大致)均匀分布在 2^64 空间中。