B-Tree in C: Insertion, Deletion and Search With a Tested Implementation

How B-trees stay shallow and balanced, with a tested C implementation, measured height and fill for a million keys, and the bugs deletion invites.

A three-level B-tree with many slots per node and all leaves on one level, with one search path from the root to a leaf highlighted, illustrating B-tree search

Put one million keys in a B-tree whose nodes hold up to 127 keys, and any of them can be found by reading at most 4 nodes. That property is why databases and file systems use B-trees: when every node read can be a disk page, the height of the tree is the cost of a lookup. The same tree also behaves predictably in another way. Insert the keys in ascending order and the nodes end up almost exactly half full; insert them in random order and they end up about 69% full, the figure a classic analysis by Andrew Yao predicts.

This guide explains how a B-tree works, from the minimum degree and node layout to search, insertion with node splits, and deletion with borrowing and merging. It implements all of it in C, measures how tall and full the tree gets with one million keys, and checks the code with model-based tests and nine deliberate mistakes. Every program was compiled and run for this article on Ubuntu 24.04 (x86-64) with GCC 13.3 and Clang 18.1.3 under -std=c11 and -std=c17, with -Wall -Wextra -pedantic -Werror and no warnings; the tests also run clean under AddressSanitizer, UndefinedBehaviorSanitizer and Valgrind, and every output block is captured verbatim. The same checks were repeated under WSL, and the code builds and passes its tests with MSVC 19.44 on Windows at /W4 /WX; the code is in a GitHub repository whose workflow repeats them on each commit.

What Is a B-Tree?

A B-tree is a self-balancing search tree in which each node holds many sorted keys and has one more child than it has keys. Every leaf sits at the same depth, and every node except the root stays at least half full, so a tree of n keys is only about logt n levels deep. That keeps searches, insertions and deletions fast even when each node is a disk page.

Rudolf Bayer and Edward McCreight described the B-tree in “Organization and Maintenance of Large Ordered Indexes”, published in Acta Informatica in 1972 (DOI 10.1007/BF00288683). The structure they designed for indexes on slow storage is still the default index in relational databases: PostgreSQL’s CREATE INDEX builds a B-tree unless told otherwise, and SQLite stores every table and index as a b-tree. Most databases use the B+ tree variant, compared further down.

This guide uses the minimum degree t from Cormen, Leiserson, Rivest and Stein’s Introduction to Algorithms, the most common textbook definition:

PropertyFor minimum degree t
Keys in a nodeAt most 2t − 1; at least t − 1, except the root, which needs only 1
Children of an internal nodeOne more than its keys: between t and 2t
LeavesAll at the same depth
Height for n keysAt most 1 + logt((n + 1) / 2) levels
t = 2A 2-3-4 tree: 1 to 3 keys and 2 to 4 children per node

Other books describe a B-tree by its order m, the maximum number of children, which is 2t here. The algorithms are the same.

How a B-Tree Works

Nodes and the Minimum Degree

Each node stores its keys in a sorted array, a value for each key, and child pointers. This implementation allocates a node and its three arrays in one block, sized for the tree’s minimum degree:

typedef struct node {
    int n;                  /* keys in use                                  */
    bool leaf;
    btree_key *keys;        /* keys[0..n-1], ascending; room for 2t-1       */
    btree_value *vals;      /* vals[i] belongs to keys[i]                   */
    struct node **child;    /* child[0..n] if not a leaf; room for 2t       */
} node;

struct btree {
    node *root;             /* NULL when the tree is empty */
    int t;                  /* minimum degree              */
    size_t count;
};

/* One allocation per node: the header, then the three arrays. */
static node *node_new(int t, bool leaf)
{
    size_t max_keys = (size_t)(2 * t - 1);
    node *x = malloc(sizeof *x + max_keys * (sizeof(btree_key) + sizeof(btree_value)) +
                     (max_keys + 1) * sizeof(node *));
    if (x == NULL)
        return NULL;
    x->n = 0;
    x->leaf = leaf;
    x->keys = (btree_key *)(x + 1);
    x->vals = (btree_value *)(x->keys + max_keys);
    x->child = (node **)(x->vals + max_keys);
    return x;
}

Inside a node, the keys are searched with a binary search that returns the first position whose key is not smaller than the target. The same function decides which child to follow:

