Step-by-Step B-Tree Implementation Guide for Database and File Systems

Core Concepts: Nodes, Order, and the "Wide" Advantage

Before we dive into the code, let's build a mental model. In a standard Binary Search Tree (BST), a node is tiny—it holds one key and points to two children. But in a B-Tree, we change the rules to suit the hardware.

Notice the difference? The BST is tall and thin. To find data, you have to read 20 separate pages from the disk. The B-Tree is short and wide. Because each node holds so many keys, we jump to the right child immediately, skipping thousands of possibilities in a single read.

Balance: Rotations vs. Splits

In a standard BST (like an AVL or Red-Black tree), keeping the tree balanced is expensive for disks. If you insert a node and the tree gets unbalanced, you perform rotations. Rotations change the structure of the tree by rewiring pointers. If those nodes are on different disk pages, you have to read and write multiple pages just to fix a small imbalance.

B-Trees solve this with Local Operations:

B-Tree Implementation: The Modular Roadmap

Now that we understand why B-Trees are structured this way, let's talk about how to build one. A common mistake beginners make is trying to write a single, massive function that does everything.

In reality, implementing a B-Tree is like assembling a toolkit. You build small, reusable tools (like split and merge) and then use them to build the bigger features (like insert and delete).

Your 5-Step Implementation Roadmap

Don't try to write the whole thing at once. Follow this order to keep your sanity:

Professor Pixel's Advice: Treat split and merge as pure utilities. They take a node and fix it. Your high-level insert and delete functions are just the managers that call these utilities when necessary.

Building the Initial Node Structure

Before we write complex logic for splitting or merging, we need to build the fundamental building block: the Node.

Think of a B-Tree node as a single page on a hard drive. It has a fixed size. To make sure our data fits perfectly into that page, we use a simple, rigid structure.

Now, let's look at the actual C code that defines this structure.

#define ORDER 5 // Example: max 4 keys, 5 children per node

typedef struct BTreeNode {
    int keys[ORDER - 1];           // Holds up to 4 keys (if ORDER=5)
    struct BTreeNode* children[ORDER]; // Pointers to 5 child pages
    int num_keys;                  // How many keys are currently used (0 to 4)
    bool is_leaf;                  // Is this a leaf node? (no children)
} BTreeNode;

Why Arrays? Why `num_keys`?

The Critical Pitfall: Initialization

When you allocate a new node (e.g., BTreeNode* node = malloc(sizeof(BTreeNode));), the memory contains garbage values. The `keys` array might have random integers, and `children` might point to random memory addresses. This is a latent crash bug.

You must explicitly initialize the node's state. Here is the safe way to do it:

BTreeNode* create_node() {
    BTreeNode* node = malloc(sizeof(BTreeNode));
    
    node->num_keys = 0;      // Start empty
    node->is_leaf = true;   // New nodes are leaves initially
    
    // CRITICAL: Initialize all child pointers to NULL
    for (int i = 0; i < ORDER; i++) {
        node->children[i] = NULL;
    }
    
    // keys[] don't strictly need zeroing if you only use indices < num_keys,
    // but it's safe to do so during debugging.
    return node;
}

Insertion Algorithm Intuition: The Top-Down Journey

Now we are ready to insert data. But before you write a single line of code, you must adopt the Golden Rule of B-Tree Insertion:

This is a top-down process. You start at the root and walk down to the leaf. At every step, you check the child you are about to visit. If it's full, you break it in half (split it) and promote the middle key up to your current node. This guarantees that by the time you reach a leaf, it has space for your new key.

Notice what happened in the visual? We didn't try to jam 15 into the full node. We split the node first, promoted 20 up, and then dropped 15 into the left side.

The Correct Pattern (The "Check-Then-Go" Rule)

This logic is so critical that it forms the core of your insertion function. You never just say insert(child, key). You say:

