From a9cb228861a6b0fad4d508c05c0614757a7f0a34 Mon Sep 17 00:00:00 2001 From: nasr Date: Mon, 13 Apr 2026 14:58:49 +0200 Subject: refactor(main): refactor directory structure --- source/tb_db/btree_impl.h | 209 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 209 insertions(+) create mode 100644 source/tb_db/btree_impl.h (limited to 'source/tb_db/btree_impl.h') diff --git a/source/tb_db/btree_impl.h b/source/tb_db/btree_impl.h new file mode 100644 index 0000000..b7015bd --- /dev/null +++ b/source/tb_db/btree_impl.h @@ -0,0 +1,209 @@ +/** + * >> api notes + * >> by Abdellah El Morabit + * + * - creation of a btree happens when doing an insertion on an + * empty btree where the root is null or nil + * + **/ + +/* single header b-tree implementation by Abdellah El Morabit */ +#ifndef BTREE_H +#define BTREE_H + +// maximum height of the tree the lower the lower the lower amount +// of disk reads which translates into faster? +#if 0 +global_variable read_only s16 btree_ORDER = 4; +#endif +#define BTREE_ORDER 4 + +//- NOTE(nasr): defining a key to improve sorting +// i think saying that a key is a combination of the column + row is a good way of appraoching this +typedef struct key key; +struct key +{ + s32 header_index; //- col number + s32 row_index; +}; + +typedef struct btree_node btree_node; +struct btree_node +{ + // store the key values of the sub nodes? if they are leaves? + key keys[BTREE_ORDER - 1]; + // TODO(nasr): replace with something more generic? + // NOTE(nasr): cons of void * -> no type safety + // is there a way to still have some sort of that? size not variable + void *payload_per_key[BTREE_ORDER - 1]; + btree_node *parent; + // handle to store children faster than linked list + // because now we can iterate over the nodes instead of having cache misses + // when jumping through linked nodes + btree_node *children[BTREE_ORDER]; + // this shouldn't change things but could be a performance improvement on a bigger scale?? + s32 *max_children; + // NOTE(nasr): reference count ::: check how many leaves are using this node + // also not needed for now because we don't free individual node because of arena allocator + // s32 *refc; + s32 key_count; + b32 leaf; + + + // NOTE(nasr): do we hold the reference to the arena? or do we pass is it as a reference? + // this could solve memory location issues? +}; + + +typedef struct btree btree; +struct btree +{ + // NOTE(nasr): make sure this always stays in memory + // so that initial fetch never requires a disk read + btree_node *root; +}; + + + +#ifdef BTREE_IMPLEMENTATION +/////////////////////////////////////////////////////////////////////////////// +//- btree.c + + +internal b32 +is_nil_btree_node(btree_node *node) +{ + // NOTE(nasr): looks like a useless function but could be usefull when we implement a nil_btree_node + return (node == NULL); +} + +// TODO(nasr): 1. splitting the tree when getting too big? (horizontally) 2. joining trees? + +internal b8 +key_compare(key destination_key, key source_key) +{ + s32 source_index = source_key.header_index + source_key.row_index; + s32 destination_index = destination_key.header_index + destination_key.row_index; + + if(destination_index > source_index) return 1; + else if(destination_index < source_index) return -1; + else return 0; +} + +// NOTE(nasr): @return the index of the found element +//- @param: start node could be the root node for all we care. but this enables optimizations in the future if we need them +internal s32 +btree_find_ipos(key k, btree_node *start_node) +{ + s32 index = 0; + // scan right while the node's key at [index] is strictly less than k + while (index < start_node->key_count && key_compare(start_node->keys[index], k) < 0) + { + ++index; + } + return index; +} + +// NOTE(nasr): nodes that get passed as parameters should've already been loaded into memory +internal void * +btree_search(btree_node *node, key key) +{ + s32 index = btree_find_ipos(key, node); + + if (index < node->key_count && key_compare(node->keys[index], key) == 0) + { + return node->payload_per_key[index]; + } + if (node->leaf) + { + return NULL; + } + return btree_search(node->children[index], key); +} + +// TODO(nasr): split node when key_count == btree_ORDER - 1 (node is full) +// -- each node has max btree_ORDER - 1 keys +// +internal void +btree_insert(mem_arena *arena, btree *tree, key key, void *payload) +{ + if(is_nil_btree_node(tree->root)) + { + tree->root = PushStructZero(arena, btree_node); + tree->root->leaf = 1; + tree->root->key_count = 0; + } + + btree_node *current_node = tree->root; + + if (current_node->leaf) + { + // find the insertion position and shift keys right to make room + //- after: but what is this. we are expecting a new key.but we are looking for + //- its position in the tree is useless because it's non existent + + s32 i = btree_find_ipos(key, current_node); + + for (s32 j = current_node->key_count; j > i; --j) + { + current_node->keys[j] = current_node->keys[j - 1]; + current_node->payload_per_key[j] = current_node->payload_per_key[j - 1]; + } + + current_node->keys[i] = key; + current_node->payload_per_key[i] = payload; + + if(current_node->key_count < (BTREE_ORDER - 1)) + { + current_node->key_count += 1; + } + else { + // TODO(nasr): creating a new branch / tree? + // make a seperate function for this + // NOTE(nasr): only split through the parent when one actually exists; + // root splits need to be handled separately (promote mid key, create two children) + if(current_node->parent != NULL) + { + s32 split_pos = current_node->parent->key_count / 2 - 1; + s32 updated_keycount_p = 0; + for(s32 index = 0; index <= split_pos; ++index) + { + ++updated_keycount_p; + } + current_node->parent->key_count = updated_keycount_p; + } + } + } + // TODO(nasr): internal node case walk down then split on the way back up +} + + +internal void +btree_write(btree *bt) +{ + unused(bt); +#if 0 + temp_arena *temp_arena = temp_arena_begin(arena); + btree_node *root = bt->root; + + for(btree_node *bt = PushStruct(arena); root->next; next = root;) + { + + } + + temp_arena_end(temp); +#endif +} + +// - load the entire db into memory. +#if 0 +internal void +btree_load(mem_arena *arena) +{ + + +} +#endif + +#endif /* BTREE_IMPLEMENTATION */ +#endif /* BTREE_H */ -- cgit v1.3