/* The first position i with keys[i] >= key (binary search). */
static int lower_bound(const node *x, btree_key key)
{
    int lo = 0, hi = x->n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (x->keys[mid] < key)
            lo = mid + 1;
        else
            hi = mid;
    }
    return lo;
}

Searching a B-Tree

A search starts at the root and either finds the key in the current node or follows the child between the two keys that bracket it:

bool btree_search(const btree *tree, btree_key key, btree_value *value)
{
    const node *x = tree->root;
    while (x != NULL) {
        int i = lower_bound(x, key);
        if (i < x->n && x->keys[i] == key) {
            if (value != NULL)
                *value = x->vals[i];
            return true;
        }
        x = x->leaf ? NULL : x->child[i];
    }
    return false;
}

The loop runs once per level, so the cost of a search is the height of the tree, measured in nodes read. Within each node, a binary search over up to 2t − 1 keys costs about log2(2t) comparisons, cheap next to reading the node from disk.

Insertion: Split on the Way Down

New keys always go into a leaf. The difficulty is a full leaf: it cannot take another key, so it has to split into two nodes, and its middle key moves up into the parent. If the parent is full too, the split moves up again.

The approach here avoids that upward chain by splitting in advance. On the way down, every full node the insertion is about to enter is split first, so when the insertion reaches the leaf, the leaf has room and its parent can always take a median:

/* Splits the full child y = x->child[i] around its median key, which moves
 * up into x. y keeps the t-1 smaller keys; a new node z takes the t-1
 * larger ones. x must not be full. */
static bool split_child(node *x, int i, int t)
{
    node *y = x->child[i];
    node *z = node_new(t, y->leaf);
    if (z == NULL)
        return false;
    z->n = t - 1;
    memcpy(z->keys, y->keys + t, (size_t)(t - 1) * sizeof *z->keys);
    memcpy(z->vals, y->vals + t, (size_t)(t - 1) * sizeof *z->vals);
    if (!y->leaf)
        memcpy(z->child, y->child + t, (size_t)t * sizeof *z->child);
    y->n = t - 1;

    /* Open a gap at position i in x for the median and at i+1 for z. */
    memmove(x->child + i + 2, x->child + i + 1, (size_t)(x->n - i) * sizeof *x->child);
    memmove(x->keys + i + 1, x->keys + i, (size_t)(x->n - i) * sizeof *x->keys);
    memmove(x->vals + i + 1, x->vals + i, (size_t)(x->n - i) * sizeof *x->vals);
    x->child[i + 1] = z;
    x->keys[i] = y->keys[t - 1];
    x->vals[i] = y->vals[t - 1];
    x->n++;
    return true;
}

int btree_insert(btree *tree, btree_key key, btree_value value)
{
    int t = tree->t;
    if (tree->root == NULL && (tree->root = node_new(t, true)) == NULL)
        return -1;

    /* A full root splits first: this is the only way the tree grows taller. */
    if (tree->root->n == 2 * t - 1) {
        node *s = node_new(t, false);
        if (s == NULL)
            return -1;
        s->child[0] = tree->root;
        if (!split_child(s, 0, t)) {
            free(s);
            return -1;
        }
        tree->root = s;
    }

    /* Walk down, splitting every full child before entering it, so the
     * leaf at the bottom always has room. A key already in the tree is
     * met on the way and only its value changes. */
    node *x = tree->root;
    for (;;) {
        int i = lower_bound(x, key);
        if (i < x->n && x->keys[i] == key) {
            x->vals[i] = value;
            return 0;
        }
        if (x->leaf) {
            memmove(x->keys + i + 1, x->keys + i, (size_t)(x->n - i) * sizeof *x->keys);
            memmove(x->vals + i + 1, x->vals + i, (size_t)(x->n - i) * sizeof *x->vals);
            x->keys[i] = key;
            x->vals[i] = value;
            x->n++;
            tree->count++;
            return 1;
        }
        if (x->child[i]->n == 2 * t - 1) {
            if (!split_child(x, i, t))
                return -1;
            if (key == x->keys[i]) {            /* the median that moved up */
                x->vals[i] = value;
                return 0;
            }
            if (key > x->keys[i])
                ++i;
        }
        x = x->child[i];
    }
}

A full root splits like any other node, but its median becomes a new root. That is the only way a B-tree grows taller, and it is why every leaf stays at the same depth: the tree grows at the top, not at the bottom.

