在文件中存储大量由定界符分隔的整数键值对的最有效方法

Question

我有一个系统，其中两个程序同时读写一个包含大量无符号整数对的文件。键可以有值 [0,2^16)，值可以有值 [0,2^32)。我目前将这些整数作为字符存储在文件中，其中每一对都在自己的行中，键和值由一个空格分隔，所有值都有 10 个字符。

10 个字符的原因有两个：1. 解释为字符的最大无符号整数的长度为 10 个字符，以及 2. 我正在使用 mmap 将文件映射到两个程序的内存中，使用MAP_SHARED 标志。当写入文件的程序第一个运行时，它会线性扫描文件并构建一个哈希映射，将键映射到指向值的指针。当writer要向文件中放入一个新的键值对时，它会在hash map中查找key，如果该key存在，它就会覆盖存储在与该key关联的地址中的值。我确保所有值都在文件中存储为 10 个字符，其中较小的值在右边用空格填充，这样编写者总是可以简单地覆盖该地址处的值，而不必对内存和 munmap 进行一些疯狂的改组并再次 mmap。

但是，将整数作为字符串存储在文件中效率极低，我想知道如何更有效地做三件事：

将整数对存储为整数对而不是字符串。我希望文件尽可能小。
不必在编写程序时使用像hash map这样的额外大数据结构
允许读取程序在 log(n) 时间内搜索和检索键值对，而不是现在正在做的，即线性读取文件以查找匹配的字符串.

一般来说，文件的结构是否可以像数据结构一样通过二进制搜索之类的方法进行排序？如果可以，我该怎么做？

Answer 1

数据存储：我建议您以二进制形式存储数据，这会稍微减小文件大小。保持platform-independence, you should use something like msgpack.

数据访问：我认为mmap()是个好主意（特别是如果你使用像boost memory-mapped file这样的cross-platform解决方案）

Search：因为 mmap()ing 会提供一些指针来处理您的数据，您应该可以使用它作为原始 C-style 数组或将其包装在 array_view and use it with the <algorithm> header 设施中。

Answer 2

我最终实施了一个我一直在寻找的解决方案，它做了以下事情：

键值对以二进制格式存储在文件中，4字节为键，4字节为值。
该文件仅包含键值对，因此该文件只是一个键值对流，没有分隔符或多余的内容。
读写程序都可以在log(n)时间内搜索一个键并检索到对应的值。这是通过将二进制文件重新解释为 8 字节块的数组，将每个 8 字节块重新解释为两个 4 字节块（键和值），并对映射文件执行二进制搜索来实现的。

我想出的代码如下：

struct Pair { uint32_t index[]; };
struct PairArray { uint64_t index[]; };

size_t getFilesize(const char* filename) {
    struct stat st;
    stat(filename, &st);
    return st.st_size;   
}

void binarySearch(const PairArray* const pairArray, 
    uint16_t numElements, uint32_t key, uint32_t*& value) {

    int mid = numElements/2;

    if (numElements == 0) return;

    // interpret the pair as an array of 4 byte key and value
    const Pair* pair = reinterpret_cast<const Pair*>(&(pairArray->index[mid]));

    // new pointer to pass into recursive call
    const PairArray* const newPairArray = reinterpret_cast<const PairArray* const>(
        &(pairArray->index[mid + 1]));

    // if key is found, point pointer passed by reference to value
    if (key == pair->index[0]) {
        value = const_cast<uint32_t*>(&pair->index[1]);
        return;
    } 

    // if search key is less than current key, binary search on left subarray
    else if (key < pair->index[0]) {
        binarySearch(pairArray, mid, key, value);
    } 

    // otherwise, binary search on right subarray
    else (numElements%2 == 0) 
            ? binarySearch(newPairArray, mid - 1, key, value)
            : binarySearch(newPairArray, mid, key, value);
}

int main(int argc, char** argv) {

    ...

    // get size of the file
    size_t filesize = getFilesize(argv[1]);

    // open file
    int fd = open(argv[1], O_RDWR, 0);
    if (fd < 0) {
        std::cerr << "error: file could not be opened" << std::endl;
        exit(EXIT_FAILURE);
    }   

    // execute mmap:
    char* mmappedData = static_cast<char*>(
        mmap(NULL, filesize, PROT_WRITE|PROT_READ, MAP_SHARED, fd, 0));
    if (mmappedData == NULL) {
        std::cerr << "error: could not memory map file" << std::endl;
        exit(EXIT_FAILURE);
    }

    // interpret the memory mapped file as an array of 8 byte pairs
    const PairArray* const pairArray = reinterpret_cast<PairArray*>(mmappedData);

    // spin until file is unlocked, and take lock for yourself
    while(true) {
        int gotLock = flock(fd, LOCK_SH);
        if (gotLock == 0) break;
    }

    // binary search for key value pair
    uint32_t* value = nullptr;
    binarySearch(pairArray, filesize/8, key, value);
    (value == nullptr)
        ? std::cout << "null" << std::endl 
        : std::cout << *value << std::endl;

    // release lock
    flock(fd, LOCK_UN);

    ...

}

在文件中存储大量由定界符分隔的整数键值对的最有效方法

Most efficient way to store a large number of key-value pairs of integers, separated by a delimiter, in a file

c++

file-io

integer

mmap

file