在未知行长度的大文件上进行二分查找

Question

我正在处理一个非常大的CSV文件。每个文件里有数百万条记录，每条记录都有一个键。这些记录是按照键排序的。我不想在搜索特定数据时遍历整个文件。

我看到过一个解决方案：在Python中读取大文件

但这个方案建议文件中的每一行长度都要相同，而在我的情况下，这个要求不适用。

我考虑过给每一行添加一些填充内容，这样就能保持固定的行长度，但我想知道有没有更好的方法。

我正在使用Python编程。

Answer 1

在提到的问题中，有人说二分查找只能用于固定长度的记录，这个说法是错误的。而且你根本不需要进行搜索，因为你有多个项目要查找。你只需要逐行读取整个文件，建立一个字典，字典的格式是key:offset，也就是每一行的键和它在文件中的位置。然后，对于你要查找的每个项目，直接用os.lseek跳转到对应键的记录位置。

当然，如果你不想一次性读取整个文件，那你就得使用二分查找了。但是如果你可以把建立索引的时间分摊到多个查找上，比如说每天只查找一次，那保存这个索引就会很有用，这样就不需要再进行搜索了。

Answer 2

要解决这个问题，你也可以使用二分查找，不过需要稍微改动一下：

1. 先获取文件的大小。
2. 用 File.seek 方法跳到文件大小的中间位置。
3. 然后寻找第一个换行符，也就是找到一行的结束。
4. 检查这一行的关键字，如果不是你想要的，就更新文件的大小，然后回到第2步。

下面是一个示例代码：

fp = open('your file')
fp.seek(0, 2)
begin = 0
end = fp.tell()

while (begin < end):
    fp.seek((end + begin) / 2, 0)
    fp.readline()
    line_key = get_key(fp.readline())
    if (key == line_key):
        pass # find what you want
    elif (key > line_key):
        begin = fp.tell()
    else:
        end = fp.tell()

这个代码可能有错误，建议你自己验证一下。如果你真的想要最快的方法，也请检查一下性能。

Answer 3

你不需要固定宽度的记录，因为你不必进行基于记录的搜索。相反，你可以进行基于字节的搜索，并确保每次查找时都对齐到关键字。下面是一个（可能有问题的）示例，展示了如何将你链接的解决方案从基于记录的方式修改为基于字节的方式：

bytes = 24935502 # number of entries
for i, search in enumerate(list): # list contains the list of search keys
  left, right = 0, bytes - 1 
  key = None
  while key != search and left <= right:
    mid = (left + right) / 2
    fin.seek(mid)
    # now realign to a record
    if mid:
        fin.readline()
    key, value = map(int, fin.readline().split())
    if search > key:
      left = mid + 1
    else:
      right = mid - 1
  if key != search:
    value = None # for when search key is not found
  search.result = value # store the result of the search