How a B-tree grows, and what a search reads 1. Insert 40 into a full node (t = 2: at most 3 keys per node) 10 20 30 before: the root is full split 20 10 30 40 after: 20 moves up into a new root, and the tree grows one level at the top 2. Search for 65 in the demo’s 18-key tree: 3 nodes read 50 10 20 30 80 1 5 12 15 25 33 35 55 60 65 85 90 95 Every leaf is at the same depth. Each node read narrows the search to one child, so the cost is the height of the tree: 3 reads here, where a perfectly balanced binary search tree of 18 keys needs up to 5.
Figure 1: Inserting into a full B-tree node splits it and moves its middle key up, which is how a B-tree grows taller; a search reads one node per level, three for the 18-key tree built by the demo program.

Deletion: Fix Up on the Way Down

Deleting is harder, because a node can fall below t − 1 keys. The method mirrors insertion: before the deletion enters a child, it makes sure the child has at least t keys, one more than the minimum, so removing a key from it can never cause an underflow. There are three ways to top up a child that has only t − 1 keys:

  1. Borrow from the left sibling if it has t keys or more: the separating key in the parent moves down into the child, and the sibling’s largest key moves up to replace it.
  2. Borrow from the right sibling the same way, in mirror image.
  3. Merge with a sibling when both have only t − 1 keys: the two siblings and the separating key from the parent become one node of 2t − 1 keys.
/* Makes sure x->child[i] has at least t keys before the deletion enters
 * it; returns the index of the child to enter (it changes after merging
 * with the left sibling). */
static int fill_child(node *x, int i, int t)
{
    if (x->child[i]->n >= t)
        return i;
    if (i > 0 && x->child[i - 1]->n >= t) {
        borrow_from_left(x, i);
    } else if (i < x->n && x->child[i + 1]->n >= t) {
        borrow_from_right(x, i);
    } else if (i < x->n) {
        merge_children(x, i);
    } else {
        merge_children(x, i - 1);
        --i;
    }
    return i;
}

/* Removes key from the subtree rooted at x, which has at least t keys
 * (or is the root). */
static bool remove_key(node *x, btree_key key, int t)
{
    for (;;) {
        int i = lower_bound(x, key);
        bool here = i < x->n && x->keys[i] == key;

        if (here && x->leaf) {                        /* case 1 */
            remove_from_node(x, i);
            return true;
        }
        if (here) {                                   /* case 2: internal node */
            node *y = x->child[i], *z = x->child[i + 1];
            if (y->n >= t) {                          /* 2a: use the predecessor */
                node *p = y;
                while (!p->leaf)
                    p = p->child[p->n];
                x->keys[i] = p->keys[p->n - 1];
                x->vals[i] = p->vals[p->n - 1];
                key = x->keys[i];
                x = y;
            } else if (z->n >= t) {                   /* 2b: use the successor */
                node *s = z;
                while (!s->leaf)
                    s = s->child[0];
                x->keys[i] = s->keys[0];
                x->vals[i] = s->vals[0];
                key = x->keys[i];
                x = z;
            } else {                                  /* 2c: merge, then go on */
                merge_children(x, i);
                x = y;
            }
            continue;
        }
        if (x->leaf)
            return false;                             /* not in the tree */
        x = x->child[fill_child(x, i, t)];            /* case 3 */
    }
}

bool btree_remove(btree *tree, btree_key key)
{
    if (tree->root == NULL)
        return false;
    /* One pass down; nodes on the path may be rebalanced even if the key
     * turns out to be absent, which leaves a valid tree. */
    bool removed = remove_key(tree->root, key, tree->t);
    if (removed)
        tree->count--;

    /* An empty root: the tree shrinks by one level, or becomes empty. */
    node *r = tree->root;
    if (r->n == 0) {
        tree->root = r->leaf ? NULL : r->child[0];
        free(r);
    }
    return removed;
}

When the key is found in an internal node, it cannot simply be removed, because it separates two subtrees. Case 2 replaces it with its predecessor (the largest key in the left subtree) or its successor (the smallest key in the right subtree), whichever side has a key to spare, and then deletes that key from the subtree instead. If neither side has a spare key, the two children are merged around it first.

A merge takes a key out of the parent. When the parent is the root and that was its only key, the root ends up empty, and btree_remove replaces it with its single child: the tree loses a level at the top, exactly where it gained one. The merge itself is short:

/* Merges child[i+1] and the separating key keys[i] into child[i]. Both
 * children have t-1 keys, so the result has exactly 2t-1. */
