The goal of this program is to get me comfortable with the fundamentals of database internals. By that, I mean the data structures (B-Tree, B+Tree, etc.), indexing, hashing, storage, and memory management. I aim to implement a basic non-relational database, starting with an in-memory approach and later adding persistence.
make: Compiles the source code.db.bin: The compiled executable binary.make run: Run the compiled executable binary.make leak: Runs the binary withvalgrindto check for memory leaks.make clean: Removes all generated build files and binaries.make test: Run all unit tests with valgrind checksmake test-single FILE="tests/test_crud_avl.c": Run single file of unit tests with valgrind cecks as well
Step 1: Deepen Understanding of Binary Search Trees (BST)
- Implement core BST operations:
- Insertion.
- Search.
- Deletion (delete node of 2 children not handled yet).
- Calculate the height of the tree.
- Implement level-order traversal (BFS) using a queue.
- Ignore duplicate values
- Implement functions to find the:
- Predecessor of a node.
- Successor of a node.
- Implement full functionally of Deletion using (Predecessor & Successor)
Step 2: Move to Balanced Trees
- Learn and implement AVL Trees:
- Add necessary methods (find, create, insert, height, balance, traversal, prec/suc, delete)
- Add rotations (left, right, left-right, right-left).
- Maintain height balancing after insertion/deletion.
- Create Unit tests
- Implement a Red-Black Tree:
- Add node coloring (red or black).
- Maintain balance after insertion/deletion.
- Handle edge cases like double-red or double-black.