B-tree

Prerequisites

• Binary search tree.
• Binary search or a scan inside a sorted array.
• Logarithms in other bases: $\log_{100} n$.

The analogy

How it works

Start with insertions by hand

Here each node holds at most 3 keys (a 2-3-4 tree). A full node splits: its middle key moves up into the parent. Insert 10, 20, 30, 40, 50, 60. Predict, then open "Check".

Finish the picture: why all leaves stay level

Look at what splitting does to the shape.

• Splitting a leaf. Predict: does it make that branch deeper than the others?
  Check

  No. The two halves stay at the same depth; only the parent gains a key.

• Splitting the root. Predict what happens to the depth of every leaf.
  Check

  Every leaf gets one level deeper at the same time, because the new root sits above them all. So all leaves are always at the same depth.

The rule in plain words

A node holds sorted keys, and between each pair of keys there is a child pointer to the values in that range. Every node except the root is at least half full.

Search: find the right range in the node, go down. Insert: add to a leaf; if it overflows, split it and push the middle key up, which may split the parent too.

The code

Read this code after you have done the insertions by hand. It will make more sense.

typedef struct BNode { int n; int key[3]; struct BNode *child[4]; int leaf; } BNode;

BNode *btree_search(BNode *x, int k) {          /* returns the node holding k, or NULL */
    while (x) {
        int i = 0;
        while (i < x->n && k > x->key[i]) i++;   /* first key >= k */
        if (i < x->n && k == x->key[i]) return x;
        if (x->leaf) return NULL;
        x = x->child[i];                        /* go down between keys */
    }
    return NULL;
}

void split_child(BNode *x, int i) {             /* x->child[i] is full (3 keys) */
    BNode *y = x->child[i];
    BNode *z = malloc(sizeof(BNode));
    z->leaf = y->leaf; z->n = 1;
    z->key[0] = y->key[2];                       /* right key moves to new node z */
    z->child[0] = y->child[2]; z->child[1] = y->child[3];
    y->n = 1;                                    /* y keeps its left key */
    for (int j = x->n; j > i; j--) {             /* make room in x */
        x->child[j + 1] = x->child[j]; x->key[j] = x->key[j - 1];
    }
    x->child[i + 1] = z;
    x->key[i] = y->key[1];                       /* middle key moves up */
    x->n++;
}

graph TD
  R["20 | 40"] --> A["10"]
  R --> B["30"]
  R --> C["50 | 60"]
          

How fast is it?

If every node (except the root) has at least $t$ children, the height of a B-tree with $n$ keys is at most:

With $t = 100$ and $n = 10^9$: $\log_{100} (5 \times 10^8) \approx 4.4$, so at most 4 levels below the root. Each level is one disk read.

Common mistakes

• Splitting by moving the middle key down into a child, instead of up into the parent.
• Thinking the tree grows at the leaves; a B-tree only gets taller when the root splits.
• Forgetting that keys inside a node are kept sorted, which is what makes the range choice work.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• A B-tree is very short because every node has many children, so the height is $O(\log_t n)$.
• All leaves are at the same depth because the tree only grows when the root splits.
• Splits push the middle key up because it separates the two halves in the parent.
• It suits disks because one node fits one disk block, and each level costs one read.
• Search picks one child per node because the node's sorted keys define the ranges.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is a B-tree like a library catalogue with labelled drawers?
   Sample answer

   Each drawer covers a range and points to smaller drawers, so only a few drawers stand between you and any card; B-tree nodes hold several keys and split the range many ways.

2. Walk through inserting 10, 20, 30, 40 into a B-tree with at most 3 keys per node.
   Sample answer

   10, 20, 30 fill one node. 40 overflows it: the middle key 20 moves up into a new root, with [10] on the left and [30 | 40] on the right.

3. Why does split_child move y->key[1] into the parent?

   A good answer says what that key separates.

   Sample answer

   It is the middle key: everything in y's left half is smaller and everything in the new node z is bigger, so in the parent it marks exactly the boundary between y and z.

4. So what is a B-tree, in one sentence?
   Sample answer

   A balanced search tree with many sorted keys per node that stays balanced by splitting full nodes and pushing the middle key up.

5. Why are all the leaves of a B-tree at the same depth?

   A good answer says where the tree grows.

   Sample answer

   Splits keep halves at the same level, and the tree only gets taller when the root splits, which pushes every leaf down together.

6. What do search and insert cost, and how many disk reads does a search need?
   Sample answer

   Both are $O(\log n)$ overall, and a search reads one node per level, $O(\log_t n)$ disk reads, about 4 for a billion keys.

7. Why do databases use B-trees rather than binary search trees?
   Sample answer

   A BST of a billion keys is about 30 levels deep, 30 disk reads. A B-tree node fills a disk block with hundreds of keys, so it needs about 4.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the order-versus-degree conventions and deletion. I'd keep the catalogue analogy, the 10–40 split example, and "fat nodes, very short, one disk read per level".

External resources

• USFCA: B-tree visualization: insert keys and watch nodes split, with adjustable max degree.
• GeeksforGeeks: B-tree: definitions, search and insert.
• Wikipedia: B-tree: history, variants and database use.

Videos

• YouTube search: B-tree insertion and splitting: pick a walkthrough.