28,7 → 28,7 |
|
/* |
* This B-tree has the following properties: |
* - it is a ballanced 2-3-4 tree (i.e. BTREE_M = 4) |
* - it is a ballanced 2-3-4-5 tree (i.e. BTREE_M = 5) |
* - values (i.e. pointers to values) are stored only in leaves |
* - leaves are linked in a list |
* - technically, it is a B+-tree (because of the previous properties) |
61,6 → 61,8 |
#define INDEX_NODE(n) ((n)->subtree[0] != NULL) |
#define LEAF_NODE(n) ((n)->subtree[0] == NULL) |
|
#define FILL_FACTOR ((BTREE_M-1)/2) |
|
#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2) |
#define MEDIAN_HIGH_INDEX(n) ((n)->keys/2) |
#define MEDIAN_LOW(n) ((n)->key[MEDIAN_LOW_INDEX((n))]); |
171,11 → 173,27 |
|
} |
|
/* TODO */ |
void btree_remove(btree_t *t, __native key) |
/** Remove B-tree node. |
* |
* @param B-tree. |
* @param key Key to be removed from the B-tree along with its associated value. |
* @param leaf_node If not NULL, pointer to the leaf node where the key is found. |
*/ |
void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node) |
{ |
btree_node_t *lnode; |
|
lnode = leaf_node; |
if (!lnode) { |
if (!btree_search(t, key, &lnode)) { |
panic("B-tree %P does not contain key %d\n", t, key); |
} |
} |
|
/* TODO */ |
|
} |
|
/** Search key in a B-tree. |
* |
* @param t B-tree. |