Building a Simple Database using Data Structures in C

Table of Contents

1. Fundamental Concepts
2. Data Structures for Database
3. Building the Database
4. Usage Methods
5. Common Practices
6. Best Practices
7. Conclusion
8. References

Fundamental Concepts

A database is an organized collection of data. In the context of our simple database in C, we will focus on the following fundamental concepts:

• Data Storage: We need a way to store data in memory or on disk. Data structures like arrays, linked lists, and trees can be used for in - memory storage, while files can be used for persistent storage on disk.
• Data Retrieval: Once the data is stored, we need to be able to retrieve it based on certain criteria. This involves searching through the data structures efficiently.
• Data Manipulation: We should be able to insert, update, and delete data from the database.

Data Structures for Database

Arrays

Arrays are a simple and straightforward data structure. They provide direct access to elements using an index. However, they have a fixed size, which can be a limitation when the amount of data is not known in advance.

#include <stdio.h>

#define MAX_RECORDS 100

typedef struct {
    int id;
    char name[50];
} Record;

Record database[MAX_RECORDS];
int recordCount = 0;

Linked Lists

Linked lists are dynamic data structures that can grow or shrink as needed. Each node in a linked list contains data and a pointer to the next node.

#include <stdio.h>
#include <stdlib.h>

typedef struct Record {
    int id;
    char name[50];
    struct Record *next;
} Record;

Record *head = NULL;

void insertRecord(int id, const char *name) {
    Record *newRecord = (Record *)malloc(sizeof(Record));
    newRecord->id = id;
    snprintf(newRecord->name, sizeof(newRecord->name), "%s", name);
    newRecord->next = head;
    head = newRecord;
}

Binary Search Trees

Binary search trees are efficient for searching, insertion, and deletion operations. Each node in a binary search tree has at most two children, and the left subtree of a node contains only nodes with keys less than the node’s key, while the right subtree contains only nodes with keys greater than the node’s key.

#include <stdio.h>
#include <stdlib.h>

typedef struct Record {
    int id;
    char name[50];
    struct Record *left;
    struct Record *right;
} Record;

Record *root = NULL;

Record* insert(Record *node, int id, const char *name) {
    if (node == NULL) {
        Record *newRecord = (Record *)malloc(sizeof(Record));
        newRecord->id = id;
        snprintf(newRecord->name, sizeof(newRecord->name), "%s", name);
        newRecord->left = newRecord->right = NULL;
        return newRecord;
    }

    if (id < node->id)
        node->left = insert(node->left, id, name);
    else if (id > node->id)
        node->right = insert(node->right, id, name);

    return node;
}

Building the Database

Let’s build a simple database using a linked list. We will create functions to insert, search, and delete records.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Record {
    int id;
    char name[50];
    struct Record *next;
} Record;

Record *head = NULL;

// Insert a new record
void insertRecord(int id, const char *name) {
    Record *newRecord = (Record *)malloc(sizeof(Record));
    newRecord->id = id;
    strcpy(newRecord->name, name);
    newRecord->next = head;
    head = newRecord;
}

// Search for a record by id
Record* searchRecord(int id) {
    Record *current = head;
    while (current != NULL) {
        if (current->id == id) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

// Delete a record by id
void deleteRecord(int id) {
    Record *current = head;
    Record *previous = NULL;

    while (current != NULL && current->id != id) {
        previous = current;
        current = current->next;
    }

    if (current == NULL) return;

    if (previous == NULL) {
        head = current->next;
    } else {
        previous->next = current->next;
    }
    free(current);
}

// Print all records
void printRecords() {
    Record *current = head;
    while (current != NULL) {
        printf("ID: %d, Name: %s\n", current->id, current->name);
        current = current->next;
    }
}

Usage Methods

Here is how you can use the database functions:

int main() {
    insertRecord(1, "Alice");
    insertRecord(2, "Bob");
    insertRecord(3, "Charlie");

    printf("All records:\n");
    printRecords();

    Record *found = searchRecord(2);
    if (found != NULL) {
        printf("Found record: ID: %d, Name: %s\n", found->id, found->name);
    } else {
        printf("Record not found.\n");
    }

    deleteRecord(2);
    printf("Records after deletion:\n");
    printRecords();

    return 0;
}

Common Practices

• Error Handling: Always check for memory allocation errors when using malloc or other dynamic memory allocation functions.
• Data Validation: Validate user input to ensure that the data inserted into the database is in the correct format.
• Memory Management: Free any dynamically allocated memory to avoid memory leaks.

Best Practices

• Code Modularity: Break the database code into smaller functions for better readability and maintainability.
• Use of Comments: Add comments to explain the purpose of each function and important code segments.
• Testing: Write test cases to verify the correctness of the database operations.

Conclusion

Building a simple database using data structures in C is a great way to understand the underlying principles of data storage and retrieval. By using data structures like arrays, linked lists, and binary search trees, we can create a basic database system with insert, search, and delete functionality. Remember to follow common practices and best practices to ensure the reliability and maintainability of your code.

References

• “The C Programming Language” by Brian W. Kernighan and Dennis M. Ritchie
• Online tutorials on data structures and algorithms in C

This blog post provides a starting point for building more complex database systems. You can further expand the functionality by adding features like data persistence, indexing, and concurrency control.