static void merge_children(node *x, int i)
{
    node *y = x->child[i], *z = x->child[i + 1];
    y->keys[y->n] = x->keys[i];
    y->vals[y->n] = x->vals[i];
    memcpy(y->keys + y->n + 1, z->keys, (size_t)z->n * sizeof *z->keys);
    memcpy(y->vals + y->n + 1, z->vals, (size_t)z->n * sizeof *z->vals);
    if (!y->leaf)
        memcpy(y->child + y->n + 1, z->child, (size_t)(z->n + 1) * sizeof *z->child);
    y->n += z->n + 1;
    remove_from_node(x, i);
    free(z);
}

Checking the Invariants

A B-tree that breaks one of its rules can still answer most searches correctly, so the tests use a checker that verifies every rule on the whole tree: key counts, order within each node, the range each subtree’s keys must fall in, and equal leaf depth.

/* Checks the subtree at x: key counts, order, bounds (lo, hi) given by the
 * ancestors' keys, and leaf depth. Counts keys into *keys. */
static const char *check_node(const node *x, int t, bool is_root, bool has_lo, btree_key lo,
                              bool has_hi, btree_key hi, int depth, int *leaf_depth, size_t *keys)
{
    if (x->n > 2 * t - 1)
        return "a node has more than 2t-1 keys";
    if (!is_root && x->n < t - 1)
        return "a node other than the root has fewer than t-1 keys";
    if (is_root && x->n < 1)
        return "the root of a non-empty tree has no keys";
    for (int i = 0; i < x->n; ++i) {
        if (i > 0 && x->keys[i - 1] >= x->keys[i])
            return "keys in a node are not in ascending order";
        if ((has_lo && x->keys[i] <= lo) || (has_hi && x->keys[i] >= hi))
            return "a key is outside the range its ancestors allow";
    }
    *keys += (size_t)x->n;
    if (x->leaf) {
        if (*leaf_depth < 0)
            *leaf_depth = depth;
        return *leaf_depth == depth ? NULL : "leaves are at different depths";
    }
    for (int i = 0; i <= x->n; ++i) {
        if (x->child[i] == NULL)
            return "an internal node is missing a child";
        const char *e = check_node(x->child[i], t, false, i > 0 || has_lo, i > 0 ? x->keys[i - 1] : lo,
                                   i < x->n || has_hi, i < x->n ? x->keys[i] : hi, depth + 1,
                                   leaf_depth, keys);
        if (e != NULL)
            return e;
    }
    return NULL;
}

Using the B-Tree in C

The header declares the whole interface: btree_create(t), btree_insert() (which replaces the value of an existing key), btree_search(), btree_remove(), btree_range() and btree_walk() for ordered traversal, statistics, btree_check() and btree_print(). This program builds a small tree with minimum degree 2 and exercises each operation:

/* btree_demo.c - builds a small B-tree of minimum degree 2 (a 2-3-4 tree),
 * prints it level by level, then searches, removes keys and runs a range
 * query, checking every invariant after each change.
 * Build: gcc -std=c11 -Wall -Wextra -pedantic btree_demo.c btree.c -o btree_demo */
#include <stdio.h>
#include <stdlib.h>

#include "btree.h"

static void print_key(btree_key key, btree_value value, void *ctx)
{
    (void)value;
    (void)ctx;
    printf(" %lld", (long long)key);
}

static void show(const btree *tree, const char *title)
{
    btree_stats s = btree_get_stats(tree);
    const char *problem = btree_check(tree);
    printf("%s: %zu keys, %zu nodes, height %d, %s\n", title, s.keys, s.nodes, s.height,
           problem == NULL ? "valid" : problem);
    btree_print(tree, stdout);
}

int main(void)
{
    static const btree_key keys[] = {50, 20, 80, 10, 30, 60, 90, 5, 15,
                                     25, 35, 55, 65, 85, 95, 1, 12, 33};
    btree *tree = btree_create(2);
    if (tree == NULL)
        return EXIT_FAILURE;
    for (size_t i = 0; i < sizeof keys / sizeof keys[0]; ++i)
        if (btree_insert(tree, keys[i], keys[i] * 10) < 0)
            return EXIT_FAILURE;
    show(tree, "After 18 inserts");

    btree_value v = 0;
    if (btree_search(tree, 65, &v))
        printf("search 65: found, value %lld, %d nodes read\n", (long long)v,
               btree_search_cost(tree, 65));
    printf("search 66: %s\n", btree_search(tree, 66, NULL) ? "found" : "not found");

    btree_remove(tree, 20);     /* a key in an internal node */
    btree_remove(tree, 1);      /* a key in a leaf */
    btree_remove(tree, 5);
    show(tree, "After removing 20, 1 and 5");

    printf("keys in [30, 60]:");
    size_t n = btree_range(tree, 30, 60, print_key, NULL);
    printf("  (%zu keys)\n", n);

    btree_destroy(tree);
    return 0;
}

