快速遍历大型二进制文件的算法

Question

我有一个涉及读取大文件的问题需要解决，并且我大致了解如何处理它，但希望看到可能有更好的方法。

问题如下:我有几个巨大的磁盘文件(每个 64GB)，每个文件都包含 2.5KB 的记录(大约 25,000,000记录总数)。除其他字段外，每条记录还具有时间戳和指示时间戳是否有效的isValid标志。当用户输入时间跨度时，我需要返回时间戳在指定范围内的所有记录。

数据的布局是这样的，对于标记为“有效”的所有记录，时间戳单调增加。无效记录根本不应该被考虑。因此，文件通常如下所示(尽管范围要大得多):

a[0]  = { Time=11, IsValid = true };
a[1]  = { Time=12, IsValid = true };
a[2]  = { Time=13, IsValid = true };
a[3]  = { Time=401, IsValid = false }; // <-- should be ignored
a[4]  = { Time=570, IsValid = false }; // <-- should be ignored
a[5]  = { Time=16, IsValid = true }; 

a[6]  = { Time=23, IsValid = true };  // <-- time-to-index offset changed 
a[7]  = { Time=24, IsValid = true };
a[8]  = { Time=25, IsValid = true };
a[9]  = { Time=26, IsValid = true };

a[10] = { Time=40, IsValid = true };  // <-- time-to-index offset changed 
a[11] = { Time=41, IsValid = true };
a[12] = { Time=700, IsValid = false };  // <-- should be ignored 
a[13] = { Time=43, IsValid = true };

如果时间戳和计数器之间的偏移量是恒定的，则查找第一条记录将是一个 O(1) 操作(我将简单地跳转到索引)。由于事实并非如此，我正在寻找一种不同的方法来(快速)找到此信息。

一种方法可能是修改后的二分搜索，但我不完全确定如何处理更大的无效记录 block 。我想我还可以创建一个“索引”来加快查找速度，但是由于会有很多这样的大文件，并且提取的数据大小将比整个文件小得多，所以我不想遍历这些文件中的每一个，逐条记录，生成索引。我在想二分搜索在构建索引时是否也有帮助。

更不用说我不确定索引的最佳结构是什么。平衡二叉树？

Answer 1

您可以使用修改后的二分搜索。这个想法是进行通常的二分搜索来找出下限和上限，然后返回有效的条目之间的内容。

修改的是当前条目无效的部分。在这种情况下，您必须找出有有效条目的两个端点。 例如，如果中点是 3，

a[0]  = { Time=11, IsValid = true };
a[1]  = { Time=12, IsValid = true };
a[2]  = { Time=401, IsValid = false };
a[3]  = { Time=570, IsValid = false }; // <-- Mid point.
a[4]  = { Time=571, IsValid = false };
a[5]  = { Time=16, IsValid = true }; 
a[6]  = { Time=23, IsValid = true };

在上述情况下，算法将返回两个点 a[1] 和 a[5]。现在算法将决定二分搜索下半部分或上半部分。