B+树功能的实现

Uncategorized
24k words

B+树的功能实现

1. 在insertToNode函数中，完成if语句中的两个TODO。此时你的代码应该可以完成简单的数据插入、判断重复的key，能够通过测试样例1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
long insertToNode(Node *node, long key, long value) {
    if (node->n > MAX_KEY) {
        return -1; // 已经超过MAX_KEY了，说明split功能没有写好，要检查splitNode函数
    }
    long current_idx = searchKeyInNode(node, key);
    if (node->isLeaf) {
        // 如果已存在相同的键，返回-1
        if (current_idx > -1 && node->key[current_idx] == key) {
            return -1;
        }

        // 否则在key和data数组中，第i位插入对应的数据
        for (long i = node->n; i > current_idx + 1; i--) {
            node->key[i] = node->key[i - 1];
            node->data[i] = node->data[i - 1];
        }
        node->key[current_idx + 1] = key;
        node->data[current_idx + 1] = value;
        node->n++;
        return 0;
    }

    // 对非叶子节点，应该递归地调用本函数，将数据插入child节点中
    Node *child = node->child[current_idx + 1];
    long result = insertToNode(child, key, value);
    if (result == -1) {
        return -1;
    }

    // 根据返回结果判断是否需要分裂子节点
    if (child->n > MAX_KEY) {
        splitNode(node, current_idx + 1);
    }

    return 0;
}

B+树的插入操作的C++实现。

函数参数与返回值

  • node: 指向当前处理的节点的指针。
  • key: 要插入的新键。
  • value: 与键关联的值。
  • 返回值: 成功插入返回0，如果键已经存在于叶子节点中或者插入过程中出现问题，则返回-1。

函数逻辑

  1. 容量检查:
    • 首先检查节点中的键数量是否超过了最大允许的数量MAX_KEY。如果是，返回-1，表示该节点无法接受新的键值对，这可能是因为splitNode函数没有正确实现。
  2. 搜索位置:
    • 使用searchKeyInNode函数找到新键应该插入的位置current_idx。这个函数应该是根据给定的键值在节点中查找相应位置的辅助函数。
  3. 叶子节点处理:
    • 如果当前节点是叶子节点：
      • 如果current_idx大于-1且该位置的键等于要插入的键，说明键已存在，直接返回-1。
      • 否则，在key和data数组的适当位置插入新的键值对，并增加节点中键的数量n。
  4. 非叶子节点处理:
    • 对于非叶子节点，递归地在合适的子节点中调用insertToNode函数来插入键值对。
    • 如果子节点插入成功后其键数量超过了MAX_KEY，则调用splitNode函数对该子节点进行分裂，确保每个节点的键数量不超过最大限制。
  5. 返回结果:
    • 如果所有操作都成功完成，返回0表示插入成功；如果在任何步骤中遇到错误（如节点已满），返回-1。

2. 在equalSearch函数中，完成TODO。此时你的代码应该可以完成单个key的查询，能够通过测试样例2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 等值查询，给出key，查找对应的value，并返回。如果不存在该key，返回-1
// 完成查询操作
long equalSearch(Tree *tree, long key) {
    Node *r = tree->root;
    long current_idx, current_key = -1, result = -1;
    while (1) {
        if (r->isLeaf) {
            // 对于叶子节点，判断key是否存在，相应返回-1或者对应的值
            current_idx = searchKeyInNode(r, key);
            if (current_idx > -1 && r->key[current_idx] == key) {
                result = r->data[current_idx];
            }
            return result;
        } else {
            // 对于非叶子节点，找到key可能存在的唯一子节点，并赋值给r，以进行下一轮循环
            current_idx = searchKeyInNode(r, key);
            r = r->child[current_idx + 1];
        }
    }
}

这段代码实现了在一个B树或B+树中进行等值查询的功能，即根据给定的键key查找对应的值value。如果树中不存在该键，则返回-1。

函数参数与返回值

  • tree: 指向B树的指针。
  • key: 要查询的键。
  • 返回值: 如果找到了对应的键，则返回对应的值；如果没有找到，则返回-1。

函数逻辑

  1. 初始化:
    • 从树的根节点开始，将根节点赋值给r。
    • 初始化current_idx、current_key和result变量，其中result默认为-1，表示未找到键。
  2. 循环遍历:
    • 使用一个无限循环while (1)来遍历树的节点，直到找到目标键或到达叶子节点为止。
  3. 叶子节点处理:
    • 当到达叶子节点时，使用searchKeyInNode函数查找键的位置current_idx。
    • 如果找到匹配的键（即current_idx > -1且r->key[current_idx] == key），则将对应的值赋给result。
    • 返回result，如果找到了键则返回对应的值，否则返回-1。
  4. 非叶子节点处理:
    • 对于非叶子节点，使用searchKeyInNode函数查找键的位置current_idx。
    • 更新r为下一个可能包含目标键的子节点r->child[current_idx + 1]，继续下一轮循环。

