← Articles

Systems Programming

AVL Trees C CRUD Data Structures

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

Part 5 of creating an in-memory record database in C. This article goes over the beginning stages of the search functionality and creation of the list sorted records feature.

Published Sep 11, 2026

In-Memory Record Database

Want to view this project? In-Memory Record Database

Creating Search and Sorting Features

Okay, let’s get into searching and sorting. Back in part 3, I showed you the createRecord function which contained getNextId.

enum InsertResult createRecord(struct RecordTable *table, const char *firstName, const char *lastName, int age)
{
    int nextId = getNextId(table);

    if (nextId == -1)
    {
        return INSERT_FAILED_GENERIC;
    }

    struct Record *record = malloc(sizeof(*record));

    if (record == NULL)
    {
        return INSERT_MEMORY_ERROR;
    }

I also showed you deleteRecord in part 4 where we saw the findRecordById function and the findRecord function.

enum DeleteResult deleteRecord(struct RecordTable *table, int id)
{
    struct Record *recordToDelete = findRecordById(table, id);

    if (recordToDelete == NULL)
    {
        return DELETE_FAILED;
    }

    struct Record *firstNameRecord = findRecord(&table->firstNameTree, recordToDelete);
    struct Record *lastNameRecord = findRecord(&table->lastNameTree, recordToDelete);
    struct Record *ageRecord = findRecord(&table->ageTree, recordToDelete);

    if (firstNameRecord != recordToDelete || lastNameRecord != recordToDelete || ageRecord != recordToDelete)
    {
        return DELETE_CORRUPTED;
    }

Once we implement these functions, we’ll nearly have all we need to complete this record database aside from editing records and letting the user search for records themselves. There’s a lot to do, so let’s begin with the functions that locate individual records.

Finding Individual Records

I’ll admit that it’s a bit confusing to have “finding” and “searching” in the same program, but they mean something completely different. Guess that goes to show you the importance of properly naming your functions! So what are we wanting to do when we call findRecord? You’re not going to believe this, but it’s something we’ve already done before:

struct Record *findRecord(const struct RecordAVLTree *tree, const struct Record *recordToFind)
{
    return findRecordInternal(tree->root, recordToFind, tree->comparator);
}

Oh no… another internal function? Yes, but don’t worry because this one is short and easy to follow. It’s also why I wanted to cover this one first because it gets deleteRecord complete and out of the way.

static struct Record *findRecordInternal(const struct RecordNode *root, const struct Record *recordToFind, RecordComparator comparator)
{
    struct Record *record;

    if (root == NULL)
    {
        return NULL;
    }

    int compareResult = comparator(recordToFind, root->record);

    if (compareResult < 0)
    {
        record = findRecordInternal(root->left, recordToFind, comparator);
    }
    else if (compareResult > 0)
    {
        record = findRecordInternal(root->right, recordToFind, comparator);
    }
    else
    {
        record = root->record;
    }

    return record;
}

As you can see, it’s nothing we haven’t done before. Do the NULL check, compare the two struct Record*s, and return the result once compareResult equals 0. So what about findRecordById? Simple. That just calls findRecord and utilizes the ID tree and a compound literal.

struct Record *findRecordById(const struct RecordTable *table, int id)
{
    return findRecord(&table->idTree, &(struct Record){.id = id});
}

Done and done. See? That wasn’t too bad right?

Search Setup and Listing Sorted Records

If you recall earlier way back in part 2, we created struct SearchResults which will hold pointers to all of the Record*s we find when searching by ID, first name, last name, or age as well as the count of Record*s we find.

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

Before we can go sticking stuff into an instance of struct SearchResults, we have to initialize it first as you can imagine. Let’s go ahead and create that function to use later.

enum SearchInitStatus initializeSearchResults(struct SearchResults *results, int count)
{
    results->records = NULL;
    results->count = 0;

    if (count == 0)
    {
        return INITIALIZATION_COMPLETE;
    }

    results->records = malloc(count * sizeof(struct Record *));

    if (results->records == NULL)
    {
        return INITIALIZATION_FAILED;
    }

    results->count = count;

