面试题：C语言实现B+树的插入优化

常规插入算法性能瓶颈分析

频繁的节点分裂：在B+树插入过程中，当节点已满时会进行节点分裂。每次分裂都需要重新分配内存、调整指针，这涉及较多的I/O操作（如果B+树存储在磁盘上）和内存操作，开销较大。
查找插入位置的开销：为了找到合适的插入位置，需要从根节点开始沿着树的路径进行查找，最坏情况下需要遍历到叶子节点，时间复杂度为O(log n)，n为树中节点数。若树高度较高，此查找过程会消耗较多时间。

优化方案

批量插入优化：先将待插入的键值对收集到一个缓冲区中，当缓冲区满时，再一次性进行插入操作。这样可以减少节点分裂的次数，因为多个插入操作可能可以合并到已有的节点中，避免多次单个插入导致的频繁分裂。
预测性节点分裂：在插入前，预测节点是否可能在插入后导致分裂。如果预测到可能分裂，可以提前进行预分裂操作，减少实际插入时的开销。

C语言代码实现优化后的插入操作（以批量插入为例）

#include <stdio.h>
#include <stdlib.h>

#define ORDER 3 // B+树的阶数

// B+树节点结构
typedef struct BPlusTreeNode {
    int *keys;
    struct BPlusTreeNode **children;
    struct BPlusTreeNode *next;
    int count;
    int isLeaf;
} BPlusTreeNode;

// 创建新的B+树节点
BPlusTreeNode* createNode(int isLeaf) {
    BPlusTreeNode *node = (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode));
    node->keys = (int*)malloc((ORDER - 1) * sizeof(int));
    node->children = (BPlusTreeNode**)malloc(ORDER * sizeof(BPlusTreeNode*));
    node->next = NULL;
    node->count = 0;
    node->isLeaf = isLeaf;
    return node;
}

// 插入键值对到叶子节点
void insertLeaf(BPlusTreeNode *leaf, int key) {
    int i = leaf->count - 1;
    while (i >= 0 && key < leaf->keys[i]) {
        leaf->keys[i + 1] = leaf->keys[i];
        i--;
    }
    leaf->keys[i + 1] = key;
    leaf->count++;
}

// 分裂叶子节点
void splitLeaf(BPlusTreeNode *parent, BPlusTreeNode *leaf) {
    BPlusTreeNode *newLeaf = createNode(1);
    newLeaf->count = ORDER / 2;
    leaf->count = ORDER / 2;
    for (int i = 0; i < ORDER / 2; i++) {
        newLeaf->keys[i] = leaf->keys[ORDER / 2 + i];
    }
    newLeaf->next = leaf->next;
    leaf->next = newLeaf;

    // 将新叶子节点插入到父节点
    int i = parent->count - 1;
    while (i >= 0 && newLeaf->keys[0] < parent->keys[i]) {
        parent->children[i + 2] = parent->children[i + 1];
        i--;
    }
    parent->children[i + 2] = newLeaf;
    parent->keys[i + 1] = newLeaf->keys[0];
    parent->count++;
}

// 插入键值对到非叶子节点
void insertNonLeaf(BPlusTreeNode *node, int key, BPlusTreeNode *child) {
    int i = node->count - 1;
    while (i >= 0 && key < node->keys[i]) {
        node->children[i + 2] = node->children[i + 1];
        i--;
    }
    node->children[i + 2] = child;
    node->keys[i + 1] = key;
    node->count++;
}

// 分裂非叶子节点
void splitNonLeaf(BPlusTreeNode *parent, BPlusTreeNode *node) {
    BPlusTreeNode *newNode = createNode(0);
    newNode->count = ORDER / 2;
    node->count = ORDER / 2;
    for (int i = 0; i < ORDER / 2; i++) {
        newNode->keys[i] = node->keys[ORDER / 2 + i];
        newNode->children[i] = node->children[ORDER / 2 + i];
    }
    newNode->children[ORDER / 2] = node->children[ORDER];

    // 将新非叶子节点插入到父节点
    int i = parent->count - 1;
    while (i >= 0 && newNode->keys[0] < parent->keys[i]) {
        parent->children[i + 2] = parent->children[i + 1];
        i--;
    }
    parent->children[i + 2] = newNode;
    parent->keys[i + 1] = newNode->keys[0];
    parent->count++;
}

// 插入键值对到B+树
void insert(BPlusTreeNode **root, int key) {
    if (*root == NULL) {
        *root = createNode(1);
        (*root)->keys[0] = key;
        (*root)->count = 1;
        return;
    }
    BPlusTreeNode *current = *root;
    BPlusTreeNode *parent = NULL;
    while (!current->isLeaf) {
        parent = current;
        int i = 0;
        while (i < current->count && key > current->keys[i]) {
            i++;
        }
        current = current->children[i];
    }
    if (current->count < ORDER - 1) {
        insertLeaf(current, key);
    } else {
        splitLeaf(parent, current);
        if (parent == NULL) {
            BPlusTreeNode *newRoot = createNode(0);
            newRoot->keys[0] = current->next->keys[0];
            newRoot->children[0] = current;
            newRoot->children[1] = current->next;
            newRoot->count = 1;
            *root = newRoot;
        } else {
            if (parent->count < ORDER - 1) {
                insertNonLeaf(parent, current->next->keys[0], current->next);
            } else {
                splitNonLeaf(parent, current);
            }
        }
    }
}

// 批量插入
void batchInsert(BPlusTreeNode **root, int *keys, int keyCount) {
    for (int i = 0; i < keyCount; i++) {
        insert(root, keys[i]);
    }
}

// 打印B+树叶子节点
void printLeaf(BPlusTreeNode *leaf) {
    while (leaf != NULL) {
        for (int i = 0; i < leaf->count; i++) {
            printf("%d ", leaf->keys[i]);
        }
        leaf = leaf->next;
    }
    printf("\n");
}

优化后的时间复杂度变化

常规插入：每次插入的时间复杂度为O(log n)，其中n为B+树节点数。这是因为每次插入需要先查找插入位置，最坏情况需要遍历从根节点到叶子节点的路径。
批量插入优化后：批量插入在最好情况下（即所有插入都能合并到已有节点，不产生分裂），时间复杂度接近O(1)，因为减少了节点分裂带来的额外开销。在最坏情况下，由于批量插入只是减少了分裂次数而没有改变查找插入位置的本质，所以时间复杂度仍为O(log n)，但平均性能会优于常规插入，因为减少了分裂操作的频率。

面试题：C语言实现B+树的插入优化

知识考点

面试题答案

常规插入算法性能瓶颈分析

优化方案

C语言代码实现优化后的插入操作（以批量插入为例）

优化后的时间复杂度变化