3. 在insertToNode函数和splitNode函数中，完成所有TODO。此时你的代码应该可以处理数据插入时需要进行节点分裂的情况，能够通过测试样例3和4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// 对parent的第i个子节点进行分裂
void splitNode(Node *parent, long i) {
    Node *child = parent->child[i];
    Node *sibling = (Node*)malloc(sizeof(Node));  // sibling就是分裂出的节点
    sibling->right = NULL;
    sibling->isLeaf = child->isLeaf;
    sibling->parent = parent;
    
    // 将key、data、child数组中的数据，重新分配给新旧节点
    if (child->isLeaf) {
        sibling->right = child->right;  // 原来的右邻居会成为新节点的右邻居
        child->right = sibling;
        // 对于叶子节点，分裂后两个节点的key的数量总和 = 原节点key的数量
        // 给原节点留一半的数据
        sibling->n = child->n / 2;
        child->n -= sibling->n;
        sibling->data = (long*)malloc(sizeof(long) * (MAX_KEY + 1));
        //TODO STEP 3：将原来child节点key和data数组中的数据按照上述比例分给sibling节点
        for (long j = 0; j < sibling->n; j++) {
            sibling->key[j] = child->key[child->n + j];
            sibling->data[j] = child->data[child->n + j];
        }
        //TODO END
    } else {
        // 对于非叶子节点，分裂后两个节点的key的数量总和 + 1 = 原节点key的数量
        sibling->n = child->n / 2;  // 给新节点分配原来一半数量的键（向下取整）
        child->n -= sibling->n + 1;

        sibling->child = (Node**)malloc(sizeof(Node*) * (MAX_CHILD + 1));
        //TODO STEP 3：将原来child节点key和child数组中的数据按照上述比例分给sibling节点
        for (long j = 0; j < sibling->n; j++) {
            sibling->key[j] = child->key[child->n + 1 + j];
            sibling->child[j] = child->child[child->n + 1 + j];
        }
        sibling->child[sibling->n] = child->child[MAX_CHILD];        
        //TODO END
    }

    //TODO STEP 3：在parent节点的key数组中，第i位插入一个合适的key，用来分隔child和sibling
    //TODO STEP 3：然后在parent节点的child数组中插入sibling节点，最后注意维护parent->n的值
    for (long j = parent->n; j > i; j--) {
        parent->key[j] = parent->key[j - 1];
        parent->child[j + 1] = parent->child[j];
    }
    parent->key[i] = child->key[child->n];
    parent->child[i + 1] = sibling;
    parent->n++;    
    //TODO END
}

// 向node中加入(key,value)对
long insertToNode(Node *node, long key, long value) {
    if (node->n > MAX_KEY) {
        return -1; // 已经超过MAX_KEY了，说明split功能没有写好，要检查splitNode函数
    }
    long current_idx = searchKeyInNode(node, key);
    if (node->isLeaf) {
        //TODO STEP 1：如果已存在相同的键，返回-1
        if (current_idx != -1 && node->key[current_idx] == key) {
            return -1;
        }

        //TODO STEP 1：否则在key和data数组中，第i位插入对应的数据
        for (long i = node->n; i > current_idx + 1; i--) {
            node->data[i] = node->data[i - 1];
            node->key[i] = node->key[i - 1];
        }
        node->key[current_idx + 1] = key;
        node->data[current_idx + 1] = value;
        node->n++; 
        //TODO END
        return 0;
    }
    Node *child = node->child[current_idx + 1];
    //TODO STEP 3：对于非叶子节点，应该递归地调用本函数，将数据插入child节点中
    if (insertToNode(child, key, value) == -1) {
        return -1;
    }
    //TODO STEP 3：并注意根据返回结果判断是否应该返回-1、是否应该调用splitNode函数分裂child节点
    if (child->n > MAX_KEY) {
        splitNode(node, current_idx + 1); // 对child节点进行分裂
    }
    //TODO END
    return 0;
}

函数描述

long insertToNode(Node *node, long key, long value) 是一个用于向B树的指定节点中插入键值对 (key, value) 的函数。该函数实现了B树的基本插入逻辑，包括处理节点已满的情况、插入键值对以及处理非叶子节点的递归插入。

参数

  • Node *node: 指向当前节点的指针。
  • long key: 需要插入的键。
  • long value: 与键对应的值。

返回值

  • 0: 插入成功。
  • -1: 插入失败（例如，节点已满或键已存在）。

