2

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

问题如下：我有几个巨大的磁盘文件（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)操作（我会简单地跳转到索引）。既然不是，我正在寻找一种不同的方法来（快速）找到这些信息。

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

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

4

4 回答 4

2

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

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

于 2012-09-27T12:31:28.477 回答
1

您可能会在二进制搜索中带来一些随机性。实际上，随机算法对于大型数据集表现良好。

于 2012-09-27T12:20:51.180 回答
1

在这种情况下，使用别人的数据库代码开始看起来是个好主意，

无论如何，您需要摸索直到找到有效数据的开头，然后再阅读直到结束，

首先进行射击并相应地移动标记，与正常的二分搜索相同，除非您遇到无效记录 开始搜索有效记录 只需从猜测中向前读取就可以了

可能值得对文件运行维护任务以用有效时间戳替换无效时间戳，或者维护外部索引，

于 2012-09-27T12:00:37.330 回答
1

听起来确实像修改后的二进制搜索可能是一个很好的解决方案。如果大块无效记录是一个问题，您可以通过跳过大小呈指数增长的块来处理它们，例如 1,2,4,8,.... 如果这使您超出当前括号的末尾，请退回到括号的末尾并以 1,2,4,8,... 的步长向后跳，以找到合理靠近中心的有效记录。

于 2012-09-27T12:31:38.237 回答