Output:

After 18 inserts: 18 keys, 9 nodes, height 3, valid
[50]
[10 20 30] [80]
[1 5] [12 15] [25] [33 35] [55 60 65] [85 90 95]
search 65: found, value 650, 3 nodes read
search 66: not found
After removing 20, 1 and 5: 15 keys, 8 nodes, height 3, valid
[50]
[15 30] [80]
[10 12] [25] [33 35] [55 60 65] [85 90 95]
keys in [30, 60]: 30 33 35 50 55 60  (6 keys)

Eighteen keys fit in three levels, and the search for 65 reads one node per level. Removing 20, which sits in an internal node, replaced it with its predecessor 15, taken from the leaf [12 15]. Removing 5 then found its leaf at the minimum of one key, with no sibling to borrow from, so the leaf was merged with its neighbour and the parent [10 15 30] gave up a key to become [15 30]. The checker reports the tree valid after every change. The range query walks the keys in order, crossing from leaves into the root and back, which is what makes B-trees good at queries such as WHERE price BETWEEN 30 AND 60.

How Tall and How Full Does a B-Tree Get?

btree_shape inserts one million keys, once in random order and once in ascending order, into trees of five minimum degrees. For each it reports the height, the textbook upper bound on the height, the number of nodes, how full the nodes are on average, and the mean number of nodes a search reads over all one million keys:

1000000 keys
order         t  height   bound      nodes    full reads/search
random        2      16      19     570283   58.5%        15.43
random        4       9      10     216942   65.9%         8.78
random       16       5       5      46911   68.8%         4.95
random       64       4       4      11372   69.2%         3.99
random      256       3       3       2752   71.1%         3.00
ascending     2      19      19     999988   33.3%        18.00
ascending     4      10      10     333329   42.9%         9.67
ascending    16       5       5      66666   48.4%         4.93
ascending    64       4       4      15873   49.6%         3.98
ascending   256       3       3       3922   49.9%         3.00

Three things stand out.

  • Ascending order is the worst case for height. It reaches the bound exactly for every t. Random order stays below the bound for small t, three levels below it for the 2-3-4 tree, and meets it from t = 16 up, where the bound has almost no slack.
  • Ascending order leaves the nodes half full. Every split leaves t − 1 keys in the left node, and ascending keys never come back to it, so the fill matches (t − 1) / (2t − 1) to the printed decimal: 33.3% for t = 2, 42.9% for t = 4, 49.6% for t = 64.
  • Random order fills the nodes to about 69%. For t = 16 and t = 64 the measured fill is 68.8% and 69.2%. Andrew Yao’s analysis of B-trees under random insertions predicts about 69% (ln 2), which is still cited as the standard result, for example in a 2026 paper on B-tree fragmentation. Small trees are less full, because a node of three keys cannot be 69% full.

With t = 64, one million keys need only 4 levels, and an average search reads 3.99 nodes. A binary search tree holding the same keys has a node for every key and, even perfectly balanced, is 20 levels deep; built from ascending keys without rebalancing, it degenerates into a list one million nodes long, the case the binary trees guide measures.

Testing a B-Tree With a Model

Hand-written examples cannot reach the rare cases of deletion, such as a merge that empties the root after a borrow lower down. The tests therefore compare the B-tree with a model: a plain sorted array that does the same job slowly and obviously correctly. tests/test_btree.c runs random insertions, updates, searches and removals on both, checks that every result agrees, and runs btree_check() and a full in-order comparison. Each tree is then emptied in random order and must end with no nodes at all:

RunMinimum degreesOperationsKey rangeInvariants checked
Small2, 3, 4, 5, 8, 3220,000 each0 to 1,999After every operation
Large2, 3, 4, 5, 8, 32200,000 each0 to 49,999Every 5,000 operations

