From 111fde401ad32ceff815f0a5ea3ace650cce60b6 Mon Sep 17 00:00:00 2001
From: nasr <nsrddyn@gmail.com>
Date: Wed, 4 Mar 2026 20:22:50 +0000
Subject: feature(main): b-tree structure + thoughts and sources

---
 source/query/query.c    |  0
 source/query/query.h    |  0
 source/storage/b_tree.c | 34 ++++++++++++++++++++++++++++++++++
 source/storage/b_tree.h | 44 ++++++++++++++++++++++++++++++++++++++++++++
 source/storage/table.c  |  0
 source/storage/table.h  |  0
 sources.txt             | 12 ++++++++++++
 7 files changed, 90 insertions(+)
 create mode 100644 source/query/query.c
 create mode 100644 source/query/query.h
 create mode 100644 source/storage/b_tree.c
 create mode 100644 source/storage/b_tree.h
 create mode 100644 source/storage/table.c
 create mode 100644 source/storage/table.h
 create mode 100644 sources.txt

diff --git a/source/query/query.c b/source/query/query.c
new file mode 100644
index 0000000..e69de29
diff --git a/source/query/query.h b/source/query/query.h
new file mode 100644
index 0000000..e69de29
diff --git a/source/storage/b_tree.c b/source/storage/b_tree.c
new file mode 100644
index 0000000..4b42496
--- /dev/null
+++ b/source/storage/b_tree.c
@@ -0,0 +1,34 @@
+
+// TODO(nasr):
+// 1. splitting the tree when getting too big? (horizontally)
+// 2. joining trees?
+
+
+internal void
+b_tree_create(mem_arena *arena, u16 order)
+{
+
+
+}
+
+// NOTE(nasr): nodes that get  passed as parameters should've already been loaded into memory
+internal void
+b_tree_search(node *node)
+{
+
+
+}
+
+internal void
+b_tree_insert()
+{
+
+}
+
+internal void
+b_tree_write()
+{
+    // TODO(nasr): write the b_tree to disk
+}
+
+
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 */
diff --git a/source/storage/table.c b/source/storage/table.c
new file mode 100644
index 0000000..e69de29
diff --git a/source/storage/table.h b/source/storage/table.h
new file mode 100644
index 0000000..e69de29
diff --git a/sources.txt b/sources.txt
new file mode 100644
index 0000000..18b491b
--- /dev/null
+++ b/sources.txt
@@ -0,0 +1,12 @@
+ https://www.geeksforgeeks.org/dsa/introduction-of-b-tree-2/
+ github.com/tsoding/sv/blob/master/sv.h
+ https://github.com/semitrivial/csv_parser
+
+ Introduction to Algorithms, Fourth Edition
+ ISBN-10 : 026204630X
+ ISBN-13  : 978-0262046305
+
+ chapter 18: B-Trees
+
+
+ https://github.com/tidwall/btree.c/blob/master/btree.c
-- 
cgit v1.3