面试题：C语言中B+树节点的内存分配与释放

Question

在C语言实现B+树时，简述如何合理分配和释放B+树节点的内存。假设B+树节点结构已定义，包含数据项和指针，详细描述内存分配函数和释放函数的实现思路，并写出关键代码片段。

Answer 1

内存分配函数实现思路

1. 确定节点大小：根据B+树节点结构，计算出一个节点所需的内存大小，包括数据项和指针占用的空间。
2. 调用内存分配函数：使用C语言的标准内存分配函数malloc或calloc来分配所需大小的内存空间。
3. 初始化节点：分配内存成功后，对节点的各个成员进行初始化，例如设置数据项数量为0，指针初始化为NULL等。

关键代码片段 - 内存分配函数

#include <stdlib.h>

// 假设已定义B+树节点结构
typedef struct BPlusTreeNode {
    int *data; // 数据项数组
    struct BPlusTreeNode **children; // 指针数组
    int count; // 当前数据项数量
    int isLeaf; // 是否为叶子节点
} BPlusTreeNode;

// 内存分配函数
BPlusTreeNode* createBPlusTreeNode(int order) {
    BPlusTreeNode *newNode = (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode));
    if (newNode == NULL) {
        return NULL;
    }
    newNode->data = (int*)malloc((order - 1) * sizeof(int));
    if (newNode->data == NULL) {
        free(newNode);
        return NULL;
    }
    newNode->children = (BPlusTreeNode**)malloc(order * sizeof(BPlusTreeNode*));
    if (newNode->children == NULL) {
        free(newNode->data);
        free(newNode);
        return NULL;
    }
    newNode->count = 0;
    newNode->isLeaf = 1;
    for (int i = 0; i < order; i++) {
        newNode->children[i] = NULL;
    }
    return newNode;
}

内存释放函数实现思路

1. 释放子节点内存：如果节点不是叶子节点，递归调用释放函数来释放其所有子节点的内存。
2. 释放数据项内存：释放节点中数据项数组占用的内存。
3. 释放指针数组内存：释放节点中指针数组占用的内存。
4. 释放节点自身内存：最后释放节点结构体本身占用的内存。

关键代码片段 - 内存释放函数

// 内存释放函数
void freeBPlusTreeNode(BPlusTreeNode *node, int order) {
    if (node == NULL) {
        return;
    }
    if (!node->isLeaf) {
        for (int i = 0; i <= node->count; i++) {
            freeBPlusTreeNode(node->children[i], order);
        }
    }
    free(node->data);
    free(node->children);
    free(node);
}