The small runs keep the tree small enough that merges, borrows and root changes happen constantly; the large runs reach deeper trees. With unit tests for empty trees, updates, range queries and the extreme keys INT64_MIN and INT64_MAX:

model-based runs passed: 12 of 12
unit checks failed: 0

Nine Mistakes That Break a B-Tree

tests/mutations.py puts nine plausible mistakes into copies of btree.c, one at a time, builds each copy with AddressSanitizer and UndefinedBehaviorSanitizer, and runs the tests. Sanitizer reports are summarized here as the error type and the first place in btree.c:

mistake                                              result
split leaves the median in the left node             caught: AddressSanitizer: heap-use-after-free in node_free (btree.c:43)
split moves the wrong children                       caught: AddressSanitizer: heap-use-after-free in lower_bound (btree.c:52)
only the root is split before inserting              caught: AddressSanitizer: heap-buffer-overflow in btree_insert (btree.c:175)
search finds the first key > k, not >= k             caught: FAILED line 171: btree_search(tree, 7, &v) && v == 700
deletion enters a child with only t-1 keys           caught: FAILED line 188: btree_check(tree) == NULL
predecessor copied up but not deleted                caught: t=2 op 343: a key is outside the range its ancestors allow
borrowing from the left forgets the child pointer    caught: AddressSanitizer: heap-use-after-free in node_free (btree.c:43)
merge with the left sibling enters the wrong child   caught: AddressSanitizer: heap-use-after-free in lower_bound (btree.c:52)
an empty root is kept                                caught: AddressSanitizer: SEGV in merge_children (btree.c:211)
mistakes the tests miss: 0

All nine were caught, but in two different ways, and the difference matters.

  • Three mistakes were caught by the checks themselves. A search that finds the first key greater than the target, instead of greater than or equal, misses keys that are present. Entering a child that has only t − 1 keys lets a node underflow, which btree_check() reports at once. Copying a predecessor up without deleting it leaves the key in the tree twice, and the range check fires 343 operations into a run.
  • Six mistakes corrupted memory before any check ran. A split that moves the wrong child pointers, a borrow that forgets one, or a root that is never shrunk leave pointers to freed or invalid memory, and AddressSanitizer stopped each run at the first access to freed or out-of-bounds memory. Without a sanitizer, the same bugs might crash, return wrong results, or appear to work.

The lesson for testing tree code in C is to use both: a checker for the structure’s rules, and a sanitizer for the memory those rules are built on.

How Fast Is a B-Tree in Memory?

How This Was Measured

SettingValue
Date testedNovember 10, 2026
HardwareCloud VM, 2 vCPUs, Intel Xeon @ 2.10 GHz
Operating systemUbuntu 24.04.5 LTS, x86-64
CompilerGCC 13.3.0, CMake Release build (-O3 -DNDEBUG)
Input1,000,000 pseudo-random 63-bit keys from a fixed seed, all distinct
What is timedInserting all keys into an empty tree; then searching for each (in reverse order); then removing each. Creating the key array is excluded
Baselinebsearch() over the same keys in a sorted array, search only
StatisticMedian of 5 runs, in nanoseconds per operation
CheckEvery search must find its key; the program prints the count

All figures come from one machine, single-threaded, with no CPU pinning or frequency-scaling control and no percentiles. A first run the same day differed by up to 18% for t = 2 and by under 10% for t = 16 and above. The tree lives entirely in memory, so the numbers measure CPU cache behaviour, not disk reads.

1000000 random keys, median of 5 runs, ns per operation
structure                insert   search   remove
B-tree, t = 2              1035     1108     1017
B-tree, t = 4               437      526      549
B-tree, t = 8               330      380      379
B-tree, t = 16              274      312      306
B-tree, t = 32              263      270      281
B-tree, t = 64              251      265      294
B-tree, t = 128             288      273      305
B-tree, t = 256             330      264      352
sorted array, bsearch         -      204        -
searches that found their key: 1000000 of 1000000

Even in memory, wide nodes win. A 2-3-4 tree (t = 2) takes about four times as long per operation as a tree with t = 32 or 64, because each of its 16 levels is a separate node somewhere in memory, and most of those reads miss the CPU cache. With t between 32 and 128, a search costs about 265 to 275 ns, about a third slower than a binary search over a plain sorted array. The array is the most compact layout possible, but inserting into it means moving, on average, half of its elements. Above t = 128, the time spent shifting keys inside each node on insertion and deletion starts to grow again.