// Pseudocode for the correct insertion flow
void insert_nonfull(BTreeNode* node, int key) {
    int i = node->num_keys - 1;

    // 1. If leaf, just insert (we are guaranteed space here)
    if (node->is_leaf) {
        // ... shift keys and insert ...
    } 
    else {
        // 2. Find the child to descend into
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++; // Now i is the correct child index

        // 3. CRITICAL CHECK: Is the child full?
        if (node->children[i]->num_keys == ORDER - 1) {
            split_child(node, i); // FIX IT NOW
            
            // After split, we might need to move to the right child
            if (key > node->keys[i]) {
                i++;
            }
        }

        // 4. Now it's safe to descend
        insert_nonfull(node->children[i], key);
    }
}

Deletion: The Bottom-Up Challenge

If Insertion is a top-down, preemptive march, Deletion is a reactive, bottom-up cleanup.

In insertion, we fixed problems before we entered a node. In deletion, we remove a key and then check if the node broke the rules. If a node falls below the minimum number of keys (underflow), we must fix it immediately.

Notice the flow: The parent's key (20) didn't just disappear. It was promoted down to become the separator between the two children's data. The two children then merged into one solid block.

Borrowing vs. Merging

When a node underflows, we don't always have to merge. We follow a hierarchy of fixes:

// Simplified logic: Merge child[i] and child[i+1] under parent 'x'
void merge_child(BTreeNode* x, int i) {
    BTreeNode* left = x->children[i];
    BTreeNode* right = x->children[i+1];
    
    // 1. Move parent's key down to the left child
    left->keys[left->num_keys] = x->keys[i];
    left->num_keys++;
    
    // 2. Append right child's keys to left
    for (int j = 0; j < right->num_keys; j++) {
        left->keys[left->num_keys++] = right->keys[j];
    }
    
    // 3. Append right child's children pointers (if not leaf)
    for (int j = 0; j <= right->num_keys; j++) {
        left->children[left->num_keys] = right->children[j];
    }
    
    // 4. Remove the key and pointer from parent
    // (Shift arrays left to close the gap)
    x->num_keys--;
    // ... shift code omitted for brevity ...
    
    free(right); // Free memory
}

The "Domino Effect" (Cascading Underflow)

This is why deletion is often harder than insertion. Insertion is a one-way trip down. Deletion is a round trip: you go down to find the key, and you come back up fixing the damage.

Search Operation: The Art of the "Wide" Scan

Now that we understand the structure, let's talk about the most common operation: Search.

You already know that a B-Tree node is a disk page holding a sorted array of keys. The order M determines how many keys you examine per page read. Because the tree stays balanced—all leaves at the same depth—and each node is packed as full as possible, the number of levels (and thus disk I/Os) grows very slowly as you add more data.

Misconception: "Linear Scan is Slow"

It is true that within a single node, we scan its keys linearly (one by one) to decide which child to follow. Beginners often worry: "Isn't checking 100 keys one by one slow? Shouldn't we use binary search inside the node?"

The answer is usually no. Here is why:

The Search Algorithm

The logic is straightforward. You don't need complex recursion for the scanning part—just a loop.

BTreeNode* search(BTreeNode* node, int key) {
    int i = 0;
    
    // 1. Linear scan to find the first key >= search key
    // We stop as soon as we find a key that is bigger or equal
    while (i < node->num_keys && key > node->keys[i]) {
        i++;
    }
    
    // 2. If key is found at this node, return it
    if (i < node->num_keys && key == node->keys[i]) {
        return node; // Found!
    }
    
    // 3. If node is a leaf, key doesn't exist
    if (node->is_leaf) {
        return NULL;
    }
    
    // 4. Otherwise, descend into child[i] (Next Disk Read)
    return search(node->children[i], key);
}

Professor Pixel's Takeaway: B-Tree search efficiency comes from minimizing disk I/Os, not from avoiding linear scans within a page. The linear scan is not just acceptable—it's the simplest, most space-efficient way to use the keys you've already paid to load.

