如何在C语言内存映射文件区域中初始化B树节点？

假设我有一个内存中的B树（非B+树），其节点声明如下：

struct node
{
    int* keys;
    struct node** children;
    int currentNumOfKeys;
    char isLeaf;
};

我了解到使用**mmap()**可将内存区域映射到文件存储数据，实现持久化，下次启动程序时指针依然有效——只要将文件映射到相同起始地址，或使用相对偏移指针！

现在我想利用这一特性，如何在映射区域内初始化结构体对象？
通常使用struct node* root = (struct node*)malloc( sizeof(struct node) );会得到操作系统分配的任意内存地址。

我希望实现以下需求：

1. 在映射区域中初始化树的第一个节点
2. 将struct node** children改为int children[MAX_DEGREE]，以便存储子节点相对于根节点的偏移量
3. 以某种方式在映射区域中初始化并存储后续节点，使得下次程序启动时，映射该文件即可重建树，无需重新排序

• 所有步骤中，除了映射文件本身，要避免使用交换文件弥补内存不足，或进行任何形式的磁盘数据复制。
• 我会将struct node** children改为类似int children[MAX_DEGREE]的形式，存储每个子节点相对于根节点的相对偏移量。

已编辑问题，聚焦单个核心问题

1. 准备映射文件与内存区域 #

首先创建/打开用于存储B树的文件，用mmap()将其映射到进程内存。需预先规划文件大小（或按需扩展），确保能容纳所有节点数据。示例代码：

#include <fcntl.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
#include <cstring>

#define MAX_DEGREE 3
// 调整后的节点大小：固定数组存储键 + 子节点偏移数组 + 键数量 + 叶子标记
#define NODE_SIZE sizeof(struct node)

// 调整后的节点结构：用固定数组替代指针，避免内存地址依赖
struct node {
    int keys[MAX_DEGREE - 1]; // B树节点键数量上限为2t-1，MAX_DEGREE对应2t
    int children[MAX_DEGREE]; // 存储相对于映射区域起始地址的字节偏移，0表示无对应子节点
    int currentNumOfKeys;
    char isLeaf;
};

// 映射区域元数据：记录下一个可用节点的偏移、映射总大小等
struct btree_meta {
    int next_free_offset; // 相对于节点区域起始地址的字节偏移
    long long total_nodes; // 当前可容纳的节点总数
};

int main() {
    const char* file_path = "btree_storage.dat";
    int fd = open(file_path, O_RDWR | O_CREAT, 0644);
    if (fd == -1) { /* 错误处理：perror后退出 */ }

    struct stat sb;
    fstat(fd, &sb);
    off_t map_size;
    void* map_base;
    struct btree_meta* meta;
    struct node* nodes_base;

    if (sb.st_size == 0) {
        // 首次创建文件：分配元数据 + 100个节点的初始空间
        map_size = sizeof(struct btree_meta) + 100 * NODE_SIZE;
        ftruncate(fd, map_size);
        map_base = mmap(NULL, map_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
        if (map_base == MAP_FAILED) { /* 错误处理 */ }

        meta = (struct btree_meta*)map_base;
        nodes_base = (struct node*)((char*)map_base + sizeof(struct btree_meta));
        // 初始化元数据：根节点用第一个位置，下一个可用节点偏移为NODE_SIZE
        meta->next_free_offset = NODE_SIZE;
        meta->total_nodes = 100;

        // 初始化根节点
        struct node* root = nodes_base;
        root->currentNumOfKeys = 0;
        root->isLeaf = 1;
        memset(root->keys, 0, sizeof(root->keys));
        memset(root->children, 0, sizeof(root->children));
    } else {
        // 加载已有文件
        map_size = sb.st_size;
        map_base = mmap(NULL, map_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
        if (map_base == MAP_FAILED) { /* 错误处理 */ }

        meta = (struct btree_meta*)map_base;
        nodes_base = (struct node*)((char*)map_base + sizeof(struct btree_meta));
    }

2. 在映射区域内分配新节点 #

通过元数据记录的next_free_offset定位空闲节点，空间不足时扩展文件与映射区域：

// 分配新节点的工具函数
    struct node* allocate_node() {
        // 检查剩余空间是否足够
        if (meta->next_free_offset + NODE_SIZE > map_size - sizeof(struct btree_meta)) {
            // 扩展文件大小：翻倍扩容
            off_t new_map_size = map_size * 2;
            if (ftruncate(fd, new_map_size) == -1) { /* 错误处理 */ }
            // 重新映射内存区域
            map_base = mremap(map_base, map_size, new_map_size, MREMAP_MAYMOVE);
            if (map_base == MAP_FAILED) { /* 错误处理 */ }
            // 更新指针与元数据
            meta = (struct btree_meta*)map_base;
            nodes_base = (struct node*)((char*)map_base + sizeof(struct btree_meta));
            meta->total_nodes *= 2;
            map_size = new_map_size;
        }

        // 定位并初始化新节点
        struct node* new_node = (struct node*)((char*)nodes_base + meta->next_free_offset);
        new_node->currentNumOfKeys = 0;
        new_node->isLeaf = 1;
        memset(new_node->keys, 0, sizeof(new_node->keys));
        memset(new_node->children, 0, sizeof(new_node->children));

        // 更新元数据：移动到下一个空闲位置
        meta->next_free_offset += NODE_SIZE;
        return new_node;
    }

3. 使用相对偏移关联节点 #

子节点的偏移量通过节点地址与区域起始地址的差值计算，存储到children数组中，重启后可通过偏移量找回节点：

// 示例：给根节点添加子节点
    struct node* child = allocate_node();
    // 计算子节点相对于nodes_base的字节偏移
    int child_offset = (char*)child - (char*)nodes_base;
    nodes_base->children[0] = child_offset;

    // 重启后通过偏移量找回子节点
    struct node* retrieved_child = (struct node*)((char*)nodes_base + nodes_base->children[0]);

4. 程序退出与重新加载 #

使用MAP_SHARED模式时，内存修改会自动同步到磁盘，退出前无需额外写入操作。下次启动时，直接打开文件并映射，读取元数据与根节点即可重建B树：

// 退出前的清理：解除映射
    munmap(map_base, map_size);
    close(fd);
    return 0;
}

核心要点 #

• 所有节点必须从映射区域内分配，绝对不能使用malloc/free，避免引入外部内存地址。
• 偏移量基于节点区域起始地址计算，而非绝对内存地址，确保重启映射后地址有效性。
• 扩展空间时使用ftruncate+mremap，避免磁盘数据复制，符合需求限制。

内容的提问来源于stack exchange，提问作者Shahaboddin