代码逻辑详解

  1. 检查节点是否已满

    1
    2
    3
    if (node->n > MAX_KEY) {
        return -1; // 节点已满，插入失败
    }

    这里首先检查当前节点是否已经包含了最大数量的键值对（MAX_KEY）。如果超过了这个限制，则返回-1，表示插入失败。通常这意味着需要先对节点进行分裂。

  2. 查找插入位置

    1
    long current_idx = searchKeyInNode(node, key);

    使用 searchKeyInNode 函数来找到 key 应该插入的位置。这个函数返回一个索引值，指示 key 应该插入的位置或者已存在的相同键的位置。

  3. 处理叶子节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    if (node->isLeaf) {
        if (current_idx != -1 && node->key[current_idx] == key) {
            return -1; // 键已存在，插入失败
        }
        for (long i = node->n; i > current_idx + 1; i--) {
            node->data[i] = node->data[i - 1];
            node->key[i] = node->key[i - 1];
        }
        node->key[current_idx + 1] = key;
        node->data[current_idx + 1] = value;
        node->n++;
        return 0;
    }

    当处理的是叶子节点时：

    • 首先检查是否存在相同的键，如果存在则返回-1表示插入失败。
    • 如果没有找到相同的键，通过移动元素为新的键值对腾出空间。
    • 在正确的位置插入新键值对，并增加节点中的键数。
    • 返回0表示插入成功。

  4. 处理非叶子节点

    1
    2
    3
    4
    5
    6
    7
    8
    Node *child = node->child[current_idx + 1];
    if (insertToNode(child, key, value) == -1) {
        return -1; // 子节点插入失败
    }
    if (child->n > MAX_KEY) {
        splitNode(node, current_idx + 1); // 对子节点进行分裂
    }
    return 0;

    对于非叶子节点：

    • 递归地调用 insertToNode 函数，尝试将键值对插入到合适的子节点中。
    • 如果插入失败，直接返回-1。
    • 如果插入成功后发现子节点超出了最大键数限制，调用 splitNode 函数对子节点进行分裂。
    • 返回0表示插入成功。

关键辅助函数

  • searchKeyInNode: 用于在节点中查找键的位置。返回值为键在数组中的索引，如果键不存在则返回-1。
  • splitNode: 用于对节点进行分裂。当一个节点的键数超过 MAX_KEY 时，需要调用此函数将其分裂成两个节点，并调整父节点的结构。

函数描述

void splitNode(Node *parent, long i) 是一个用于对B树中某个节点进行分裂的函数。当一个节点的键数超过最大键数 MAX_KEY 时，需要调用此函数将其分裂成两个节点，并调整父节点的结构。

参数

  • Node *parent: 指向父节点的指针。
  • long i: 表示需要分裂的子节点在父节点的子节点数组中的索引。

代码逻辑详解

  1. 初始化新节点

    1
    2
    3
    4
    5
    Node *child = parent->child[i];
    Node *sibling = (Node*)malloc(sizeof(Node));  // sibling就是分裂出的节点
    sibling->right = NULL;
    sibling->isLeaf = child->isLeaf;
    sibling->parent = parent;
    • child: 指向需要分裂的子节点。
    • sibling: 分裂后的新节点。
    • 初始化 sibling 的属性，包括 right、isLeaf 和 parent。

  2. 处理叶子节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    if (child->isLeaf) {
        sibling->right = child->right;  // 原来的右邻居会成为新节点的右邻居
        child->right = sibling;
        sibling->n = child->n / 2;
        child->n -= sibling->n;
        sibling->data = (long*)malloc(sizeof(long) * (MAX_KEY + 1));
        for (long j = 0; j < sibling->n; j++) {
            sibling->key[j] = child->key[child->n + j];
            sibling->data[j] = child->data[child->n + j];
        }
    }
    • 对于叶子节点，分裂后两个节点的键的数量总和等于原节点的键的数量。
    • 给原节点留一半的数据，另一半数据分配给新节点 sibling。
    • 更新 child 和 sibling 的键和数据数组。
    • 更新 child 和 sibling 的 right 指针，确保链表的连续性。

  3. 处理非叶子节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    else {
        sibling->n = child->n / 2;  // 给新节点分配原来一半数量的键（向下取整）
        child->n -= sibling->n + 1;

        sibling->child = (Node**)malloc(sizeof(Node*) * (MAX_CHILD + 1));
        for (long j = 0; j < sibling->n; j++) {
            sibling->key[j] = child->key[child->n + 1 + j];
            sibling->child[j] = child->child[child->n + 1 + j];
        }
        sibling->child[sibling->n] = child->child[MAX_CHILD];
    }
    • 对于非叶子节点，分裂后两个节点的键的数量总和加1等于原节点的键的数量。
    • 给新节点 sibling 分配原来一半数量的键（向下取整），并更新 child 的键数。
    • 更新 sibling 的子节点数组。
    • 确保最后一个子节点指针正确设置。

  4. 更新父节点

    1
    2
    3
    4
    5
    6
    7
    for (long j = parent->n; j > i; j--) {
        parent->key[j] = parent->key[j - 1];
        parent->child[j + 1] = parent->child[j];
    }
    parent->key[i] = child->key[child->n];
    parent->child[i + 1] = sibling;
    parent->n++;
    • 在父节点的键数组中，第 i 位插入一个合适的键，用来分隔 child 和 sibling。
    • 在父节点的子节点数组中插入 sibling 节点。
    • 更新父节点的键数 n。

