b_plus_tree.zip_b 树_b+tree_b_plus_tree_b树数据库_galles b plus tree

#include <stdio.h> // max length of key, bytes #define MAX_KEY_LEN 32 // block size, k bytes #define BLOCK_SIZE 8 // pointer length in 32-bit system #define POINTER_LENGTH 4 // MAX_KEY_LEN*2x+sizeof(int)*2x+POINTER_LENGTH*2x+POINTER_LENGTH*3+sizeof(unsigned int)*4 = BLOCK_SIZE #define BTREE_MIN_DEGREE (int)((8*1024 - POINTER_LENGTH*3 - sizeof(unsigned int)*4) \ / (MAX_KEY_LEN*2 + sizeof(int)*2 + POINTER_LENGTH*2)) typedef struct btree_node { char key[2*BTREE_MIN_DEGREE-1][MAX_KEY_LEN]; int key_len[2*BTREE_MIN_DEGREE-1]; // key's acutual length struct void *child[2*BTREE_MIN_DEGREE]; // pointer to a btree_node, or a data node if it's a leaf struct btree_node *parent; struct btree_node *l_sibling; struct btree_node *r_sibling; unsigned int num_key; unsigned int isLeaf; unsigned int isRoot; unsigned int root_level; } btree_node; /* wrap for search node */ typedef struct btree_srched_node { btree_node *node; int pos; //position of key in node } btree_srched_node; btree_node *root; static void split_child(btree_node **pparent, long pos, btree_node *child); static void insert_nonfull(btree_node *node, int key); static void delete_key(btree_node *node, int pos,btree_node *child); static void replace_key_up(btree_node *node, int key, int replaceWith); static void insert_predecessor(btree_node *node, int key, btree_node *child); static void insert_successor(btree_node *node, int key, btree_node *child); static void merge_node(btree_node **plNode, btree_node *rNode); static int get_key_pos(btree_node *node, int key); static int get_subtree_for_key(btree_node *node, int key); /*search one key in one B-Tree*/ btree_srched_node* btree_search(btree_node *node, int key) { int i = 0; btree_node *child; btree_srched_node *srched_node; while ((i < node->num_key) && (key > node->key[i])) { i++; } if ((i < node->num_key) && (key == node->key[i] ) && node->isLeaf) { srched_node = (btree_srched_node*)malloc(sizeof(*srched_node)); srched_node->node = node; srched_node->pos = i; return srched_node; } else if(node->isLeaf) { return NULL; } else if ((i < node->num_key) && (key < node->key[i] ) && !node->isLeaf) { child = node->child[i]; return btree_search(child, key); } else if ((i == node->num_key) && (key >= node->key[--i] ) && !node->isLeaf) { child = node->child[++i]; return btree_search(child, key); } else if ((i < node->num_key) && (key == node->key[i] ) && !node->isLeaf) { child = node->child[++i]; return btree_search(child, key); } else { return NULL; } } /*create one empty B-TREE*/ void btree_create() { root = (btree_node*)malloc(sizeof(*root)); root->isLeaf = 1; root->isRoot = 1; root->num_key = 0; } /*insert one key into B-TREE, from tree root*/ void btree_insert_key(int key) { btree_node *node; if (root->num_key == (2 * BTREE_MIN_DEGREE) - 1) { node = (btree_node*)malloc(sizeof(*node)); if((root->num_key > 0) && root->child[0]) root->isLeaf = 0; else root->isLeaf = 1; root->isRoot = 0; node->isLeaf = 0; node->isRoot = 1; node->num_key = 0; node->child[0] = root; root = node; split_child(&node, -1, node->child[0]); insert_nonfull(root, key); } else { insert_nonfull(root, key); } } /*split child node, when walking throut down, and find child is full parent: parent node pos: position of parent node, in which subtree locate child: child node */ void split_child(btree_node **pparent, long pos, btree_node *child) { int j; btree_node *node; btree_node *parent = *pparent; node = (btree_node*)malloc(sizeof(*node)); node->isLeaf = child->isLeaf; node->parent = parent; child->parent = parent; child->num_key = BTREE_MIN_DEGREE - 1; if (child->isLeaf) { node->num_key = (2*BTREE_MIN_DEGREE - 1) - (BTREE_MIN_DEGREE - 1); child->r_sibling = node; node->l_sibling = child; for(j = 0; j < node->num_key; j++) { node->key[j] = child->key[BTREE_MIN_DEGREE-1+j]; } } else { node->num_key = (2*BTREE_MIN_DEGREE - 1) - (BTREE_MIN_DEGREE - 1) - 1; for(j = 0; j < node->num_key; j++) { node->key[j] = child->key[BTREE_MIN_DEGREE+j]; node->child[j] = child->child[BTREE_MIN_DEGREE+j]; node->child[j]->parent = node; } child->child[child->num_key]->r_sibling = NULL; node->child[j] = child->child[BTREE_MIN_DEGREE+j]; node->child[j]->parent = node; node->child[0]->l_sibling = NULL; } if(pos == -1) { parent->key[0] = child->key[BTREE_MIN_DEGREE-1]; parent->child[1] = node; parent->num_key++; } else { parent->key[pos] = child->key[BTREE_MIN_DEGREE-1]; for(j = parent->num_key-1; j > pos; j--) { parent->key[j+1] = parent->key[j]; } for(j = parent->num_key; j > pos; j--) { parent->child[j+1] = parent->child[j]; } parent->child[pos+1] = node; parent->num_key++; } } /*insert key into child node*/ void insert_nonfull(btree_node *node, int key) { int i; btree_node *n; i = node->num_key; if (node->isLeaf) { while (i >= 1 && (key < node->key[i-1])) { node->key[i] = node->key[i-1]; i--; } node->key[i] = key; node->num_key++; } else { while (i >= 1 && (key < node->key[i-1])) { i--; } n = node->child[i]; if (n->num_key == (2*BTREE_MIN_DEGREE - 1)) { split_child(&node, i, n); if (key > node->key[i]) { i++; } } insert_nonfull(node->child[i], key); } } /* delete one key from btree Datebase implementation. Third.Edition Introduction.to.Algorithms,.Second.Edition 1. If searched out key, a. node x has more than t - 1 keys, or key is root(it's leaf first). Just delete key from x. b. node x has less than t - 1 keys, but left sibing of x has more than t - 1 keys. Then copy up and copy right the max key from left sibling. And delete key from x. c. determine the root ci[x] of the appropriate subtree that must contain k, if k is in the tree at all. If ci[x] has only t - 1 keys, execute step 3a or 3b as necessary to guarantee that we descend to a node containing at least t keys. Then, finish by recursing on the appropriate child of x. 1). If ci[x] has only t - 1 keys but has an immediate sibling with at least t keys, give ci[x] an extra key by moving a key from x down into ci[x], moving a key from ci[x]'s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into ci[x]. 2). If ci[x] and both of ci[x]'s immediate siblings have t - 1 keys, merge ci[x] with one sibling, which involves moving a key from x down into the new merged node to become the median key for that node. 2. If no searched out key, nothing to do. */ void btree_delete_key(btree_node *node, int key) { // key postion int pos; int parentPos; btree_srched_node *srched_node = NULL; btree_node *n = NULL; btree_node *parent = NULL; btree_node *child = NULL; btree_node *l_sibling = NULL; btree_node *r_sibling = NULL; srched_node = btree_search(node, key); if(srched_node) { n = srched_node->node; pos = srched_node->pos; if((n->num_key > (BTREE_MIN_DEGREE - 1)) || (n->isRoot)) { delete_key(n, pos, NULL); return; } if(n->l_sibling) l_sibling = n->l_sibling; if(n->r_sibling) r_sibling = n->r_sibling; parent = n->parent; if(l_sibling && (l_sibling->num_key > (BTREE_M