B-Tree Implementation in Database Indexing

Now that we understand the mechanics of the B-Tree, let's look at its most famous application: Database Indexing.

When a database creates an index on a column (like user_id), it isn't just sorting the data. It is building a separate, parallel structure stored on disk. This structure is the B-Tree.

The Critical Constraint: Page Size

In our earlier examples, we arbitrarily chose ORDER = 5. In a real database, you cannot choose the order arbitrarily.

The ORDER is mathematically determined by the Disk Page Size.

Here is how you would implement this calculation logic in C to ensure your node fits perfectly:

#define PAGE_SIZE 4096
#define HEADER_SIZE 16

// Helper to calculate max keys
int calculate_order(int key_size, int ptr_size) {
    // Available space for keys/pointers
    int available_space = PAGE_SIZE - HEADER_SIZE;
    
    // Each key takes 'key_size' bytes.
    // Each pointer takes 'ptr_size' bytes.
    // Note: A node with N keys has N+1 pointers.
    // We approximate by assuming equal distribution for simplicity.
    // A tighter bound is: N * key + (N+1) * ptr <= available
    // N * (key + ptr) + ptr <= available
    // N <= (available - ptr) / (key + ptr)
    
    int max_keys = (available_space - ptr_size) / (key_size + ptr_size);
    
    // Order M = Max Keys + 1 (Pointers)
    return max_keys + 1;
}

B-Tree Implementation in File System Data Structure

Now that we've seen how B-Trees power databases, let's look at where they live on your computer: the File System.

Modern file systems (like NTFS on Windows, ext4 on Linux, or APFS on macOS) don't store directories as simple lists. If you have a folder with 1 million files, a linear list would be unusable. Instead, they use B-Trees (or B+ Trees) to index those files.

Notice the difference? In a Linear List, the OS has to read every single file entry until it finds the one you want. In a B-Tree Directory, the OS reads the "Index Node" (the directory page), checks the keys (filenames), and jumps straight to the right block.

Keys, Values, and Inodes

The structure is identical to a database index, but the data types differ:

typedef struct DirEntry {
    // KEY: The filename (variable length string)
    // In reality, this is often packed efficiently to fit in the page
    char filename[255]; 

    // VALUE: The Inode Number (pointer to metadata)
    // This tells the OS where the actual file content lives on disk
    unsigned long long inode_number;

} DirEntry;

Professor Pixel's Note: Filenames are strings, not integers. Comparing strings is slower than comparing numbers. However, because the B-Tree is so shallow (often only 2 or 3 levels deep), the overhead of string comparison is negligible compared to the speed of jumping directly to the right file.

Misconception: "Does Caching Make B-Trees Irrelevant?"

This is a common trap. You might think: "Modern OSs have huge RAM. They cache everything. So if the directory is in RAM, does the B-Tree structure even matter?"

The answer is Yes, it matters even more. Here is why:

The B-Tree's design is a system-wide optimization. It aligns perfectly with how the OS manages memory (pages) and disk (blocks). By keeping the tree wide, we minimize the number of "jumps" the CPU has to make, whether those jumps are across a spinning disk or across a massive RAM array.

Conclusion and Next Steps

You've now seen the complete mental model for implementing a B-Tree tailored to disk-based storage. The core principles are:

Common Misconception: "Is this overkill?"

It is easy to think B-Trees are overkill for small datasets. "I have a 10,000-row table; a simple array or binary tree will be fine." This ignores the storage medium.

Detailed Next Steps

Now, build it. Follow this sequence to ensure your sanity:

You now understand why B-Trees are built this way. The next step is to let your hands learn through implementation. Start small, test constantly, and build confidence with each correct split and merge. You've got this.

Frequently Asked Questions

You've built the mental model. Now, let's tackle the tricky details that often trip up students and engineers alike. These are the questions I get asked most often in the lab.