    return INITIALIZATION_COMPLETE;
}

We’ll also do ourselves a favor and create a function that will free up the memory of the search results once we’re finished using it. For our purposes, we’re simply displaying the records on screen, so there’s no need to keep it in memory after we do that.

void freeSearchResults(struct SearchResults *results)
{
    free(results->records);

    results->records = NULL;
    results->count = 0;
}

With that complete, let’s get our count function created. We’ll use post-order traversal for this, but use whatever you like if it matters that much to you. It’s just counting after all.

static int countNodes(const struct RecordNode *root)
{
    if (root == NULL)
    {
        return 0;
    }

    int leftCount = countNodes(root->left);
    int rightCount = countNodes(root->right);

    return leftCount + rightCount + 1;
}

Now that we’ve counted the nodes, let’s go ahead and collect them. The traversal method for this one is more important since when we display them, we’d like them to be in order, so we’ll do exactly that with collectNodesInOrder.

static void collectNodesInOrder(const struct RecordNode *root, struct SearchResults *results, int *index)
{
    if (root == NULL)
    {
        return;
    }

    collectNodesInOrder(root->left, results, index);

    results->records[*index] = root->record;
    (*index)++;

    collectNodesInOrder(root->right, results, index);
}

With this created, we can make our function grabs the list of sorted records. In this function, we’re using a switch statement to decide which root to use from the 4 different AVL trees. Once we decide that, we’ll count the nodes, initialize our struct SearchResults *results, and collect the nodes using in-order traversal.

enum SearchResultStatus listRecordsSorted(const struct RecordTable *table, enum SortField sortField, struct SearchResults *results)
{
    const struct RecordNode *root;

    switch (sortField)
    {
    case SORT_ID:
        root = table->idTree.root;
        break;

    case SORT_FIRSTNAME:
        root = table->firstNameTree.root;
        break;

    case SORT_LASTNAME:
        root = table->lastNameTree.root;
        break;

    case SORT_AGE:
        root = table->ageTree.root;
        break;

    default:
        return SEARCH_FAILED;
    }

    int nodeCount = countNodes(root);

    enum SearchInitStatus initialized = initializeSearchResults(results, nodeCount);

    if (initialized == INITIALIZATION_FAILED)
    {
        return SEARCH_FAILED;
    }

    int index = 0;

    collectNodesInOrder(root, results, &index);

    return SEARCH_SUCCESS;
}

So with that function complete, we can finally figure out what getNextId does. We’ll check if a root exists in the ID tree first. We could add some extra checks in here to see if a root exists in all our trees if we’re worried about corrupted trees, but createRecord will tell us if that’s the case after we attempt to insert a record. After doing the NULL check, we’ll call our listRecordsSorted function and sort by ID. If the search is a success, we’ll simply grab the last ID in the results and increment it by 1. After this, we’ll use freeSearchResults to free up the memory that was allocated in initializeSearchResults.

int getNextId(const struct RecordTable *table)
{
    if (table->idTree.root == NULL)
    {
        return 0;
    }

    struct SearchResults results = {0};

    enum SearchResultStatus recordsSorted = listRecordsSorted(table, SORT_ID, &results);

    if (recordsSorted == SEARCH_SUCCESS)
    {
        int nodeCount = results.count;
        int nextId = results.records[nodeCount - 1]->id + 1;

        freeSearchResults(&results);

        return nextId;
    }

    freeSearchResults(&results);

    return -1;
}

One thing you might notice is this technically isn’t getting the next ID like most databases would.

This is under the assumption that you’re letting your database table auto-increment your IDs for you.

As you’re probably aware, the next ID technically is not the last existing ID plus 1 like we have here. Database systems keep internal counters of these IDs that way whenever you delete, say, the last record with an ID of 5 and then create a new one to replace it, the next ID will be 6 instead of 5 again. Our system here doesn’t account for this and I’ll admit, this is an oversight on my part that I’d like to change if I develop a database system using secondary storage. This isn’t to say that our table will break in this implementation, but it’s something to be aware of if you’re connecting this to other systems that depend on the ID. If we delete ID 5, then we should not reassign ID 5. Once it’s gone, it’s gone.

You should now have all that you need to get createRecord and deleteRecord functioning properly. The next article will finish up the list and searching functions.

← Back to Part 4 Continue to Part 6 →