c - 大文件搜索算法

Question

我需要帮助来决定用于搜索大文件的搜索算法。 这就是我在做什么。假设文件包含时间范围 t1 到 t2。 (t2>t1)

我需要获取以下的文件偏移量 (fseek):

1. 大于t1的时间t3

2. 小于时间t2的时间t4

   | ------| ---|----------------|
   
   t1      t3   t4              t2
   

Naive 版本是遍历整个文件的行并在当前时间为 t3 时返回 fseek，从返回的 seek 开始并在当前时间为 t4 时进行迭代，返回第二个 fseek

现在假设文件是​​ 100GB，我需要在文件中迭代以获得 2 秒的周期。 然后这个逻辑变得太昂贵了 CPU 和文件系统。寻找更好的解决方案。使用的语言是C。 行目前是固定大小的，但我想展望 future 并处理一些不使用固定大小长度的算法。

Answer 1

您可以使用 binary search如果文件中的时间都已排序。如果文件中的记录具有固定宽度，那就更好了，但即使它们不是固定宽度，您也可以通过一些工作来使用它。