c++ - 如何在c ++中对文件执行二进制搜索而不将其全部读入内存

Question

我需要一种可以通过二进制搜索从文件中特定位置读取数据的方法。

Answer 1

有两种可能的方法可以在不将整个文件读入内存的情况下实现您想要的效果。第一个（可能也是最健壮/便携的）是使用定位 API：

• std::ifstream::tellg()
• std::ifstream::seekg()

使用上述两种std::ifstream类方法，您可以在文件中“导航”，而无需将整个内容读入内存。

第二种方法是简单地将文件“映射”到内存中，mmap()例如可以使用“”来完成。操作系统（及其文件系统驱动程序）将负责分页和读取数据。从您的应用程序的角度来看，就像将整个文件读入内存一样。

其余的取决于文件中的数据类型以及实现二进制搜索的方式。

Answer 2

这实际上取决于文件中的数据格式。要在文件中进行二进制搜索，需要满足以下条件：

• 数据记录需要在磁盘文件中按排序顺序排列。
• 您需要有一个 O(1) 方法来选择文件中的记录。

如果这两个都是真的，那么磁盘上的二进制搜索就像任何其他的二进制搜索一样工作。不同之处在于，当您获取记录进行比较时，您将通过在磁盘文件中寻找记录的正确位置来获取它们，从磁盘加载记录，然后根据您加载的记录进行比较。

如果采用这种方法，您必须非常注意性能。从磁盘中查找和读取的操作比您过去在内存中所做的任何操作都要慢得多。磁盘缓存可以为您提供很大帮助，但无论何时移动磁盘，您都会损失多个数量级的性能。