关键辅助函数

  • malloc: 用于动态分配内存。
  • free: 用于释放内存（在其他地方使用）。

4. 在delFromNode函数中，完成if语句中的两个TODO。此时你的代码应该可以完成简单的数据删除、判断不存在的key，能够通过测试样例5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 从node中删除key
long delFromNode(Node *node, long key) {
    long current_idx = searchKeyInNode(node, key);
    if (node->isLeaf) {
        //TODO STEP 4：如果已存在相同的键，返回-1
        if (current_idx == -1 || node->key[current_idx] != key) 
        {
            return -1;
        }
        //TODO STEP 4：否则在key和data数组中，删除第i位的数据，更新node->n的值
        for (long i = current_idx; i < node->n - 1; i++) {
            node->key[i] = node->key[i + 1];
            node->data[i] = node->data[i + 1];
        }
        node->n--;          
        //TODO END
        return 0;
    }
    Node *child = node->child[current_idx + 1];
    // 对非叶子节点，递归地在child节点中进行删除
    if (delFromNode(child, key) == -1) {
        return -1;
    } else {
        // delFromNode返回0，说明删除成功，如果当前节点也存了这个key，需要替换为child子树中最小的key
        if (current_idx > -1 && node->key[current_idx] == key) {
            while (!child->isLeaf) {
                child = child->child[0];
            }
            node->key[current_idx] = child->key[0];
        }
        //TODO STEP 5：当子节点的key过少时，需要调用mergeNode进行节点的合并
        if (child->n < MIN_KEY) {
            mergeNode(node, current_idx + 1);
        }        
        //TODO END
    } 
    return 0;
}

B树删除操作实现说明文档

函数描述

long delFromNode(Node *node, long key) 是一个用于从B树的指定节点中删除键值对 (key, value) 的函数。该函数实现了B树的基本删除逻辑，包括处理节点已满的情况、删除键值对以及处理非叶子节点的递归删除。

参数

  • Node *node: 指向当前节点的指针。
  • long key: 需要删除的键。

返回值

  • 0: 删除成功。
  • -1: 删除失败（例如，键不存在）。

代码逻辑详解

  1. 查找键的位置

    1
    long current_idx = searchKeyInNode(node, key);

    使用 searchKeyInNode 函数来找到 key 在当前节点中的位置。这个函数返回一个索引值，指示 key 在数组中的位置或者返回-1表示键不存在。

  2. 处理叶子节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    if (node->isLeaf) {
        if (current_idx == -1 || node->key[current_idx] != key) {
            return -1; // 键不存在，删除失败
        }
        for (long i = current_idx; i < node->n - 1; i++) {
            node->key[i] = node->key[i + 1];
            node->data[i] = node->data[i + 1];
        }
        node->n--;          
        return 0;
    }

    当处理的是叶子节点时：

    • 检查是否存在相同的键，如果不存在则返回-1表示删除失败。
    • 如果存在相同的键，通过移动元素来删除键值对，并减少节点中的键数。
    • 返回0表示删除成功。

  3. 处理非叶子节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    Node *child = node->child[current_idx + 1];
    if (delFromNode(child, key) == -1) {
        return -1; // 子节点删除失败
    } else {
        if (current_idx > -1 && node->key[current_idx] == key) {
            while (!child->isLeaf) {
                child = child->child[0];
            }
            node->key[current_idx] = child->key[0];
        }
        if (child->n < MIN_KEY) {
            mergeNode(node, current_idx + 1); // 对子节点进行合并
        }        
    } 
    return 0;

    对于非叶子节点：

    • 递归地调用 delFromNode 函数，尝试在合适的子节点中删除键值对。
    • 如果删除失败，直接返回-1。
    • 如果删除成功且当前节点也存储了这个键，需要从子树中找到最小的键来替换当前节点中的键。
    • 如果子节点的键数低于最小键数 MIN_KEY，调用 mergeNode 函数对子节点进行合并。
    • 返回0表示删除成功。

关键辅助函数

  • searchKeyInNode: 用于在节点中查找键的位置。返回值为键在数组中的索引，如果键不存在则返回-1。
  • mergeNode: 用于对节点进行合并。当一个节点的键数低于 MIN_KEY 时，需要调用此函数将其与相邻节点合并。

