c - C 中大磁盘文件的二进制搜索 - 问题

Question

这个问题在 StackOverflow 上经常出现，但我已经阅读了所有以前的相关答案，并且对这个问题有轻微的扭曲。

我有一个 23Gb 的文件，其中包含 4.75 亿行大小相等的行，每行由一个 40 个字符的哈希码和一个标识符(一个整数)组成。

我有一个传入的哈希码流 - 总共有数十亿个 - 对于每个传入的哈希码，我需要找到它并打印出相应的标识符。这项工作虽然很大，但只需要完成一次。

文件太大，我无法读入内存，所以我一直在尝试通过以下方式使用 emmap:

codes = (char *) mmap(0,statbuf.st_size,PROT_READ,MAP_SHARED,codefile,0); 

然后我只是根据代码中的地址使用地址算法进行二进制搜索。

这似乎开始漂亮地工作并在几秒钟内生成几百万个标识符，使用 100% 的 cpu，但在一些看似随机的时间之后它会减慢到爬行。当我使用 ps 查看进程时，它已从使用 100% cpu 的状态“R”变为使用 1% cpu 的状态“D”(磁盘绑定(bind))。

这是不可重复的 - 我可以对相同的数据再次启动该过程，并且它可能会运行 5 秒或 10 秒，然后才会出现“缓慢爬行”。昨晚有一次，在这件事发生之前我有将近一分钟的时间。

一切都是只读的，我没有尝试对文件进行任何写入，并且我已经停止了机器上的所有其他进程(我控制的)。它是现代 Red Hat Enterprise Linux 64 位机器。

有谁知道为什么进程会受磁盘限制以及如何停止它？

更新:

感谢大家的回答和您的想法；我以前没有尝试过所有各种改进，因为我想知道我是否以某种方式错误地使用了 mmap。但答案的要点似乎是，除非我能把所有东西都塞进内存里，否则我将不可避免地遇到问题。因此，我将哈希码的大小压缩为不会创建任何重复项的前导前缀的大小——前 15 个字符就足够了。然后我将生成的文件拉入内存，并分批运行传入的哈希码，每批约 20 亿个。

Answer 1

首先要做的是拆分文件。

用散列码制作一个文件，用整数 ID 制作另一个文件。由于行相同，因此在找到结果后它会很好地排列。您也可以尝试一种将每个第 n 个哈希值放入另一个文件然后存储索引的方法。

例如，每第 1000 个散列键与索引一起放入一个新文件中，然后将其加载到内存中。然后二进制扫描它。这将告诉您需要在文件中进一步扫描的 1000 个条目的范围。是的，那会很好!但可能远不止于此。大概每 20 条记录就会将文件大小除以 20 + - 如果我觉得不错的话。

换句话说，扫描后您只需要触摸磁盘上几千字节的文件。

另一种选择是将文件拆分并放在多台机器的内存中。然后只需二进制扫描每个文件。这将在零磁盘访问的情况下产生绝对最快的搜索...