面试题：C语言B+树在高并发场景下的锁机制设计

锁粒度选择及优缺点分析

树级锁
- 锁粒度：对整个B+树加锁。
- 优点：实现简单，易于理解和维护。在任何操作（插入、删除、查找）时，只需要获取树级锁，能保证数据的一致性。
- 缺点：并发性能差。因为同一时间只有一个线程可以访问树，其他线程都需要等待锁的释放，容易造成线程阻塞，降低系统的吞吐量。
节点级锁
- 锁粒度：对B+树的每个节点分别加锁。
- 优点：并发性能好。不同线程可以同时访问不同的节点，提高了系统的并发度。例如，在查找操作时，多个线程可以同时在不同的分支上进行查找。
- 缺点：实现复杂。需要考虑锁的获取和释放顺序，避免死锁。例如，在插入或删除操作时，可能需要获取多个节点的锁，若锁的获取顺序不当，可能会导致死锁。

C语言代码示例

以下是使用节点级锁实现B+树操作的C语言代码示例，假设使用pthread_mutex_t作为锁机制。

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

// 定义B+树节点结构
typedef struct BPlusTreeNode {
    int *keys;
    struct BPlusTreeNode **children;
    int keyCount;
    int isLeaf;
    pthread_mutex_t lock;
} BPlusTreeNode;

// 定义B+树结构
typedef struct BPlusTree {
    BPlusTreeNode *root;
    int degree;
} BPlusTree;

// 创建一个新的B+树节点
BPlusTreeNode* createNode(int degree, int isLeaf) {
    BPlusTreeNode *node = (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode));
    node->keys = (int*)malloc((2 * degree - 1) * sizeof(int));
    node->children = (BPlusTreeNode**)malloc(2 * degree * sizeof(BPlusTreeNode*));
    node->keyCount = 0;
    node->isLeaf = isLeaf;
    pthread_mutex_init(&node->lock, NULL);
    return node;
}

// 查找操作
int search(BPlusTree *tree, int key) {
    BPlusTreeNode *current = tree->root;
    while (current->isLeaf == 0) {
        pthread_mutex_lock(&current->lock);
        int i = 0;
        while (i < current->keyCount && key > current->keys[i]) {
            i++;
        }
        BPlusTreeNode *child = current->children[i];
        pthread_mutex_unlock(&current->lock);
        current = child;
    }
    pthread_mutex_lock(&current->lock);
    int i = 0;
    while (i < current->keyCount && key > current->keys[i]) {
        i++;
    }
    int found = (i < current->keyCount && key == current->keys[i]);
    pthread_mutex_unlock(&current->lock);
    return found;
}

// 插入操作
void insert(BPlusTree *tree, int key) {
    BPlusTreeNode *root = tree->root;
    if (root == NULL) {
        root = createNode(tree->degree, 1);
        root->keys[0] = key;
        root->keyCount = 1;
        tree->root = root;
        return;
    }
    if (root->keyCount == 2 * tree->degree - 1) {
        BPlusTreeNode *newRoot = createNode(tree->degree, 0);
        newRoot->children[0] = root;
        tree->root = newRoot;
        // 分裂根节点
        // 这里省略具体分裂代码
    }
    // 查找插入位置并插入
    BPlusTreeNode *current = root;
    while (current->isLeaf == 0) {
        pthread_mutex_lock(&current->lock);
        int i = 0;
        while (i < current->keyCount && key > current->keys[i]) {
            i++;
        }
        BPlusTreeNode *child = current->children[i];
        pthread_mutex_unlock(&current->lock);
        current = child;
    }
    pthread_mutex_lock(&current->lock);
    int i = current->keyCount - 1;
    while (i >= 0 && key < current->keys[i]) {
        current->keys[i + 1] = current->keys[i];
        i--;
    }
    current->keys[i + 1] = key;
    current->keyCount++;
    pthread_mutex_unlock(&current->lock);
}

// 删除操作
// 这里省略具体删除代码，删除操作也需要类似的锁处理

int main() {
    BPlusTree tree;
    tree.degree = 2;
    tree.root = NULL;
    insert(&tree, 10);
    insert(&tree, 20);
    printf("Search 10: %d\n", search(&tree, 10));
    printf("Search 30: %d\n", search(&tree, 30));
    return 0;
}

上述代码展示了在B+树的查找和插入操作中如何使用节点级锁。删除操作也需要类似的锁处理逻辑，在获取和释放锁时要特别注意顺序以避免死锁。同时，实际应用中还需要考虑更多细节，如锁的销毁等。

星途面试题库

面试题：C语言B+树在高并发场景下的锁机制设计

知识考点

面试题答案

锁粒度选择及优缺点分析

C语言代码示例