5. 在delFromNode函数和mergeNode函数中，完成所有TODO。此时你的代码应该可以处理非叶子节点的合并，能够通过测试样例6和7。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// 对parent的第k个子节点进行合并
void mergeNode(Node *parent, long k) {
    // 默认是向右合并（k与k+1合并）；如果k是parent的最后一个子节点了，就向左合并（k-1与k合并）
    if (k == parent->n) {
        k--;
    }
    if (k < 0) {
        return; // 如果k<0，说明parent的子节点数量小于2，一般是因为delFromTree或者mergeNode函数没有写好
    }
    Node *lchild = parent->child[k];
    Node *rchild = parent->child[k+1];
    
    // 如果两个节点的key数量足够多，就不必合并，而是在两个节点间重新分配key
    long total = lchild->n + rchild->n;
    if (total >= MIN_KEY + MIN_KEY) {
        // 计算两个节点分完各应该有多少个key
        long left_size = total / 2;
        long right_size = total - left_size;
    
        // 情况1：左边节点的数量比计算出来的少，把右边节点的数据往左挪
    
        long offset = left_size - lchild->n;
        if (offset > 0) {
            // 先把数据按照计算好的下标从右节点拷贝到左节点
            for (long i = lchild->n; i < left_size; i++) {
                lchild->key[i] = parent->key[k];
                if (lchild->isLeaf) {
                    parent->key[k] = rchild->key[i - lchild->n + 1];
                    lchild->data[i] = rchild->data[i - lchild->n];
                } else {
                    parent->key[k] = rchild->key[i - lchild->n];
                    lchild->child[i + 1] = rchild->child[i - lchild->n];
                }
            }
            // 挪完后，把右节点未拷贝的数据往前移，放到正确的位置上
            if (lchild->isLeaf) {
                for (long i = 0; i < right_size; i++) {
                    rchild->key[i] = rchild->key[i + offset];
                    rchild->data[i] = rchild->data[i + offset];
                }
            } else {
                for (long i = 0; i < right_size; i++) {
                    rchild->key[i] = rchild->key[i + offset];
                    rchild->child[i] = rchild->child[i + offset];
                }
                rchild->child[right_size] = rchild->child[right_size + offset];
            }
        }
    
        //情况2：右边节点的数量比计算出来的少，把左边节点的数据往右挪
    
        offset = right_size - rchild->n;
        if (offset > 0) {
            // 与上面的步骤相反，需要先把右节点的已有数据往后移，为拷贝数据腾出空间
            if (lchild->isLeaf) {
                //TODO STEP 5：参考上面的代码，完成叶子结点的数据挪动
                for (long i = rchild->n - 1; i >= 0; i--) {
                    rchild->key[i + offset] = rchild->key[i];
                    rchild->data[i + offset] = rchild->data[i];
                }
                //TODO END
            } else {
                //TODO STEP 5：参考上面的代码，完成非叶子结点的数据挪动
                for (long i = rchild->n - 1; i >= 0; i--) {
                    rchild->key[i + offset] = rchild->key[i];
                }
                for (long i = rchild->n; i >= 0; i--) {
                    rchild->child[i + offset] = rchild->child[i];
                }
                //TODO END
            }
            //TODO STEP 5：参考上面的代码，将数据从左节点拷贝到右节点的正确位置
            //TODO STEP 5：注意parent的key数组应该如何更新
            if (lchild->isLeaf) {
                for (long i = 0; i < offset; i++) {
                    rchild->key[i] = lchild->key[lchild->n - offset + i];
                    rchild->data[i] = lchild->data[lchild->n - offset + i];
                }
                parent->key[k] = rchild->key[0];
            } else {
                rchild->key[offset - 1] = parent->key[k];
                for (long i = 0; i < offset - 1; i++) {
                    rchild->key[i] = lchild->key[lchild->n - offset + i + 1];
                }
                for (long i = 0; i < offset; i++) {
                    rchild->child[i] = lchild->child[lchild->n - offset + i + 1];
                }
                parent->key[k] = lchild->key[lchild->n - offset];
            }
            //TODO END
        }
        lchild->n = left_size;
        rchild->n = right_size;
    } else { // 两个节点不够分，必须要合并节点，这里选择把右节点合并到左节点中
        if (lchild->isLeaf) {
            //TODO STEP 5：完成叶子结点的数据挪动
            for (long i = 0; i < rchild->n; i++) {
                lchild->key[lchild->n + i] = rchild->key[i];
                lchild->data[lchild->n + i] = rchild->data[i];
            }
            //TODO END
            lchild->n = lchild->n + rchild->n;
            free(rchild->data);
        } else {
            //TODO STEP 5：完成非叶子结点的数据挪动，注意parent的key数组应该如何使用
            lchild->key[lchild->n] = parent->key[k];
            for (long i = 0; i < rchild->n; i++) {
                lchild->key[lchild->n + 1 + i] = rchild->key[i];
            }
            for (long i = 0; i <= rchild->n; i++) {
                lchild->child[lchild->n + 1 + i] = rchild->child[i];
            }
            //TODO END
            lchild->n = lchild->n + rchild->n + 1;
            free(rchild->child);
        }
        //TODO STEP 5：在parent节点的key和child数组中删除相应位置的值
        for (long i = k; i < parent->n - 1; i++) {
            parent->key[i] = parent->key[i + 1];
        }
        for (long i = k + 1; i < parent->n; i++) {
            parent->child[i] = parent->child[i + 1];
        }
        //TODO END
        parent->n--;
        lchild->right = rchild->right;
        free(rchild);
    }
}

