Building an In-Memory Record Database in C (Part 2)

Want to view this project? In-Memory Record Database

Implementing the Record Table (...and other structs)

As with a lot of data structures, we have to implement a node struct that will allow this AVL tree to function in the first place. We should already have struct Record set up, so creating struct RecordNode is as simple as this:

struct RecordNode
{
    struct Record *record;
    struct RecordNode *left;
    struct RecordNode *right;
    int nodeHeight;
};

Here’s where we pivot from most implementations of binary search trees that you see in these courses. Take this implementation from GeeksforGeeks:

struct Node
{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
};

There’s nothing wrong with this code. In fact, it’s pretty much the exact same with one major difference: the key member. We have struct Record instead of int key, which will require some elbow grease on our end in order to get this to work properly with the other tree functions. You may be thinking, “Why not just utilize the ID member in struct Record?”

This COULD work, but we’d soon run into issues when we want to list records sorted by first name or search for records by age just to name a few. We wouldn’t notice these issues in a program like this where it’s doubtful to have more than 50 records, but let’s imagine that we have a million records and a performance problem becomes quite clear.

So that’s where yet another struct comes in: struct RecordAVLTree.

struct RecordAVLTree
{
    struct RecordNode *root;
    RecordComparator comparator;
};

This struct contains the root struct RecordNode and a RecordComparator datatype which we can define like so. We’ll come back to why this is important later.

typedef int (*RecordComparator)(const struct Record *, const struct Record *);

Finally, we’ll need the actual record table itself:

struct RecordTable
{
    struct RecordAVLTree idTree;
    struct RecordAVLTree firstNameTree;
    struct RecordAVLTree lastNameTree;
    struct RecordAVLTree ageTree;
};

Wait, so we’re creating a separate AVL tree for each column in our record table? Yep. That’s exactly what we’re doing. Each tree will be balanced based on their own key. This is technically what happens whenever you choose to create indexes for other columns aside from the primary key. A separate tree gets created for whatever column you choose to index which is why you’re told that indexing certain columns that you know you’ll be searching by a lot is more performative.

So now we have this base AVL tree indexed by ID associated with our Record table.

We can now have this AVL tree indexed by first name associated with the tree as well. We’ll get into what happens when there’s two or more people with the same first name later.

The same concept applies to last name as well as age.

So if we index all of our columns, we have a total of four trees that allow for performant searches and sorting. If we’re assuming we have 1 million records, we now have a worst case time complexity of O(log n) instead of O(n). Sure, you don’t HAVE to do it this way, but what sounds better: 1 million operations or 20 operations? Plus, it’s only four columns, so I don’t mind indexing all of them for the sake of this exercise.

The last struct we’ll define is struct SearchResults which will contain the search results of the records that we’re searching for. Who would’ve guessed?

struct SearchResults
{
    struct Record **records;
    int count;
};

We’re now ready to begin implementing some of the core functionality.