C++ 二进制文件 I/O 操作变慢...数据库如何处理二进制文件？

Question

我正在尝试制作一个简单的基于文件的哈希 table。这是我的 insert 成员函数：

private: std::fstream f;  // std::ios::in | std::ios::out | std::ios::binary

public: void insert(const char* this_key, long this_value) {
    char* that_key;
    long that_value;
    long this_hash = std::hash<std::string>{}(this_key) % M;
    long that_hash;  // also block status

    long block = this_hash;
    long offset = block * BLOCK_SIZE;
    while (true) {
        this->f.seekg(offset);
        this->f.read((char*) &that_hash, sizeof(long));
        if (that_hash > -1) {  // -1 (by default) indicates a never allocated block
            this->f.read(that_key, BLOCK_SIZE);
            if (strcmp(this_key, that_key) == 0) {
                this->f.seekp(this->f.tellg());
                this->f.write((char*) &this_value, sizeof(long));
                break;
            } else {
                block = (block + 1) % M;  // linear probing
                offset = block * BLOCK_SIZE;
                continue;
            }
        } else {
            this->f.seekp(offset);
            this->f.write((char*) &this_hash, sizeof(long));  // as block status
            this->f.write(this_key, KEY_SIZE);
            this->f.write((char*) &this_value, sizeof(long));
            break;
        }
    }
}

50,000,017 个块的 10M 键值对测试已经完成。（二进制文件大小约为 3.8GB）。

但是，使用 50M 密钥和 250,000,013 个块进行的测试速度极慢...（在这种情况下，二进制文件大小超过 19GB）。 1,000 inserts 通常需要 4~5ms，但例外情况下需要超过 2,000ms。它变得越来越慢，然后需要 40 ~ 150 毫秒......（x10 ~ x30 慢......）我完全不知道......

是什么原因导致这个特殊的二进制文件 I/O 变慢？
seekg&seekp 和其他 I/O 操作是否受文件大小影响？（虽然我找不到关于这个问题的任何参考资料......）
键、值存储和数据库如何避免这种I/O变慢？
我该如何解决这个问题？

Answer 1

数据大小

通常磁盘驱动器块大小是 2 的幂，所以如果您的数据块大小也是 2 的幂，那么您基本上可以消除数据块跨越磁盘块边界的情况。

在您的情况下，64 字节的值（如果您真的不需要存储哈希，则为 32 字节）可能会稍微好一点。

插入顺序

你可以做的另一件事来提高性能是做你的插入增加散列顺序以减少必须从磁盘加载数据的次数。

一般在磁盘读取或写入数据时，OS会read/write一次大卡盘（可能是4k）所以如果你的算法是写入数据的一种方式在本地及时，您将减少实际必须读取或写入磁盘的时间数据。

鉴于您进行了大量插入，一种可能性是一次处理 1000 甚至 10000 key/value 对的批量插入。本质上，你会在内存中积累数据并对其进行排序，一旦你有足够的项目（或当你完成插入），你就会按顺序写入数据。

这样，您应该能够减少非常慢的磁盘访问。如果您使用传统硬盘驱动器，这可能更为重要，因为磁头移动速度很慢（在这种情况下，对其进行碎片整理可能会有用）。另外，请确保您的硬盘有足够的可用空间 space。

在某些情况下，本地缓存（在您的应用程序中）也可能会有帮助，特别是如果您了解数据的使用方式。

文件大小 VS 冲突

当您使用散列时，您希望找到文件大小和冲突之间的平衡点。如果你有太多的碰撞，那么你会浪费很多时间，并且在某个时候它可能会退化，因为几乎每次插入都很难找到一个空闲的地方。

另一方面，如果你的文件真的非常大，你可能会遇到这样一种情况，你可能会用主要是空的数据填充你的 RAM，并且仍然需要用磁盘中的数据替换数据几乎所有插入。

例如，如果您的数据是 20GB，并且您能够在内存中加载 2GB，那么如果插入真的是随机的，那么 90% 的时间您可能需要真正访问硬盘。

配置

好吧选项将取决于 OS 并且它超出了编程论坛的范围。如果你想优化你的电脑，那么你应该看看别处。

阅读

阅读操作系统（文件系统、缓存层……）和算法（外部排序算法、B-Tree 和其他结构）可能有助于更好地理解。

备选方案

额外的内存
高速固态硬盘
多线程（例如输入和输出线程）
重写算法（例如一次 read/write 整个磁盘页面）
更快CPU / 64 位计算机
使用专为此类场景设计的算法。
正在使用数据库。
分析代码
调整参数

C++ 二进制文件 I/O 操作变慢...数据库如何处理二进制文件？

C++ Binary File I/O Operations Slow Down... How DB Handle Binary Files?

c++

fstream

binaryfiles

c++-ios