Module 6 · Interactive topic

B-Trees

Wide, short trees for disks and databases

A B-tree stores several sorted keys in every node, so it is short and wide. Databases and file systems use it because reading one node is one disk read. Inserting into a full node splits it, and deleting from a small node borrows from or merges with a sibling.

  • Order mat most m − 1 keys per node
  • Full nodesplit — the middle key moves up
  • Balancedall leaves on the same level
B-Tree Ready
keys 8
levels 2
per node 1–3
  • Current
  • Compared
  • Too many / few
  • New / moved

Ready

Comparisons 0 Shifts 0
Ready

Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode

How it works

Every operation, in plain steps

These are exactly the steps the visualizer animates.

What does a B-tree node store?

A B-tree of order m keeps up to m − 1 sorted keys in every node, and an inner node with k keys has k + 1 children. Child i holds the keys that lie between key i − 1 and key i. Every node except the root has at least ⌈m/2⌉ − 1 keys, and all leaves are on the same level — so the tree is always balanced.

#define ORDER 4                  // m: at most 3 keys, 4 children

struct Node {
    int n;                        // how many keys are used
    int keys[ORDER - 1];          // sorted keys
    struct Node *child[ORDER];    // child[i]: keys between keys[i-1] and keys[i]
    int leaf;                     // 1 = no children
};

Search

  1. Scan the keys of the node from the left.
  2. Stop at the first key ≥ the key you want.
  3. Equal? Found. Otherwise go down into the child before it.
  4. One node per level — very few nodes in total.

Insert

  1. Walk down to the leaf where the key belongs.
  2. Put it into the leaf in sorted order.
  3. If the leaf now has m keys, it must split.
  4. New keys always go into leaves.

Split

  1. Take the middle key of the full node.
  2. Keys left of it stay; keys right of it form a new node.
  3. The middle key moves up into the parent.
  4. A full root splits into a new root: the tree grows at the TOP.

Build tree

  1. Start with an empty tree.
  2. Insert the typed keys one by one, in that order.
  3. Every full node splits; its middle key moves up.
  4. The tree grows at the top, whatever the key order.

Delete

  1. Find the key.
  2. In an inner node: replace it by its predecessor (largest key on the left).
  3. Remove the key from the leaf.
  4. If the node now has too few keys, fix it.

Borrow

  1. A sibling has more than the minimum?
  2. The separator in the parent moves down into the small node…
  3. …and the sibling's nearest key moves up to replace it.
  4. Like a rotation — sorted order is kept.

Merge

  1. Neither sibling can spare a key?
  2. Join the node, its sibling and their separator into one node.
  3. The parent loses a key — it may need fixing too.
  4. An empty root disappears: the tree shrinks at the top.
Algorithm

Pseudocode

Language-independent steps. The visualizer shows the same logic in C, Python and Java.

1 SEARCH(x, key)
2 i ← 0
3 while i < x.n and key > x.keys[i]: i ← i + 1
4 if i < x.n and key = x.keys[i] then return FOUND
5 if x is a leaf then return NOT FOUND
6 return SEARCH(x.child[i], key)
Complexity

How fast is each operation?

n = number of keys, m = order. The height is about log_m n, so a B-tree of order 100 with a million keys has only 3–4 levels. Inside a node the keys are scanned (or binary searched), which costs O(m). Building a tree of n keys is n inserts, so O(n log n).

Operation Best Average Worst Speed
Search O(1) O(log n) O(log n) Grows with n
Insert (with splits) O(log n) O(log n) O(log n) Grows with n
Delete (borrow / merge) O(log n) O(log n) O(log n) Grows with n
Build tree (n keys) O(n log n) O(n log n) O(n log n) Grows with n
Disk reads per search 1 height height Instant

Keys per node for different orders

Order m Max keys (m − 1) Min keys (⌈m/2⌉ − 1) Children Also called
3 2 1 2 or 3 2-3 tree
4 3 1 2 to 4 2-3-4 tree
5 4 2 3 to 5 —
100 99 49 50 to 100 Typical database index

B-tree vs binary search tree

BST / AVL tree B-tree
Keys per node 1 Up to m − 1
Children per node Up to 2 Up to m
Height for 1,000,000 keys About 20 (AVL) About 3–4 (m = 100)
Stays balanced by Rotations (AVL) Splitting and merging nodes
Best for Data in memory Data on disk: databases, file systems
Practice

Check your understanding

Answer each question — you will see the explanation straight away.

0 / 6 correct
Question 1

In a B-tree of order 4, what is the most keys one node can hold?

Question 2

Inserting into a full leaf causes a split. What happens to the middle key?

Question 3

Where does a B-tree grow when it gets taller?

Question 4

A node has too few keys after a delete, and its left sibling has spare keys. What happens?

Question 5

Why do databases use B-trees instead of binary search trees?

Question 6

In a B-tree of order 5, every node except the root must have at least how many keys?

Assessment

Trees quiz

Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.

Create a free account →
← Previous topic Binary Search Trees Next topic → B+ Trees