c++ - 索引大型 txt 文件

Question

我有一个大文件(5 亿条记录)。该文件是两列(制表符分隔)如下:

1 4590
3 1390
4 4590
5 4285
7 8902
8 9000
...

第一列中的所有值都按数字顺序排列(但有间隙，例如:1，然后是 3，然后是 4...)。

我想对该文件进行索引，以便能够根据第 1 列的值(我将其称为键)访问第 2 列上的值

例如，如果我提交 8，它应该返回 9000。

我已经开始创建如下索引:

// Record each entry into a structure
struct Record{
  int gi; //first column
  int taxa; //second column
};

Record buffer;
ofstream BinaryFile("large_file_indexed.bin", ios::binary);
ifstream inputFile("infile.dat");

//Write to binary file
 while( inputFile.good() ){                     
        inputFile >> buffer.gi >> buffer.taxa;
        BinaryFile.write(  (char *) &buffer, sizeof(Record)  );    
        }
  BinaryFile.close();

好的，我上面所做的只是为条目创建一个二进制索引文件并将其保存到一个二进制文件中。这按预期工作。

现在问题来了，因为我不是专家，所以我很感激你的建议。思路是读取二进制文件，得到一条特定的记录

//Read binary file
ifstream ReadBinary("large_file_indexed.bin, ios::binary );
int idx = 8 ; // Which key do we search for?
 while(!ReadBinary.eof())
    {
      ReadBinary.read( (char *) &buffer, sizeof(Record));
      if(idx == buffer.gi) // If we find key return corresponding value
        {
          cout << "Found key " << buffer.gi << " Taxa:" << buffer.taxa <<  endl;
          break;
        }
    }

这将返回预期值。由于我们要求与键 8 对应的值，因此它返回 9000。

问题是获取值的时间仍然太长，我想知道如何才能更快。如果我使用 seekg 并可以获得特定索引，但我不知道哪个索引(位置)对应于我们想要的键。所以换句话说我可以直接跳转到关键所在的位置并获取相应的值。我对如何获取特定键的位置并跳转到二进制文件中的相应位置感到困惑。也许我应该以不同的方式索引我的输入文件，或者我遗漏了什么？

感谢您的评论。

Answer 1

如果您不能使用数据库或 B 树库，并且不想投资开发另一个 B 树库，您可以考虑以下两种方法之一。

两者都假定二进制索引文件已排序，并利用固定大小的记录。

1.简单的启发式方法

如果没有间隙，要找到第 n 条记录(从 1 开始编号)，您可以这样做:

if (ReadBinary.seekg(sizeof(Record)*(n-1))
     && ReadBinary.read( (char*)&buffer, sizeof(Record))) {
     // process record 
}
else {
    // record not found (certainly beyond eof)
}

但是你可以有差距。这意味着，如果没有重复项，元素 n 将位于此位置或之前。因此，只要有必要就阅读和倒带:

if (! ReadBinary.seekg(sizeof(Record)*(n-1))) { // try to position 
    ReadBinary.clear(); // if couldn't position
    ReadBinary.seekg(-sizeof(Record), ios_base::end);  // go to last record
}
while (ReadBinary.read( (char*)&buffer, sizeof(Record)) && buffer.gi>n ) {
     ReadBinary.seekg (-2*sizeof(Record), ios_base::cur); 
}
if (ReadBinary && buffer.gi==n) {
        // record found
}
else {
    // record not found
}

2.二分法

当然，如果你有很多差距，这种启发式方法很快就会变得太慢，因为搜索的数量会增加。

因此您可以选择 dichotomic search (又名 binary search ):与 seekg()转到文件末尾并使用 tellg()知道文件的大小，您可以将其转换为记录数。

将数字一分为二，放在中间的记录上，读取它，看搜索到的数字是否小于或大于读取的数字，然后重新开始搜索，直到找到正确的位置.您将使用相同的原则在数组中进行搜索。

这是非常有效的，因为您最多只需要 log(n)/log(2) 次读取就可以找到任何数字。因此，对于 500 000 000 个数字中的任何一个，您最多需要读取 29 次!

3.结论

当然还有其他可行的方法。但最终，这已经相当不错了，即使它会被任何数据库或精心制作的 b-tree 超越。库，因为 B 树通过将节点巧妙地重新组合成 block 来减少磁盘磁头移动，这些 block 被优化为以最小的磁盘开销立即读取。这减少了对 log(n)/log(b) 的磁盘访问次数，其中 b 是 block 中的节点数。例如，如果 b=10，则搜索 500 000 000 个元素最多需要从磁盘读取 9 次。