Question

在Javascript中，有没有一种方法在文本文件中进行基于磁盘的二分搜索以获取特定键？该文本文件太大，无法加载到内存中，但键值已排序。特别地，我正在寻找一种模仿Perl的Search :: Dict功能的方法。

例如，如果我有一个名为foo.txt的文件：

a 1
b 10
c 5
z 4

look（c，foo.txt） 应通过二进制搜索而不是线性遍历文件，返回行 c 5。

Answer 1

我不懂JavaScript，但如果你可以进行随机搜索，你可以通过搜索到当前块（以字节为单位）的中点，然后向前移动直到消耗掉一个换行符，来进行二分查找，只要你"知道"你的密钥是在换行符上。

有些时候会需要向后移动，因此你可能需要了解文件缓存的知识，以便向后移动不会太耗费资源。

我想如果您不处理ASCII文件的话，可能会更棘手。

Answer 2

不是真的，只有当你能够确定记录开始位置时，二分搜索才是真正可行的。您似乎具有可变长度记录，因此，除非创建一组行起始偏移量的数组，否则它不会起作用。

正如尼克希尔在评论中所指出的那样，一种方法是根据文件大小进行二进制分割，然后找到最接近此处的行开头。这仍然是相对高效的（即比顺序搜索好得多）。