B-Tree vs Binary Search Tree vs B+ Tree

AspectBinary search treeB-treeB+ tree
Keys per node1t − 1 to 2t − 1Same as a B-tree, for its fan-out
Height for 1,000,000 keys20 at best; up to 1,000,000 unbalanced4 with t = 64 (measured above)Similar to a B-tree
Where values liveIn every nodeIn every nodeOnly in the leaves; internal nodes hold copies of keys
Range scansIn-order traversalIn-order traversal across levelsAlong a linked list of leaves
BalanceNone, unless it is an AVL or red-black treeAlways balancedAlways balanced
Typical useIn-memory mapsIn-memory indexes, teachingDatabase and file-system indexes

A B+ tree keeps internal nodes small, because they hold only keys and child pointers, so more of them fit in a page and the tree is shallower. Its leaves are chained in a linked list, so a range scan reads the leaves in order without climbing the tree. The splitting and merging logic is the same as in the B-tree on this page.

Key Takeaways

  • A B-tree keeps between t − 1 and 2t − 1 keys in each node and every leaf at the same depth, so its height grows with logt n: 4 levels for one million keys with t = 64.
  • Insertion splits full nodes on the way down, and the tree grows only at the root, which is why it stays balanced.
  • Deletion tops up every child before entering it, by borrowing from a sibling or merging with one, and the tree shrinks only at the root.
  • Random insertions leave nodes about 69% full and ascending ones about 50%, matching Yao’s analysis and the split arithmetic.
  • Test tree code against a simple model and with a sanitizer: of nine deliberate mistakes, three were caught by the invariant checks and six by AddressSanitizer.
  • Wide nodes are faster even in memory: t = 32 to 128 ran about four times faster than a 2-3-4 tree, and searched only about a third slower than binary search over a sorted array.

Frequently Asked Questions

Conclusion

The B-tree has outlived almost every other data structure from its era because it is built around one fact that has not changed: reading one large block costs about the same as reading one small one. Packing many keys into each node, splitting on the way down and merging on the way down are all consequences of that, and the result is a tree that never needs a separate rebalancing pass.

The code is short for what it does, but deletion has enough cases that a confident implementation can still be wrong in ways a few examples never reveal. A slow, obviously correct model, an invariant checker and a sanitizer together are what make it trustworthy, and the same three tools work for any other structure in the data structures section.

Source Code and Tests

B-Tree build status

All programs on this page are in the data-structures/b-tree directory of the MYCPLUS C examples repository.

Build and test:

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

What the build checks. It compiles with GCC and Clang under C11 and C17 on Linux and with MSVC /W4 /WX on Windows, treating warnings as errors. CTest runs the unit tests and the 12 model-based runs, and checks that the demo and the one-million-key shape statistics print exactly the outputs on this page. On Linux the workflow also runs everything under AddressSanitizer and UndefinedBehaviorSanitizer and checks that each of the nine mutations makes the tests fail. It does not run the benchmark, whose figures came from one machine.

What I Verified

The example directory contains run_all.sh for Ubuntu and WSL and run_all.ps1 for Windows, which run every check below and print one line per row.

CheckUbuntu 24.04WSL (Ubuntu)Windows (MSVC)
Build and CTest, GCC 13.3, C11 and C17PassPassNot applicable
Build and CTest, Clang 18.1.3, C11 and C17PassPassNot applicable
Build with MSVC 19.44 /W4 /WX and CTestNot applicableNot applicablePass (3 of 3 tests)
12 model-based runs and unit testsPass (12 of 12, 0 failed)PassPass
AddressSanitizer and UndefinedBehaviorSanitizerPass (GCC)Pass (GCC)Not applicable
Valgrind on the full test suitePass (0 errors, no leaks)PassNot applicable
Nine mutations, each makes the tests failPass (9 of 9)PassNot applicable
BenchmarkRun twice, second run aboveNot runNot run

Environments: Ubuntu 24.04.5 on a cloud VM; Ubuntu 24.04.5 under WSL2 (kernel 5.15) with GCC 13.3 and Clang 18.1.3; Windows build 26300 with Visual Studio 2022 17.14 (MSVC 19.44).

Not covered: 32-bit builds, compilers newer than GCC 13.3 and Clang 18.1.3, Clang’s sanitizers (they run only in CI), timing on any other machine, and a disk-based tree: every node here is in memory.

Scroll to Top