B树节点合并实现说明文档

函数描述

void mergeNode(Node *parent, long k) 是一个用于对B树中某个节点进行合并的函数。当一个节点的键数低于最小键数 MIN_KEY 时，需要调用此函数将其与相邻节点合并，以确保B树的性质不变。

参数

  • Node *parent: 指向父节点的指针。
  • long k: 表示需要合并的子节点在父节点的子节点数组中的索引。

代码逻辑详解

  1. 确定合并方向

    1
    2
    3
    4
    5
    6
    7
    8
    if (k == parent->n) {
        k--;
    }
    if (k < 0) {
        return; // 如果k<0，说明parent的子节点数量小于2，一般是因为delFromTree或者mergeNode函数没有写好
    }
    Node *lchild = parent->child[k];
    Node *rchild = parent->child[k+1];
    • 如果 k 是父节点的最后一个子节点，调整 k 使其指向倒数第二个子节点，进行向左合并。
    • 如果 k 小于0，说明父节点的子节点数量小于2，直接返回。
    • 获取需要合并的两个子节点 lchild 和 rchild。

  2. 检查是否需要合并

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    long total = lchild->n + rchild->n;
    if (total >= MIN_KEY + MIN_KEY) {
        // 计算两个节点分完各应该有多少个key
        long left_size = total / 2;
        long right_size = total - left_size;

        // 情况1：左边节点的数量比计算出来的少，把右边节点的数据往左挪
        long offset = left_size - lchild->n;
        if (offset > 0) {
            for (long i = lchild->n; i < left_size; i++) {
                lchild->key[i] = parent->key[k];
                if (lchild->isLeaf) {
                    parent->key[k] = rchild->key[i - lchild->n + 1];
                    lchild->data[i] = rchild->data[i - lchild->n];
                } else {
                    parent->key[k] = rchild->key[i - lchild->n];
                    lchild->child[i + 1] = rchild->child[i - lchild->n];
                }
            }
            if (lchild->isLeaf) {
                for (long i = 0; i < right_size; i++) {
                    rchild->key[i] = rchild->key[i + offset];
                    rchild->data[i] = rchild->data[i + offset];
                }
            } else {
                for (long i = 0; i < right_size; i++) {
                    rchild->key[i] = rchild->key[i + offset];
                    rchild->child[i] = rchild->child[i + offset];
                }
                rchild->child[right_size] = rchild->child[right_size + offset];
            }
        }

        // 情况2：右边节点的数量比计算出来的少，把左边节点的数据往右挪
        offset = right_size - rchild->n;
        if (offset > 0) {
            if (lchild->isLeaf) {
                for (long i = rchild->n - 1; i >= 0; i--) {
                    rchild->key[i + offset] = rchild->key[i];
                    rchild->data[i + offset] = rchild->data[i];
                }
                for (long i = 0; i < offset; i++) {
                    rchild->key[i] = lchild->key[lchild->n - offset + i];
                    rchild->data[i] = lchild->data[lchild->n - offset + i];
                }
                parent->key[k] = rchild->key[0];
            } else {
                for (long i = rchild->n - 1; i >= 0; i--) {
                    rchild->key[i + offset] = rchild->key[i];
                }
                for (long i = rchild->n; i >= 0; i--) {
                    rchild->child[i + offset] = rchild->child[i];
                }
                rchild->key[offset - 1] = parent->key[k];
                for (long i = 0; i < offset - 1; i++) {
                    rchild->key[i] = lchild->key[lchild->n - offset + i + 1];
                }
                for (long i = 0; i < offset; i++) {
                    rchild->child[i] = lchild->child[lchild->n - offset + i + 1];
                }
                parent->key[k] = lchild->key[lchild->n - offset];
            }
        }
        lchild->n = left_size;
        rchild->n = right_size;
    } else {
        // 两个节点不够分，必须要合并节点，这里选择把右节点合并到左节点中
        if (lchild->isLeaf) {
            for (long i = 0; i < rchild->n; i++) {
                lchild->key[lchild->n + i] = rchild->key[i];
                lchild->data[lchild->n + i] = rchild->data[i];
            }
            lchild->n = lchild->n + rchild->n;
            free(rchild->data);
        } else {
            lchild->key[lchild->n] = parent->key[k];
            for (long i = 0; i < rchild->n; i++) {
                lchild->key[lchild->n + 1 + i] = rchild->key[i];
            }
            for (long i = 0; i <= rchild->n; i++) {
                lchild->child[lchild->n + 1 + i] = rchild->child[i];
            }
            lchild->n = lchild->n + rchild->n + 1;
            free(rchild->child);
        }
        for (long i = k; i < parent->n - 1; i++) {
            parent->key[i] = parent->key[i + 1];
        }
        for (long i = k + 1; i < parent->n; i++) {
            parent->child[i] = parent->child[i + 1];
        }
        parent->n--;
        lchild->right = rchild->right;
        free(rchild);
    }
    • 计算总键数：计算 lchild 和 rchild 的总键数 total。
    • 检查是否需要合并：
      • 如果总键数大于或等于 MIN_KEY + MIN_KEY，不需要合并，而是重新分配键。
      • 情况1：如果左边节点的数量比计算出来的少，把右边节点的数据往左挪。
      • 情况2：如果右边节点的数量比计算出来的少，把左边节点的数据往右挪。
    • 合并节点：
      • 如果总键数不足以分成两个节点，必须合并节点。这里选择把右节点合并到左节点中。
      • 对于叶子节点，直接将右节点的键和数据复制到左节点中。
      • 对于非叶子节点，将右节点的键和子节点复制到左节点中，并更新父节点的键和子节点数组。
      • 更新父节点的键数 n，并释放右节点的内存。

