Spaces:
Sleeping
Sleeping
| // B-tree implementation - self-balancing tree optimized for disk access | |
| // Each node can have multiple keys and children | |
| typedef struct BTreeNode { | |
| int *keys; | |
| struct BTreeNode **children; | |
| int num_keys; | |
| int is_leaf; | |
| } BTreeNode; | |
| typedef struct { | |
| BTreeNode *root; | |
| } BTree; | |
| BTreeNode* create_node(int is_leaf) { | |
| BTreeNode *node = (BTreeNode*)malloc(sizeof(BTreeNode)); | |
| node->keys = (int*)malloc((2 * T - 1) * sizeof(int)); | |
| node->children = (BTreeNode**)malloc(2 * T * sizeof(BTreeNode*)); | |
| node->num_keys = 0; | |
| node->is_leaf = is_leaf; | |
| return node; | |
| } | |
| BTree* create_btree() { | |
| BTree *tree = (BTree*)malloc(sizeof(BTree)); | |
| tree->root = create_node(1); | |
| return tree; | |
| } | |
| void split_child(BTreeNode *parent, int index) { | |
| BTreeNode *full_child = parent->children[index]; | |
| BTreeNode *new_child = create_node(full_child->is_leaf); | |
| new_child->num_keys = T - 1; | |
| // Copy last T-1 keys to new node | |
| for (int i = 0; i < T - 1; i++) { | |
| new_child->keys[i] = full_child->keys[i + T]; | |
| } | |
| // Copy last T children if not leaf | |
| if (!full_child->is_leaf) { | |
| for (int i = 0; i < T; i++) { | |
| new_child->children[i] = full_child->children[i + T]; | |
| } | |
| } | |
| full_child->num_keys = T - 1; | |
| // Shift parent's children | |
| for (int i = parent->num_keys; i > index; i--) { | |
| parent->children[i + 1] = parent->children[i]; | |
| } | |
| parent->children[index + 1] = new_child; | |
| // Shift parent's keys | |
| for (int i = parent->num_keys - 1; i >= index; i--) { | |
| parent->keys[i + 1] = parent->keys[i]; | |
| } | |
| parent->keys[index] = full_child->keys[T - 1]; | |
| parent->num_keys++; | |
| } | |
| void insert_non_full(BTreeNode *node, int key) { | |
| int i = node->num_keys - 1; | |
| if (node->is_leaf) { | |
| // Shift keys and insert | |
| while (i >= 0 && key < node->keys[i]) { | |
| node->keys[i + 1] = node->keys[i]; | |
| i--; | |
| } | |
| node->keys[i + 1] = key; | |
| node->num_keys++; | |
| } else { | |
| // Find child to insert into | |
| while (i >= 0 && key < node->keys[i]) { | |
| i--; | |
| } | |
| i++; | |
| if (node->children[i]->num_keys == 2 * T - 1) { | |
| split_child(node, i); | |
| if (key > node->keys[i]) { | |
| i++; | |
| } | |
| } | |
| insert_non_full(node->children[i], key); | |
| } | |
| } | |
| void btree_insert(BTree *tree, int key) { | |
| BTreeNode *root = tree->root; | |
| if (root->num_keys == 2 * T - 1) { | |
| BTreeNode *new_root = create_node(0); | |
| new_root->children[0] = root; | |
| split_child(new_root, 0); | |
| tree->root = new_root; | |
| insert_non_full(new_root, key); | |
| } else { | |
| insert_non_full(root, key); | |
| } | |
| } | |
| BTreeNode* search(BTreeNode *node, int key) { | |
| int i = 0; | |
| while (i < node->num_keys && key > node->keys[i]) { | |
| i++; | |
| } | |
| if (i < node->num_keys && key == node->keys[i]) { | |
| return node; | |
| } | |
| if (node->is_leaf) { | |
| return NULL; | |
| } | |
| return search(node->children[i], key); | |
| } | |
| int get_height(BTreeNode *node) { | |
| if (!node || node->is_leaf) return 1; | |
| return 1 + get_height(node->children[0]); | |
| } | |
| void free_btree(BTreeNode *node) { | |
| if (!node) return; | |
| if (!node->is_leaf) { | |
| for (int i = 0; i <= node->num_keys; i++) { | |
| free_btree(node->children[i]); | |
| } | |
| } | |
| free(node->keys); | |
| free(node->children); | |
| free(node); | |
| } | |
| int main() { | |
| BTree *tree = create_btree(); | |
| unsigned int seed = 42; | |
| clock_t start = clock(); | |
| // Insert operations | |
| for (int i = 0; i < NUM_OPERATIONS; i++) { | |
| seed = seed * 1103515245 + 12345; | |
| int key = seed % 50000; | |
| btree_insert(tree, key); | |
| } | |
| // Search operations | |
| int found = 0; | |
| for (int i = 0; i < NUM_OPERATIONS / 2; i++) { | |
| seed = seed * 1103515245 + 12345; | |
| int key = seed % 50000; | |
| if (search(tree->root, key)) { | |
| found++; | |
| } | |
| } | |
| int height = get_height(tree->root); | |
| clock_t end = clock(); | |
| double time_spent = (double)(end - start) / CLOCKS_PER_SEC; | |
| printf("B-tree (degree=%d): %d operations, %.6f seconds\n", T, NUM_OPERATIONS, time_spent); | |
| printf("Tree height: %d, Found: %d\n", height, found); | |
| free_btree(tree->root); | |
| free(tree); | |
| return 0; | |
| } | |