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

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

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

修改在if当前条目无效的部分。在那种情况下，您必须找出您拥有有效条目的两个端点。 例如，如果中点是 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]。现在算法将决定二进制搜索下半部分或上半部分。