From 111fde401ad32ceff815f0a5ea3ace650cce60b6 Mon Sep 17 00:00:00 2001 From: nasr Date: Wed, 4 Mar 2026 20:22:50 +0000 Subject: feature(main): b-tree structure + thoughts and sources --- source/storage/b_tree.h | 44 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) create mode 100644 source/storage/b_tree.h (limited to 'source/storage/b_tree.h') diff --git a/source/storage/b_tree.h b/source/storage/b_tree.h new file mode 100644 index 0000000..10ad00d --- /dev/null +++ b/source/storage/b_tree.h @@ -0,0 +1,44 @@ +#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? +#define B_TREE_ORDER 4 + +typedef struct b_tree_node b_tree_node; +struct b_tree_node +{ + + // store the values + string8 keys[B_TREE_ORDER - 1]; + csv_row *rows[B_TREE_ORDER - 1]; + + b_tree_node *parent; + // handle to store children faster than linked list + // because now we can iteratate over the nodes instead of having cache misses + // when jumping through linked nodes + b_tree_node *children[B_TREE_ORDER]; + + // 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 + // i32 *refc; + + i32 key_count; + + b32 leaf; + +}; + +typedef struct b_tree b_tree; +struct b_tree +{ + // NOTE(nasr): make sure this always stays in memory + // so that initial fetch never requires a disk read + b_tree_node *root; + +}; + + + + +#endif /* BTREE_H */ -- cgit v1.3