Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A B+-tree implementation with find, insert and delete in 176 lines of code.
enum { BMAX = 32, BMIN = BMAX / 2, BHEIGHT = 6 };
struct BNode {
uint32_t length;
Key keys[BMAX];
union {
BNode *children[BMAX];
Value values[BMAX];
};
};
static void BNode_Initialize(BNode *node, uint32_t length, Key *keys, void *children) {
node->length = length;
CopyMemory(node->keys, keys, length * sizeof(Key));
CopyMemory(node->children, children, length * sizeof(BNode *));
}
static BNode *BNode_Create(uint32_t length, Key *keys, void *children) {
BNode *node = (BNode *)Allocate(sizeof(BNode));
BNode_Initialize(node, length, keys, children);
return node;
}
static void BNode_Destroy(BNode *node, uint32_t height) {
for (uint32_t index = 0; index < node->length; index++) {
if (height > 1) {
BNode_Destroy(node->children[index], height - 1);
}
Free(node->children[index]);
}
}
static INLINE Key BNode_GetMaxKey(BNode *node) {
Assert(node->length > 0);
return node->keys[node->length - 1];
}
static BNode *BNodeLeaf_Insert(BNode *leaf, Key key, Value value) {
uint32_t index = SearchKeys(leaf->keys, leaf->length, key);
if (index < leaf->length && leaf->keys[index] == key) {
leaf->values[index] = value;
return 0;
}
BNode *new_sibling = 0;
if (leaf->length == BMAX) {
new_sibling = BNode_Create(BMIN, leaf->keys + BMIN, leaf->values + BMIN);
leaf->length = BMIN;
if (index >= BMIN) {
leaf = new_sibling;
index -= BMIN;
}
}
Array_Insert(leaf->keys, leaf->length, index, key);
Array_Insert(leaf->values, leaf->length, index, value);
leaf->length++;
return new_sibling;
}
static BNode *BNode_Insert(BNode *node, Key key, Value value, uint32_t height) {
Assert(height > 0);
Assert(node->length > 0);
uint32_t index = SearchKeys(node->keys, node->length, key);
if (index == node->length) {
index--;
node->keys[index] = key;
}
BNode *new_child;
if (height == 1) {
new_child = BNodeLeaf_Insert(node->children[index], key, value);
} else {
new_child = BNode_Insert(node->children[index], key, value, height - 1);
}
BNode *new_sibling = 0;
if (new_child) {
if (node->length == BMAX) {
new_sibling = BNode_Create(BMIN, node->keys + BMIN, node->children + BMIN);
node->length = BMIN;
if (index >= BMIN) {
node = new_sibling;
index -= BMIN;
}
}
node->keys[index] = BNode_GetMaxKey(node->children[index]);
Array_Insert(node->keys, node->length, index + 1, BNode_GetMaxKey(new_child));
Array_Insert(node->children, node->length, index + 1, new_child);
node->length++;
}
return new_sibling;
}
static bool BNodeLeaf_Delete(BNode *leaf, Key key) {
uint32_t index = SearchKeys(leaf->keys, leaf->length, key);
if (index < leaf->length && leaf->keys[index] == key) {
Array_Delete(leaf->keys, leaf->length, index);
Array_Delete(leaf->values, leaf->length, index);
leaf->length--;
return leaf->length == 0;
}
return false;
}
static void BNode_Delete(BNode *node, Key key, uint32_t height) {
Assert(height > 0);
uint32_t index = SearchKeys(node->keys, node->length, key);
if (index < node->length) {
if (height == 1) {
if (BNodeLeaf_Delete(node->children[index], key) && node->length > 1) {
Free(node->children[index]);
Array_Delete(node->keys, node->length, index);
Array_Delete(node->children, node->length, index);
node->length--;
}
} else {
BNode_Delete(node->children[index], key, height - 1);
}
}
}
struct BTree {
uint32_t height;
BNode root;
};
void BTree_Initialize(BTree *tree) {
Assert(BMAX == 2 * BMIN);
Assert(sizeof(BNode *) == sizeof(Value));
tree->height = 0;
tree->root.length = 0;
}
void BTree_Destroy(BTree *tree) {
if (tree->height > 0) {
BNode_Destroy(&tree->root, tree->height);
}
}
Value *BTree_Find(BTree *tree, Key key) {
uint32_t height = tree->height;
BNode *node = &tree->root;
for (;;) {
uint32_t index = SearchKeys(node->keys, node->length, key);
if (index == node->length) {
return 0;
}
if (height == 0) {
return (node->keys[index] == key) ? (node->values + index) : 0;
}
height--;
node = node->children[index];
}
}
void BTree_Insert(BTree *tree, Key key, Value value) {
BNode *root = &tree->root;
BNode *new_root_sibling;
if (tree->height == 0) {
new_root_sibling = BNodeLeaf_Insert(root, key, value);
} else {
new_root_sibling = BNode_Insert(root, key, value, tree->height);
}
if (new_root_sibling) {
BNode *old_root = BNode_Create(root->length, root->keys, root->children);
Key keys[2] = {BNode_GetMaxKey(old_root), BNode_GetMaxKey(new_root_sibling)};
BNode *children[2] = {old_root, new_root_sibling};
BNode_Initialize(root, 2, keys, children);
tree->height++;
}
}
void BTree_Delete(BTree *tree, Key key) {
if (tree->height == 0) {
BNodeLeaf_Delete(&tree->root, key);
} else {
BNode_Delete(&tree->root, key, tree->height);
}
}
@fulldecent

This comment has been minimized.

Copy link

@fulldecent fulldecent commented Apr 28, 2020

How will BHEIGHT be used?

@dicroce

This comment has been minimized.

Copy link

@dicroce dicroce commented Apr 28, 2020

Where is the header file for this? keys in BNode doesn't compile without it...

@pervognsen

This comment has been minimized.

Copy link
Owner Author

@pervognsen pervognsen commented Apr 28, 2020

I think the non-excerpt version is here: https://gist.github.com/pervognsen/e7883b3de183fcd601c1edf7f7e9508b. This Gist was just an excerpt showing that the core B-tree operations can be implemented in very few lines of code, unlike what you see in most libraries.

Anyway, I should make it very clear that no code I ever post as a Gist is intended as a "library" or as a drop-in implementation. It's an example implementation and in some cases I don't even pretend that the code is tested (though the B-tree code was pretty heavily stress tested but I'm not sure if that version is the one posted as the Gist). If you just want a drop-in B-tree library, you have plenty of options.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.