关键辅助函数

  • free: 用于释放内存。

6. 在delFromTree函数中，完成TODO。此时你的代码应该可以完全处理所有情况下的数据插入、删除，能够通过测试样例8。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long delFromTree(Tree *tree, long key) {
    if (delFromNode(tree->root, key) == -1) {
        return -1;
    }
    // 检查是否需要替换根节点
    if (tree->root->n == 0 && !tree->root->isLeaf) {
        //TODO STEP 6：将根节点的唯一子节点作为新的根节点，然后删除原根节点的数据
        Node *old_root = tree->root;
        tree->root = old_root->child[0]; // 将唯一的子节点作为新的根节点
        tree->root->parent = NULL;       // 新根节点的父指针置为空
        free(old_root->child);           // 释放旧根节点的子节点数组
        free(old_root);      
        //TODO END
    }
    tree->size--;
    return 0;
}

B树删除操作实现说明文档

函数描述

long delFromTree(Tree *tree, long key) 是一个用于从B树中删除键值对 (key, value) 的函数。该函数实现了B树的基本删除逻辑，包括调用 delFromNode 函数删除键值对，并处理根节点的特殊情况。

参数

  • Tree *tree: 指向B树的指针。
  • long key: 需要删除的键。

返回值

  • 0: 删除成功。
  • -1: 删除失败（例如，键不存在）。

代码逻辑详解

  1. 调用 delFromNode 删除键值对

    1
    2
    3
    if (delFromNode(tree->root, key) == -1) {
        return -1;
    }

    调用 delFromNode 函数从根节点开始删除键值对。如果删除失败，直接返回-1。

  2. 检查是否需要替换根节点

    1
    2
    3
    4
    5
    6
    7
    if (tree->root->n == 0 && !tree->root->isLeaf) {
        Node *old_root = tree->root;
        tree->root = old_root->child[0]; // 将唯一的子节点作为新的根节点
        tree->root->parent = NULL;       // 新根节点的父指针置为空
        free(old_root->child);           // 释放旧根节点的子节点数组
        free(old_root);                  // 释放旧根节点
    }

    如果删除操作导致根节点的键数为0且根节点不是叶子节点，需要将根节点的唯一子节点作为新的根节点，并释放旧的根节点。

  3. 更新树的大小

    1
    2
    tree->size--;
    return 0;

    更新B树的大小，并返回0表示删除成功。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long delFromTree(Tree *tree, long key) {
    if (delFromNode(tree->root, key) == -1) {
        return -1;
    }
    // 检查是否需要替换根节点
    if (tree->root->n == 0 && !tree->root->isLeaf) {
        Node *old_root = tree->root;
        tree->root = old_root->child[0]; // 将唯一的子节点作为新的根节点
        tree->root->parent = NULL;       // 新根节点的父指针置为空
        free(old_root->child);           // 释放旧根节点的子节点数组
        free(old_root);                  // 释放旧根节点
    }
    tree->size--;
    return 0;
}

关键辅助函数

  • delFromNode: 用于从指定节点中删除键值对。
  • free: 用于释放内存。

7. 在rangeSearch函数中，完成TODO。此时你的代码应该可以处理上述所有指令了，能够通过测试样例9。如果你的代码效率足够高，应该能够通过所有10个测试样例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 范围查询，给出key的范围[start,end]，查找对应的键值对，并返回总数。
// buffer要有足够的空间
long rangeSearch(Tree *tree, long start, long end, KV *buffer, long buffer_length) {
    Node *r = tree->root;
    long current_idx, current_key;
    while (1) {
        current_idx = searchKeyInNode(r, start); 
        if (r->isLeaf) {
            current_key = current_idx == -1 ? -1 : r->key[current_idx];
            break;
        }
        r = r->child[current_idx + 1];
    }
    // 如果所有key都大于start，返回的currentKey = -1，可不做特殊处理
    if (current_key < start) {
        current_idx++;
        if (current_idx == r->n) {
            r = r->right;
            current_idx = 0;
        }
    }
    long count = 0;
    //TODO STEP 7：上面已经找到了起始节点r和起始位置current_idx，现在把数据按顺序放入buffer中，
    //TODO STEP 7：虽然输入保证了数据量不会超过buffer_length，但是最好应该判断一下
    //TODO STEP 7：提示：利用好right指针，记得统计总数count
    while (r && count < buffer_length) {
        for (long i = current_idx; i < r->n && count < buffer_length; i++) {
            if (r->key[i] > end) {
                return count;  // 超出范围，直接返回
            }
            buffer[count].key = r->key[i];
            buffer[count].value = r->data[i];
            count++;
        }
        r = r->right;  // 移动到下一个叶节点
        current_idx = 0;  // 在下一个节点从第一个位置开始
    }    
    //TODO END
    return count;
}

B树范围查询实现说明文档

函数描述

long rangeSearch(Tree *tree, long start, long end, KV *buffer, long buffer_length) 是一个用于在B树中进行范围查询的函数。该函数查找键值对在 [start, end] 范围内的所有键值对，并将它们存储在 buffer 中，返回找到的键值对总数。

参数

  • Tree *tree: 指向B树的指针。
  • long start: 查询范围的起始键。
  • long end: 查询范围的结束键。
  • KV *buffer: 用于存储查询结果的缓冲区。
  • long buffer_length: 缓冲区的最大长度。

返回值

  • long: 找到的键值对总数。

代码逻辑详解

  1. 找到起始节点和起始位置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Node *r = tree->root;
    long current_idx, current_key;
    while (1) {
        current_idx = searchKeyInNode(r, start); 
        if (r->isLeaf) {
            current_key = current_idx == -1 ? -1 : r->key[current_idx];
            break;
        }
        r = r->child[current_idx + 1];
    }
    • 从根节点开始，使用 searchKeyInNode 函数找到 start 键在当前节点中的位置。
    • 如果当前节点是叶子节点，记录当前键 current_key 并退出循环。
    • 如果当前节点不是叶子节点，继续向下遍历到合适的子节点。

  2. 调整起始位置

    1
    2
    3
    4
    5
    6
    7
    if (current_key < start) {
        current_idx++;
        if (current_idx == r->n) {
            r = r->right;
            current_idx = 0;
        }
    }
    • 如果 current_key 小于 start，调整 current_idx 到下一个位置。
    • 如果 current_idx 超过了当前节点的键数，移动到下一个叶子节点，并将 current_idx 重置为0。

  3. 收集范围内的键值对

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    long count = 0;
    while (r && count < buffer_length) {
        for (long i = current_idx; i < r->n && count < buffer_length; i++) {
            if (r->key[i] > end) {
                return count;  // 超出范围，直接返回
            }
            buffer[count].key = r->key[i];
            buffer[count].value = r->data[i];
            count++;
        }
        r = r->right;  // 移动到下一个叶节点
        current_idx = 0;  // 在下一个节点从第一个位置开始
    }
    • 初始化计数器 count 为0。
    • 使用 while 循环遍历所有相关的叶子节点，直到 r 为空或 count 达到 buffer_length。
    • 在每个叶子节点中，使用 for 循环遍历键值对，将符合条件的键值对存储到 buffer 中。
    • 如果当前键大于 end，直接返回 count。
    • 如果当前节点的所有键值对都已处理完毕，移动到下一个叶子节点，并将 current_idx 重置为0。

  4. 返回结果

    1
    return count;
    • 返回找到的键值对总数 count。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
long rangeSearch(Tree *tree, long start, long end, KV *buffer, long buffer_length) {
    Node *r = tree->root;
    long current_idx, current_key;
    while (1) {
        current_idx = searchKeyInNode(r, start); 
        if (r->isLeaf) {
            current_key = current_idx == -1 ? -1 : r->key[current_idx];
            break;
        }
        r = r->child[current_idx + 1];
    }
    if (current_key < start) {
        current_idx++;
        if (current_idx == r->n) {
            r = r->right;
            current_idx = 0;
        }
    }
    long count = 0;
    while (r && count < buffer_length) {
        for (long i = current_idx; i < r->n && count < buffer_length; i++) {
            if (r->key[i] > end) {
                return count;  // 超出范围，直接返回
            }
            buffer[count].key = r->key[i];
            buffer[count].value = r->data[i];
            count++;
        }
        r = r->right;  // 移动到下一个叶节点
        current_idx = 0;  // 在下一个节点从第一个位置开始
    }
    return count;
}

关键辅助函数

  • searchKeyInNode: 用于在节点中查找键的位置。返回值为键在数组中的索引，如果键不存在则返回-1。
Comments