26.04Intermediate / Advanced7 topics21 min6 interactive animations

B-trees and storage indexes

B-trees: the node layout, the minimum degree, split and merge, search, insertion, deletion and why wide nodes suit disks and databases.

Learning goals

State the occupancy rules of a B-tree of minimum degree t
Search a B-tree and count the nodes (pages) visited
Insert with splits and delete with borrow and merge
Explain why B-trees minimise disk accesses

Prerequisites

Binary search treesRed-black trees

When data lives on disk, the cost that matters is the number of pages read, not the number of comparisons. A B-tree packs hundreds of keys into one node, so a billion keys are only about three or four pages deep.

26.04.1

B-tree nodes

A **B-tree** node holds a sorted list of keys and, if it is not a leaf, one more child pointer than keys: the keys between two pointers separate the key ranges of those subtrees. All leaves are at the same depth, so the tree is perfectly balanced, and a node typically fills a whole disk page.

In the animation each box is one node and its keys are written inside it. The code below is the node class used throughout this group; leaf tells whether kids is empty.

Java

1static int T = 2;                                // minimum degree
2static class Node {
3    List<Integer> keys = new ArrayList<>();      // sorted
4    List<Node> kids = new ArrayList<>();         // empty in a leaf; otherwise keys.size() + 1 children
5    boolean leaf = true;
6}
7static Node root = new Node();

B-tree: search, insertion with node splits, deletion with borrow and merge

Interactive · edit the input

B-tree (each box is one node) · 1 node

Node being examinedSearch pathKey found / new nodeChanged by split, borrow or mergeSibling used

Setup

A B-tree of minimum degree t = 2: every node except the root holds 1 to 3 keys, every internal node with m keys has m + 1 children, and all leaves are at the same depth. With t = 2 this is the 2-3-4 tree.

Step 1 / 19

Java

1static int T = 2;                                // minimum degree: every node but the root holds T-1 .. 2T-1 keys
2static class Node {
3    List<Integer> keys = new ArrayList<>();
4    List<Node> kids = new ArrayList<>();         // empty in a leaf
5    boolean leaf = true;
6}
7static Node root = new Node();
8static boolean contains(Node x, int k) {
9    int i = 0;
10    while (i < x.keys.size() && k > x.keys.get(i)) i++;          // first key >= k
11    if (i < x.keys.size() && x.keys.get(i) == k) return true;
12    return !x.leaf && contains(x.kids.get(i), k);
13}
14static void splitChild(Node x, int i) {          // x.kids[i] is full (2T-1 keys)
15    Node y = x.kids.get(i), z = new Node();
16    z.leaf = y.leaf;
17    z.keys.addAll(y.keys.subList(T, 2 * T - 1));                 // the upper T-1 keys move to the new node
18    int median = y.keys.get(T - 1);
19    y.keys.subList(T - 1, 2 * T - 1).clear();                    // y keeps the lower T-1 keys
20    if (!y.leaf) { z.kids.addAll(y.kids.subList(T, 2 * T)); y.kids.subList(T, 2 * T).clear(); }
21    x.keys.add(i, median);                       // the median moves up
22    x.kids.add(i + 1, z);
23}
24static void insert(int k) {
25    if (contains(root, k)) return;
26    if (root.keys.size() == 2 * T - 1) {         // a full root: the tree grows in height here
27        Node s = new Node(); s.leaf = false; s.kids.add(root); root = s; splitChild(s, 0);
28    }
29    insertNonFull(root, k);
30}
31static void insertNonFull(Node x, int k) {
32    int i = 0;
33    while (i < x.keys.size() && k > x.keys.get(i)) i++;
34    if (x.leaf) { x.keys.add(i, k); return; }
35    if (x.kids.get(i).keys.size() == 2 * T - 1) {                // split a full child before descending
36        splitChild(x, i);
37        if (k > x.keys.get(i)) i++;
38    }
39    insertNonFull(x.kids.get(i), k);
40}
41static void delete(int k) {
42    delete(root, k);
43    if (root.keys.isEmpty() && !root.leaf) root = root.kids.get(0);   // the tree shrinks in height
44}
45static void delete(Node x, int k) {
46    int i = 0;
47    while (i < x.keys.size() && k > x.keys.get(i)) i++;
48    if (i < x.keys.size() && x.keys.get(i) == k) {
49        if (x.leaf) x.keys.remove(i);                            // case 1: the key is in a leaf
50        else if (x.kids.get(i).keys.size() >= T) {               // case 2a: use the predecessor
51            int pred = max(x.kids.get(i)); x.keys.set(i, pred); delete(x.kids.get(i), pred);
52        } else if (x.kids.get(i + 1).keys.size() >= T) {         // case 2b: use the successor
53            int succ = min(x.kids.get(i + 1)); x.keys.set(i, succ); delete(x.kids.get(i + 1), succ);
54        } else { merge(x, i); delete(x.kids.get(i), k); }        // case 2c: merge both children around the key
55    } else if (!x.leaf) {
56        if (x.kids.get(i).keys.size() == T - 1) {                // the child needs a spare key before we descend
57            if (i > 0 && x.kids.get(i - 1).keys.size() >= T) borrowFromLeft(x, i);          // case 3a
58            else if (i < x.keys.size() && x.kids.get(i + 1).keys.size() >= T) borrowFromRight(x, i);
59            else { if (i == x.keys.size()) i--; merge(x, i); }                               // case 3b
60        }
61        delete(x.kids.get(i), k);
62    }
63}
64static void merge(Node x, int i) {               // kids[i] + keys[i] + kids[i+1] become kids[i]
65    Node y = x.kids.get(i), z = x.kids.get(i + 1);
66    y.keys.add(x.keys.remove(i));
67    y.keys.addAll(z.keys);
68    y.kids.addAll(z.kids);
69    x.kids.remove(i + 1);
70}
71static void borrowFromLeft(Node x, int i) {
72    Node c = x.kids.get(i), s = x.kids.get(i - 1);
73    c.keys.add(0, x.keys.get(i - 1));
74    x.keys.set(i - 1, s.keys.remove(s.keys.size() - 1));
75    if (!s.leaf) c.kids.add(0, s.kids.remove(s.kids.size() - 1));
76}
77static void borrowFromRight(Node x, int i) {
78    Node c = x.kids.get(i), s = x.kids.get(i + 1);
79    c.keys.add(x.keys.get(i));
80    x.keys.set(i, s.keys.remove(0));
81    if (!s.leaf) c.kids.add(s.kids.remove(0));
82}
83static int min(Node x) { while (!x.leaf) x = x.kids.get(0); return x.keys.get(0); }
84static int max(Node x) { while (!x.leaf) x = x.kids.get(x.kids.size() - 1); return x.keys.get(x.keys.size() - 1); }

Live state

0 splits0 merges0 borrows

max keys

No condition evaluated on this step

Execution trace (dry run table)Show 19 steps

Step	Line	State	What happens
1	L1	t=2 max keys=3	A B-tree of minimum degree t = 2: every node except the root holds 1 to 3 keys, every internal node with m keys has m + 1 children, and all leaves are at the same depth. With t = 2 this is the 2-3-4 tree.
2	L34	t=2 max keys=3 inserted=10	10 goes into the leaf at position 0.
3	L34	t=2 max keys=3 inserted=20	20 goes into the leaf at position 1.
4	L34	t=2 max keys=3 inserted=5	5 goes into the leaf at position 0.
5	L26	t=2 max keys=3 inserted=6	The root is full: create a new empty root above it and split the old root. This is the only way a B-tree grows taller.
6	L16	t=2 max keys=3 median=10	Split the full node: its median 10 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
7	L1	t=2 max keys=3 inserted=6	Descend into child 0 of this node.
8	L34	t=2 max keys=3 inserted=6	6 goes into the leaf at position 1.
9	L1	t=2 max keys=3 inserted=12	Descend into child 1 of this node.
10	L34	t=2 max keys=3 inserted=12	12 goes into the leaf at position 0.
11	L1	t=2 max keys=3 inserted=30	Descend into child 1 of this node.
12	L34	t=2 max keys=3 inserted=30	30 goes into the leaf at position 2.
13	L1	t=2 max keys=3 inserted=7	Descend into child 0 of this node.
14	L34	t=2 max keys=3 inserted=7	7 goes into the leaf at position 2.
15	L1	t=2 max keys=3 inserted=17	Descend into child 1 of this node.
16	L35	t=2 max keys=3 inserted=17	The child is full (3 keys): split it before descending, so there is always room to push a key up.
17	L16	t=2 max keys=3 median=20	Split the full node: its median 20 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
18	L34	t=2 max keys=3 inserted=17	17 goes into the leaf at position 1.
19	L1	keys=8 height=1 t=2	8 keys in a tree of height 1: 2 splits, 0 borrows, 0 merges.

26.04.2

Degree

The **minimum degree** t fixes the shape: every node except the root holds at least t - 1 keys and at most 2t - 1 keys, so an internal node has between t and 2t children, and the root holds at least 1 key. For t = 2 that is the 2-3-4 tree; with t = 3 a node holds 2 to 5 keys. Real indexes use t in the hundreds.

The upper bound is 2t - 1 and not 2t because a **split** of a full node needs to leave two valid nodes and send one median key up: (2t - 1) - 1 = 2t - 2 keys remain, which is two nodes with t - 1 keys each. Change the second input of the animation between 2 and 3 to see the node widths change.

Minimum degree t	Keys per node (not the root)	Children of an internal node
2	1 to 3	2 to 4
3	2 to 5	3 to 6
50	49 to 99	50 to 100
500	499 to 999	500 to 1000

Java

1static int minKeys(int t) { return t - 1; }       // every node except the root
2static int maxKeys(int t) { return 2 * t - 1; }   // a node with this many keys is full and splits

B-tree: search, insertion with node splits, deletion with borrow and merge

Interactive · edit the input

B-tree (each box is one node) · 1 node

Node being examinedSearch pathKey found / new nodeChanged by split, borrow or mergeSibling used

Setup

Step 1 / 19

Java

1static int T = 2;                                // minimum degree: every node but the root holds T-1 .. 2T-1 keys
2static class Node {
3    List<Integer> keys = new ArrayList<>();
4    List<Node> kids = new ArrayList<>();         // empty in a leaf
5    boolean leaf = true;
6}
7static Node root = new Node();
8static boolean contains(Node x, int k) {
9    int i = 0;
10    while (i < x.keys.size() && k > x.keys.get(i)) i++;          // first key >= k
11    if (i < x.keys.size() && x.keys.get(i) == k) return true;
12    return !x.leaf && contains(x.kids.get(i), k);
13}
14static void splitChild(Node x, int i) {          // x.kids[i] is full (2T-1 keys)
15    Node y = x.kids.get(i), z = new Node();
16    z.leaf = y.leaf;
17    z.keys.addAll(y.keys.subList(T, 2 * T - 1));                 // the upper T-1 keys move to the new node
18    int median = y.keys.get(T - 1);
19    y.keys.subList(T - 1, 2 * T - 1).clear();                    // y keeps the lower T-1 keys
20    if (!y.leaf) { z.kids.addAll(y.kids.subList(T, 2 * T)); y.kids.subList(T, 2 * T).clear(); }
21    x.keys.add(i, median);                       // the median moves up
22    x.kids.add(i + 1, z);
23}
24static void insert(int k) {
25    if (contains(root, k)) return;
26    if (root.keys.size() == 2 * T - 1) {         // a full root: the tree grows in height here
27        Node s = new Node(); s.leaf = false; s.kids.add(root); root = s; splitChild(s, 0);
28    }
29    insertNonFull(root, k);
30}
31static void insertNonFull(Node x, int k) {
32    int i = 0;
33    while (i < x.keys.size() && k > x.keys.get(i)) i++;
34    if (x.leaf) { x.keys.add(i, k); return; }
35    if (x.kids.get(i).keys.size() == 2 * T - 1) {                // split a full child before descending
36        splitChild(x, i);
37        if (k > x.keys.get(i)) i++;
38    }
39    insertNonFull(x.kids.get(i), k);
40}
41static void delete(int k) {
42    delete(root, k);
43    if (root.keys.isEmpty() && !root.leaf) root = root.kids.get(0);   // the tree shrinks in height
44}
45static void delete(Node x, int k) {
46    int i = 0;
47    while (i < x.keys.size() && k > x.keys.get(i)) i++;
48    if (i < x.keys.size() && x.keys.get(i) == k) {
49        if (x.leaf) x.keys.remove(i);                            // case 1: the key is in a leaf
50        else if (x.kids.get(i).keys.size() >= T) {               // case 2a: use the predecessor
51            int pred = max(x.kids.get(i)); x.keys.set(i, pred); delete(x.kids.get(i), pred);
52        } else if (x.kids.get(i + 1).keys.size() >= T) {         // case 2b: use the successor
53            int succ = min(x.kids.get(i + 1)); x.keys.set(i, succ); delete(x.kids.get(i + 1), succ);
54        } else { merge(x, i); delete(x.kids.get(i), k); }        // case 2c: merge both children around the key
55    } else if (!x.leaf) {
56        if (x.kids.get(i).keys.size() == T - 1) {                // the child needs a spare key before we descend
57            if (i > 0 && x.kids.get(i - 1).keys.size() >= T) borrowFromLeft(x, i);          // case 3a
58            else if (i < x.keys.size() && x.kids.get(i + 1).keys.size() >= T) borrowFromRight(x, i);
59            else { if (i == x.keys.size()) i--; merge(x, i); }                               // case 3b
60        }
61        delete(x.kids.get(i), k);
62    }
63}
64static void merge(Node x, int i) {               // kids[i] + keys[i] + kids[i+1] become kids[i]
65    Node y = x.kids.get(i), z = x.kids.get(i + 1);
66    y.keys.add(x.keys.remove(i));
67    y.keys.addAll(z.keys);
68    y.kids.addAll(z.kids);
69    x.kids.remove(i + 1);
70}
71static void borrowFromLeft(Node x, int i) {
72    Node c = x.kids.get(i), s = x.kids.get(i - 1);
73    c.keys.add(0, x.keys.get(i - 1));
74    x.keys.set(i - 1, s.keys.remove(s.keys.size() - 1));
75    if (!s.leaf) c.kids.add(0, s.kids.remove(s.kids.size() - 1));
76}
77static void borrowFromRight(Node x, int i) {
78    Node c = x.kids.get(i), s = x.kids.get(i + 1);
79    c.keys.add(x.keys.get(i));
80    x.keys.set(i, s.keys.remove(0));
81    if (!s.leaf) c.kids.add(s.kids.remove(0));
82}
83static int min(Node x) { while (!x.leaf) x = x.kids.get(0); return x.keys.get(0); }
84static int max(Node x) { while (!x.leaf) x = x.kids.get(x.kids.size() - 1); return x.keys.get(x.keys.size() - 1); }

Live state

0 splits0 merges0 borrows

max keys

No condition evaluated on this step

Execution trace (dry run table)Show 19 steps

Step	Line	State	What happens
1	L1	t=2 max keys=3	A B-tree of minimum degree t = 2: every node except the root holds 1 to 3 keys, every internal node with m keys has m + 1 children, and all leaves are at the same depth. With t = 2 this is the 2-3-4 tree.
2	L34	t=2 max keys=3 inserted=10	10 goes into the leaf at position 0.
3	L34	t=2 max keys=3 inserted=20	20 goes into the leaf at position 1.
4	L34	t=2 max keys=3 inserted=5	5 goes into the leaf at position 0.
5	L26	t=2 max keys=3 inserted=6	The root is full: create a new empty root above it and split the old root. This is the only way a B-tree grows taller.
6	L16	t=2 max keys=3 median=10	Split the full node: its median 10 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
7	L1	t=2 max keys=3 inserted=6	Descend into child 0 of this node.
8	L34	t=2 max keys=3 inserted=6	6 goes into the leaf at position 1.
9	L1	t=2 max keys=3 inserted=12	Descend into child 1 of this node.
10	L34	t=2 max keys=3 inserted=12	12 goes into the leaf at position 0.
11	L1	t=2 max keys=3 inserted=30	Descend into child 1 of this node.
12	L34	t=2 max keys=3 inserted=30	30 goes into the leaf at position 2.
13	L1	t=2 max keys=3 inserted=7	Descend into child 0 of this node.
14	L34	t=2 max keys=3 inserted=7	7 goes into the leaf at position 2.
15	L1	t=2 max keys=3 inserted=17	Descend into child 1 of this node.
16	L35	t=2 max keys=3 inserted=17	The child is full (3 keys): split it before descending, so there is always room to push a key up.
17	L16	t=2 max keys=3 median=20	Split the full node: its median 20 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
18	L34	t=2 max keys=3 inserted=17	17 goes into the leaf at position 1.
19	L1	keys=8 height=1 t=2	8 keys in a tree of height 1: 2 splits, 0 borrows, 0 merges.

26.04.3

Split/merge

**Split** and **merge** are the two structural moves. Splitting a full node (2t - 1 keys) sends its **median** to the parent and leaves two nodes of t - 1 keys, the lower half in the old node and the upper half in a new one. **Merge** is the inverse: two siblings with t - 1 keys each, together with the parent's separator between them, make one node of 2t - 1 keys. The tree grows taller only when the root splits and shrinks only when the root's last key is merged down.

In the animation, splits show as the new node (marked as created) next to the old one, and the median appearing in the parent. The “Sorted input (t = 2)” preset needs 5 splits for 10 keys and reaches height 2.

Java

1static void splitChild(Node x, int i) {          // x.kids[i] is full: 2T-1 keys
2    Node y = x.kids.get(i), z = new Node();
3    z.leaf = y.leaf;
4    z.keys.addAll(y.keys.subList(T, 2 * T - 1)); // the upper T-1 keys move to the new node
5    int median = y.keys.get(T - 1);
6    y.keys.subList(T - 1, 2 * T - 1).clear();    // y keeps the lower T-1 keys
7    if (!y.leaf) { z.kids.addAll(y.kids.subList(T, 2 * T)); y.kids.subList(T, 2 * T).clear(); }
8    x.keys.add(i, median);                       // the median moves up
9    x.kids.add(i + 1, z);
10}
11static void merge(Node x, int i) {               // kids[i] + keys[i] + kids[i+1] become kids[i]
12    Node y = x.kids.get(i), z = x.kids.get(i + 1);
13    y.keys.add(x.keys.remove(i));
14    y.keys.addAll(z.keys);
15    y.kids.addAll(z.kids);
16    x.kids.remove(i + 1);
17}

B-tree: search, insertion with node splits, deletion with borrow and merge

Interactive · edit the input

B-tree (each box is one node) · 1 node

Node being examinedSearch pathKey found / new nodeChanged by split, borrow or mergeSibling used

Setup

Step 1 / 19

Java

1static int T = 2;                                // minimum degree: every node but the root holds T-1 .. 2T-1 keys
2static class Node {
3    List<Integer> keys = new ArrayList<>();
4    List<Node> kids = new ArrayList<>();         // empty in a leaf
5    boolean leaf = true;
6}
7static Node root = new Node();
8static boolean contains(Node x, int k) {
9    int i = 0;
10    while (i < x.keys.size() && k > x.keys.get(i)) i++;          // first key >= k
11    if (i < x.keys.size() && x.keys.get(i) == k) return true;
12    return !x.leaf && contains(x.kids.get(i), k);
13}
14static void splitChild(Node x, int i) {          // x.kids[i] is full (2T-1 keys)
15    Node y = x.kids.get(i), z = new Node();
16    z.leaf = y.leaf;
17    z.keys.addAll(y.keys.subList(T, 2 * T - 1));                 // the upper T-1 keys move to the new node
18    int median = y.keys.get(T - 1);
19    y.keys.subList(T - 1, 2 * T - 1).clear();                    // y keeps the lower T-1 keys
20    if (!y.leaf) { z.kids.addAll(y.kids.subList(T, 2 * T)); y.kids.subList(T, 2 * T).clear(); }
21    x.keys.add(i, median);                       // the median moves up
22    x.kids.add(i + 1, z);
23}
24static void insert(int k) {
25    if (contains(root, k)) return;
26    if (root.keys.size() == 2 * T - 1) {         // a full root: the tree grows in height here
27        Node s = new Node(); s.leaf = false; s.kids.add(root); root = s; splitChild(s, 0);
28    }
29    insertNonFull(root, k);
30}
31static void insertNonFull(Node x, int k) {
32    int i = 0;
33    while (i < x.keys.size() && k > x.keys.get(i)) i++;
34    if (x.leaf) { x.keys.add(i, k); return; }
35    if (x.kids.get(i).keys.size() == 2 * T - 1) {                // split a full child before descending
36        splitChild(x, i);
37        if (k > x.keys.get(i)) i++;
38    }
39    insertNonFull(x.kids.get(i), k);
40}
41static void delete(int k) {
42    delete(root, k);
43    if (root.keys.isEmpty() && !root.leaf) root = root.kids.get(0);   // the tree shrinks in height
44}
45static void delete(Node x, int k) {
46    int i = 0;
47    while (i < x.keys.size() && k > x.keys.get(i)) i++;
48    if (i < x.keys.size() && x.keys.get(i) == k) {
49        if (x.leaf) x.keys.remove(i);                            // case 1: the key is in a leaf
50        else if (x.kids.get(i).keys.size() >= T) {               // case 2a: use the predecessor
51            int pred = max(x.kids.get(i)); x.keys.set(i, pred); delete(x.kids.get(i), pred);
52        } else if (x.kids.get(i + 1).keys.size() >= T) {         // case 2b: use the successor
53            int succ = min(x.kids.get(i + 1)); x.keys.set(i, succ); delete(x.kids.get(i + 1), succ);
54        } else { merge(x, i); delete(x.kids.get(i), k); }        // case 2c: merge both children around the key
55    } else if (!x.leaf) {
56        if (x.kids.get(i).keys.size() == T - 1) {                // the child needs a spare key before we descend
57            if (i > 0 && x.kids.get(i - 1).keys.size() >= T) borrowFromLeft(x, i);          // case 3a
58            else if (i < x.keys.size() && x.kids.get(i + 1).keys.size() >= T) borrowFromRight(x, i);
59            else { if (i == x.keys.size()) i--; merge(x, i); }                               // case 3b
60        }
61        delete(x.kids.get(i), k);
62    }
63}
64static void merge(Node x, int i) {               // kids[i] + keys[i] + kids[i+1] become kids[i]
65    Node y = x.kids.get(i), z = x.kids.get(i + 1);
66    y.keys.add(x.keys.remove(i));
67    y.keys.addAll(z.keys);
68    y.kids.addAll(z.kids);
69    x.kids.remove(i + 1);
70}
71static void borrowFromLeft(Node x, int i) {
72    Node c = x.kids.get(i), s = x.kids.get(i - 1);
73    c.keys.add(0, x.keys.get(i - 1));
74    x.keys.set(i - 1, s.keys.remove(s.keys.size() - 1));
75    if (!s.leaf) c.kids.add(0, s.kids.remove(s.kids.size() - 1));
76}
77static void borrowFromRight(Node x, int i) {
78    Node c = x.kids.get(i), s = x.kids.get(i + 1);
79    c.keys.add(x.keys.get(i));
80    x.keys.set(i, s.keys.remove(0));
81    if (!s.leaf) c.kids.add(s.kids.remove(0));
82}
83static int min(Node x) { while (!x.leaf) x = x.kids.get(0); return x.keys.get(0); }
84static int max(Node x) { while (!x.leaf) x = x.kids.get(x.kids.size() - 1); return x.keys.get(x.keys.size() - 1); }

Live state

0 splits0 merges0 borrows

max keys

No condition evaluated on this step

Execution trace (dry run table)Show 19 steps

Step	Line	State	What happens
1	L1	t=2 max keys=3	A B-tree of minimum degree t = 2: every node except the root holds 1 to 3 keys, every internal node with m keys has m + 1 children, and all leaves are at the same depth. With t = 2 this is the 2-3-4 tree.
2	L34	t=2 max keys=3 inserted=10	10 goes into the leaf at position 0.
3	L34	t=2 max keys=3 inserted=20	20 goes into the leaf at position 1.
4	L34	t=2 max keys=3 inserted=5	5 goes into the leaf at position 0.
5	L26	t=2 max keys=3 inserted=6	The root is full: create a new empty root above it and split the old root. This is the only way a B-tree grows taller.
6	L16	t=2 max keys=3 median=10	Split the full node: its median 10 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
7	L1	t=2 max keys=3 inserted=6	Descend into child 0 of this node.
8	L34	t=2 max keys=3 inserted=6	6 goes into the leaf at position 1.
9	L1	t=2 max keys=3 inserted=12	Descend into child 1 of this node.
10	L34	t=2 max keys=3 inserted=12	12 goes into the leaf at position 0.
11	L1	t=2 max keys=3 inserted=30	Descend into child 1 of this node.
12	L34	t=2 max keys=3 inserted=30	30 goes into the leaf at position 2.
13	L1	t=2 max keys=3 inserted=7	Descend into child 0 of this node.
14	L34	t=2 max keys=3 inserted=7	7 goes into the leaf at position 2.
15	L1	t=2 max keys=3 inserted=17	Descend into child 1 of this node.
16	L35	t=2 max keys=3 inserted=17	The child is full (3 keys): split it before descending, so there is always room to push a key up.
17	L16	t=2 max keys=3 median=20	Split the full node: its median 20 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
18	L34	t=2 max keys=3 inserted=17	17 goes into the leaf at position 1.
19	L1	keys=8 height=1 t=2	8 keys in a tree of height 1: 2 splits, 0 borrows, 0 merges.

26.04.4

Search

Searching is binary search generalised: in a node find the first key that is at least the target; if equal, done; otherwise follow the child just before that key. Each node costs O(log t) comparisons (or O(t) with a linear scan), and the number of **nodes visited**, equal to the number of page reads, is at most the height plus one.

Run the “Search” preset: the target 12 is found after visiting the nodes on one root-to-node path. The height of a B-tree with n keys is at most log base t of (n + 1) / 2, so the number of page reads grows extremely slowly.

Java

1static boolean contains(Node x, int k) {
2    int i = 0;
3    while (i < x.keys.size() && k > x.keys.get(i)) i++;          // first key >= k
4    if (i < x.keys.size() && x.keys.get(i) == k) return true;
5    return !x.leaf && contains(x.kids.get(i), k);                // follow the child just before that key
6}

Best

O(log t)

Average

O(log t · log_t n)

Worst

O(log t · log_t n)

Space

O(1) iterative, O(h) recursive

B-tree: search, insertion with node splits, deletion with borrow and merge

Interactive · edit the input

B-tree (each box is one node) · 1 node

Node being examinedSearch pathKey found / new nodeChanged by split, borrow or mergeSibling used

Setup

Step 1 / 19

Java

1static int T = 2;                                // minimum degree: every node but the root holds T-1 .. 2T-1 keys
2static class Node {
3    List<Integer> keys = new ArrayList<>();
4    List<Node> kids = new ArrayList<>();         // empty in a leaf
5    boolean leaf = true;
6}
7static Node root = new Node();
8static boolean contains(Node x, int k) {
9    int i = 0;
10    while (i < x.keys.size() && k > x.keys.get(i)) i++;          // first key >= k
11    if (i < x.keys.size() && x.keys.get(i) == k) return true;
12    return !x.leaf && contains(x.kids.get(i), k);
13}
14static void splitChild(Node x, int i) {          // x.kids[i] is full (2T-1 keys)
15    Node y = x.kids.get(i), z = new Node();
16    z.leaf = y.leaf;
17    z.keys.addAll(y.keys.subList(T, 2 * T - 1));                 // the upper T-1 keys move to the new node
18    int median = y.keys.get(T - 1);
19    y.keys.subList(T - 1, 2 * T - 1).clear();                    // y keeps the lower T-1 keys
20    if (!y.leaf) { z.kids.addAll(y.kids.subList(T, 2 * T)); y.kids.subList(T, 2 * T).clear(); }
21    x.keys.add(i, median);                       // the median moves up
22    x.kids.add(i + 1, z);
23}
24static void insert(int k) {
25    if (contains(root, k)) return;
26    if (root.keys.size() == 2 * T - 1) {         // a full root: the tree grows in height here
27        Node s = new Node(); s.leaf = false; s.kids.add(root); root = s; splitChild(s, 0);
28    }
29    insertNonFull(root, k);
30}
31static void insertNonFull(Node x, int k) {
32    int i = 0;
33    while (i < x.keys.size() && k > x.keys.get(i)) i++;
34    if (x.leaf) { x.keys.add(i, k); return; }
35    if (x.kids.get(i).keys.size() == 2 * T - 1) {                // split a full child before descending
36        splitChild(x, i);
37        if (k > x.keys.get(i)) i++;
38    }
39    insertNonFull(x.kids.get(i), k);
40}
41static void delete(int k) {
42    delete(root, k);
43    if (root.keys.isEmpty() && !root.leaf) root = root.kids.get(0);   // the tree shrinks in height
44}
45static void delete(Node x, int k) {
46    int i = 0;
47    while (i < x.keys.size() && k > x.keys.get(i)) i++;
48    if (i < x.keys.size() && x.keys.get(i) == k) {
49        if (x.leaf) x.keys.remove(i);                            // case 1: the key is in a leaf
50        else if (x.kids.get(i).keys.size() >= T) {               // case 2a: use the predecessor
51            int pred = max(x.kids.get(i)); x.keys.set(i, pred); delete(x.kids.get(i), pred);
52        } else if (x.kids.get(i + 1).keys.size() >= T) {         // case 2b: use the successor
53            int succ = min(x.kids.get(i + 1)); x.keys.set(i, succ); delete(x.kids.get(i + 1), succ);
54        } else { merge(x, i); delete(x.kids.get(i), k); }        // case 2c: merge both children around the key
55    } else if (!x.leaf) {
56        if (x.kids.get(i).keys.size() == T - 1) {                // the child needs a spare key before we descend
57            if (i > 0 && x.kids.get(i - 1).keys.size() >= T) borrowFromLeft(x, i);          // case 3a
58            else if (i < x.keys.size() && x.kids.get(i + 1).keys.size() >= T) borrowFromRight(x, i);
59            else { if (i == x.keys.size()) i--; merge(x, i); }                               // case 3b
60        }
61        delete(x.kids.get(i), k);
62    }
63}
64static void merge(Node x, int i) {               // kids[i] + keys[i] + kids[i+1] become kids[i]
65    Node y = x.kids.get(i), z = x.kids.get(i + 1);
66    y.keys.add(x.keys.remove(i));
67    y.keys.addAll(z.keys);
68    y.kids.addAll(z.kids);
69    x.kids.remove(i + 1);
70}
71static void borrowFromLeft(Node x, int i) {
72    Node c = x.kids.get(i), s = x.kids.get(i - 1);
73    c.keys.add(0, x.keys.get(i - 1));
74    x.keys.set(i - 1, s.keys.remove(s.keys.size() - 1));
75    if (!s.leaf) c.kids.add(0, s.kids.remove(s.kids.size() - 1));
76}
77static void borrowFromRight(Node x, int i) {
78    Node c = x.kids.get(i), s = x.kids.get(i + 1);
79    c.keys.add(x.keys.get(i));
80    x.keys.set(i, s.keys.remove(0));
81    if (!s.leaf) c.kids.add(s.kids.remove(0));
82}
83static int min(Node x) { while (!x.leaf) x = x.kids.get(0); return x.keys.get(0); }
84static int max(Node x) { while (!x.leaf) x = x.kids.get(x.kids.size() - 1); return x.keys.get(x.keys.size() - 1); }

Live state

0 splits0 merges0 borrows

max keys

No condition evaluated on this step

Execution trace (dry run table)Show 19 steps

Step	Line	State	What happens
1	L1	t=2 max keys=3	A B-tree of minimum degree t = 2: every node except the root holds 1 to 3 keys, every internal node with m keys has m + 1 children, and all leaves are at the same depth. With t = 2 this is the 2-3-4 tree.
2	L34	t=2 max keys=3 inserted=10	10 goes into the leaf at position 0.
3	L34	t=2 max keys=3 inserted=20	20 goes into the leaf at position 1.
4	L34	t=2 max keys=3 inserted=5	5 goes into the leaf at position 0.
5	L26	t=2 max keys=3 inserted=6	The root is full: create a new empty root above it and split the old root. This is the only way a B-tree grows taller.
6	L16	t=2 max keys=3 median=10	Split the full node: its median 10 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
7	L1	t=2 max keys=3 inserted=6	Descend into child 0 of this node.
8	L34	t=2 max keys=3 inserted=6	6 goes into the leaf at position 1.
9	L1	t=2 max keys=3 inserted=12	Descend into child 1 of this node.
10	L34	t=2 max keys=3 inserted=12	12 goes into the leaf at position 0.
11	L1	t=2 max keys=3 inserted=30	Descend into child 1 of this node.
12	L34	t=2 max keys=3 inserted=30	30 goes into the leaf at position 2.
13	L1	t=2 max keys=3 inserted=7	Descend into child 0 of this node.
14	L34	t=2 max keys=3 inserted=7	7 goes into the leaf at position 2.
15	L1	t=2 max keys=3 inserted=17	Descend into child 1 of this node.
16	L35	t=2 max keys=3 inserted=17	The child is full (3 keys): split it before descending, so there is always room to push a key up.
17	L16	t=2 max keys=3 median=20	Split the full node: its median 20 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
18	L34	t=2 max keys=3 inserted=17	17 goes into the leaf at position 1.
19	L1	keys=8 height=1 t=2	8 keys in a tree of height 1: 2 splits, 0 borrows, 0 merges.

26.04.5

Insert

Insertion uses **proactive splitting** on the way down: whenever the search is about to enter a full node, split it first, so the node it ends in always has room and no split ever has to travel back up. A full root is split first, which creates a new root and is the only way the tree gets taller. The key is finally placed in a leaf, in sorted position.

The “Splits (t = 2, a 2-3-4 tree)” preset inserts 10, 20, 5, 6, 12, 30, 7, 17: the tree ends at height 1 with 2 splits. With t = 3 and 12 sorted keys (“Wider nodes”) the same effect needs only 3 splits and the tree is still height 1.

Java

1static void insert(int k) {
2    if (contains(root, k)) return;
3    if (root.keys.size() == 2 * T - 1) {         // a full root: the tree grows in height here
4        Node s = new Node(); s.leaf = false; s.kids.add(root); root = s; splitChild(s, 0);
5    }
6    insertNonFull(root, k);
7}
8static void insertNonFull(Node x, int k) {
9    int i = 0;
10    while (i < x.keys.size() && k > x.keys.get(i)) i++;
11    if (x.leaf) { x.keys.add(i, k); return; }
12    if (x.kids.get(i).keys.size() == 2 * T - 1) {                // split a full child before descending
13        splitChild(x, i);
14        if (k > x.keys.get(i)) i++;
15    }
16    insertNonFull(x.kids.get(i), k);
17}

Best

O(log t · log_t n)

Average

O(t · log_t n)

Worst

O(t · log_t n)

Space

O(h)

B-tree: search, insertion with node splits, deletion with borrow and merge

Interactive · edit the input

B-tree (each box is one node) · 1 node

Node being examinedSearch pathKey found / new nodeChanged by split, borrow or mergeSibling used

Setup

Step 1 / 19

Java

1static int T = 2;                                // minimum degree: every node but the root holds T-1 .. 2T-1 keys
2static class Node {
3    List<Integer> keys = new ArrayList<>();
4    List<Node> kids = new ArrayList<>();         // empty in a leaf
5    boolean leaf = true;
6}
7static Node root = new Node();
8static boolean contains(Node x, int k) {
9    int i = 0;
10    while (i < x.keys.size() && k > x.keys.get(i)) i++;          // first key >= k
11    if (i < x.keys.size() && x.keys.get(i) == k) return true;
12    return !x.leaf && contains(x.kids.get(i), k);
13}
14static void splitChild(Node x, int i) {          // x.kids[i] is full (2T-1 keys)
15    Node y = x.kids.get(i), z = new Node();
16    z.leaf = y.leaf;
17    z.keys.addAll(y.keys.subList(T, 2 * T - 1));                 // the upper T-1 keys move to the new node
18    int median = y.keys.get(T - 1);
19    y.keys.subList(T - 1, 2 * T - 1).clear();                    // y keeps the lower T-1 keys
20    if (!y.leaf) { z.kids.addAll(y.kids.subList(T, 2 * T)); y.kids.subList(T, 2 * T).clear(); }
21    x.keys.add(i, median);                       // the median moves up
22    x.kids.add(i + 1, z);
23}
24static void insert(int k) {
25    if (contains(root, k)) return;
26    if (root.keys.size() == 2 * T - 1) {         // a full root: the tree grows in height here
27        Node s = new Node(); s.leaf = false; s.kids.add(root); root = s; splitChild(s, 0);
28    }
29    insertNonFull(root, k);
30}
31static void insertNonFull(Node x, int k) {
32    int i = 0;
33    while (i < x.keys.size() && k > x.keys.get(i)) i++;
34    if (x.leaf) { x.keys.add(i, k); return; }
35    if (x.kids.get(i).keys.size() == 2 * T - 1) {                // split a full child before descending
36        splitChild(x, i);
37        if (k > x.keys.get(i)) i++;
38    }
39    insertNonFull(x.kids.get(i), k);
40}
41static void delete(int k) {
42    delete(root, k);
43    if (root.keys.isEmpty() && !root.leaf) root = root.kids.get(0);   // the tree shrinks in height
44}
45static void delete(Node x, int k) {
46    int i = 0;
47    while (i < x.keys.size() && k > x.keys.get(i)) i++;
48    if (i < x.keys.size() && x.keys.get(i) == k) {
49        if (x.leaf) x.keys.remove(i);                            // case 1: the key is in a leaf
50        else if (x.kids.get(i).keys.size() >= T) {               // case 2a: use the predecessor
51            int pred = max(x.kids.get(i)); x.keys.set(i, pred); delete(x.kids.get(i), pred);
52        } else if (x.kids.get(i + 1).keys.size() >= T) {         // case 2b: use the successor
53            int succ = min(x.kids.get(i + 1)); x.keys.set(i, succ); delete(x.kids.get(i + 1), succ);
54        } else { merge(x, i); delete(x.kids.get(i), k); }        // case 2c: merge both children around the key
55    } else if (!x.leaf) {
56        if (x.kids.get(i).keys.size() == T - 1) {                // the child needs a spare key before we descend
57            if (i > 0 && x.kids.get(i - 1).keys.size() >= T) borrowFromLeft(x, i);          // case 3a
58            else if (i < x.keys.size() && x.kids.get(i + 1).keys.size() >= T) borrowFromRight(x, i);
59            else { if (i == x.keys.size()) i--; merge(x, i); }                               // case 3b
60        }
61        delete(x.kids.get(i), k);
62    }
63}
64static void merge(Node x, int i) {               // kids[i] + keys[i] + kids[i+1] become kids[i]
65    Node y = x.kids.get(i), z = x.kids.get(i + 1);
66    y.keys.add(x.keys.remove(i));
67    y.keys.addAll(z.keys);
68    y.kids.addAll(z.kids);
69    x.kids.remove(i + 1);
70}
71static void borrowFromLeft(Node x, int i) {
72    Node c = x.kids.get(i), s = x.kids.get(i - 1);
73    c.keys.add(0, x.keys.get(i - 1));
74    x.keys.set(i - 1, s.keys.remove(s.keys.size() - 1));
75    if (!s.leaf) c.kids.add(0, s.kids.remove(s.kids.size() - 1));
76}
77static void borrowFromRight(Node x, int i) {
78    Node c = x.kids.get(i), s = x.kids.get(i + 1);
79    c.keys.add(x.keys.get(i));
80    x.keys.set(i, s.keys.remove(0));
81    if (!s.leaf) c.kids.add(s.kids.remove(0));
82}
83static int min(Node x) { while (!x.leaf) x = x.kids.get(0); return x.keys.get(0); }
84static int max(Node x) { while (!x.leaf) x = x.kids.get(x.kids.size() - 1); return x.keys.get(x.keys.size() - 1); }

Live state

0 splits0 merges0 borrows

max keys

No condition evaluated on this step

Execution trace (dry run table)Show 19 steps

Step	Line	State	What happens
1	L1	t=2 max keys=3	A B-tree of minimum degree t = 2: every node except the root holds 1 to 3 keys, every internal node with m keys has m + 1 children, and all leaves are at the same depth. With t = 2 this is the 2-3-4 tree.
2	L34	t=2 max keys=3 inserted=10	10 goes into the leaf at position 0.
3	L34	t=2 max keys=3 inserted=20	20 goes into the leaf at position 1.
4	L34	t=2 max keys=3 inserted=5	5 goes into the leaf at position 0.
5	L26	t=2 max keys=3 inserted=6	The root is full: create a new empty root above it and split the old root. This is the only way a B-tree grows taller.
6	L16	t=2 max keys=3 median=10	Split the full node: its median 10 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
7	L1	t=2 max keys=3 inserted=6	Descend into child 0 of this node.
8	L34	t=2 max keys=3 inserted=6	6 goes into the leaf at position 1.
9	L1	t=2 max keys=3 inserted=12	Descend into child 1 of this node.
10	L34	t=2 max keys=3 inserted=12	12 goes into the leaf at position 0.
11	L1	t=2 max keys=3 inserted=30	Descend into child 1 of this node.
12	L34	t=2 max keys=3 inserted=30	30 goes into the leaf at position 2.
13	L1	t=2 max keys=3 inserted=7	Descend into child 0 of this node.
14	L34	t=2 max keys=3 inserted=7	7 goes into the leaf at position 2.
15	L1	t=2 max keys=3 inserted=17	Descend into child 1 of this node.
16	L35	t=2 max keys=3 inserted=17	The child is full (3 keys): split it before descending, so there is always room to push a key up.
17	L16	t=2 max keys=3 median=20	Split the full node: its median 20 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
18	L34	t=2 max keys=3 inserted=17	17 goes into the leaf at position 1.
19	L1	keys=8 height=1 t=2	8 keys in a tree of height 1: 2 splits, 0 borrows, 0 merges.

26.04.6

Delete

Deletion keeps every node above the minimum while descending, so it never needs to go back. **Case 1**: the key is in a leaf: remove it. **Case 2**: the key is in an internal node: replace it by its **predecessor** (case 2a, if the left child has at least t keys) or **successor** (case 2b, right child), and delete that key from the child; if both children have only t - 1 keys (case 2c), **merge** them with the key and recurse. **Case 3**: the key is in a subtree whose child has only t - 1 keys: before descending, **borrow** a key from a sibling with a spare (3a, a rotation through the parent) or **merge** with a sibling (3b).

Presets: “Delete from a leaf” is case 1. “Delete an internal key” (keys 1 to 10, delete 4) uses case 2b and then case 3b, with 1 merge. “Delete that merges nodes” deletes 1 from keys 1 to 7 by case 3b. If the root ends with no keys, its only child becomes the root and the tree is one level shorter.

Java

1static void delete(int k) {
2    delete(root, k);
3    if (root.keys.isEmpty() && !root.leaf) root = root.kids.get(0);    // the tree shrinks in height
4}
5static void delete(Node x, int k) {
6    int i = 0;
7    while (i < x.keys.size() && k > x.keys.get(i)) i++;
8    if (i < x.keys.size() && x.keys.get(i) == k) {
9        if (x.leaf) x.keys.remove(i);                            // case 1: the key is in a leaf
10        else if (x.kids.get(i).keys.size() >= T) {               // case 2a: use the predecessor
11            int pred = max(x.kids.get(i)); x.keys.set(i, pred); delete(x.kids.get(i), pred);
12        } else if (x.kids.get(i + 1).keys.size() >= T) {         // case 2b: use the successor
13            int succ = min(x.kids.get(i + 1)); x.keys.set(i, succ); delete(x.kids.get(i + 1), succ);
14        } else { merge(x, i); delete(x.kids.get(i), k); }        // case 2c: merge both children around the key
15    } else if (!x.leaf) {
16        if (x.kids.get(i).keys.size() == T - 1) {                // the child needs a spare key before we descend
17            if (i > 0 && x.kids.get(i - 1).keys.size() >= T) borrowFromLeft(x, i);          // case 3a
18            else if (i < x.keys.size() && x.kids.get(i + 1).keys.size() >= T) borrowFromRight(x, i);
19            else { if (i == x.keys.size()) i--; merge(x, i); }                               // case 3b
20        }
21        delete(x.kids.get(i), k);
22    }
23}
24// merge(x, i) is the one defined in the split-merge item
25static void borrowFromLeft(Node x, int i) {
26    Node c = x.kids.get(i), s = x.kids.get(i - 1);
27    c.keys.add(0, x.keys.get(i - 1));
28    x.keys.set(i - 1, s.keys.remove(s.keys.size() - 1));
29    if (!s.leaf) c.kids.add(0, s.kids.remove(s.kids.size() - 1));
30}
31static void borrowFromRight(Node x, int i) {
32    Node c = x.kids.get(i), s = x.kids.get(i + 1);
33    c.keys.add(x.keys.get(i));
34    x.keys.set(i, s.keys.remove(0));
35    if (!s.leaf) c.kids.add(s.kids.remove(0));
36}
37static int min(Node x) { while (!x.leaf) x = x.kids.get(0); return x.keys.get(0); }
38static int max(Node x) { while (!x.leaf) x = x.kids.get(x.kids.size() - 1); return x.keys.get(x.keys.size() - 1); }

Best

O(log t · log_t n)

Average

O(t · log_t n)

Worst

O(t · log_t n)

Space

O(h)

B-tree: search, insertion with node splits, deletion with borrow and merge

Interactive · edit the input

B-tree (each box is one node) · 1 node

Node being examinedSearch pathKey found / new nodeChanged by split, borrow or mergeSibling used

Setup

Step 1 / 19

Java

1static int T = 2;                                // minimum degree: every node but the root holds T-1 .. 2T-1 keys
2static class Node {
3    List<Integer> keys = new ArrayList<>();
4    List<Node> kids = new ArrayList<>();         // empty in a leaf
5    boolean leaf = true;
6}
7static Node root = new Node();
8static boolean contains(Node x, int k) {
9    int i = 0;
10    while (i < x.keys.size() && k > x.keys.get(i)) i++;          // first key >= k
11    if (i < x.keys.size() && x.keys.get(i) == k) return true;
12    return !x.leaf && contains(x.kids.get(i), k);
13}
14static void splitChild(Node x, int i) {          // x.kids[i] is full (2T-1 keys)
15    Node y = x.kids.get(i), z = new Node();
16    z.leaf = y.leaf;
17    z.keys.addAll(y.keys.subList(T, 2 * T - 1));                 // the upper T-1 keys move to the new node
18    int median = y.keys.get(T - 1);
19    y.keys.subList(T - 1, 2 * T - 1).clear();                    // y keeps the lower T-1 keys
20    if (!y.leaf) { z.kids.addAll(y.kids.subList(T, 2 * T)); y.kids.subList(T, 2 * T).clear(); }
21    x.keys.add(i, median);                       // the median moves up
22    x.kids.add(i + 1, z);
23}
24static void insert(int k) {
25    if (contains(root, k)) return;
26    if (root.keys.size() == 2 * T - 1) {         // a full root: the tree grows in height here
27        Node s = new Node(); s.leaf = false; s.kids.add(root); root = s; splitChild(s, 0);
28    }
29    insertNonFull(root, k);
30}
31static void insertNonFull(Node x, int k) {
32    int i = 0;
33    while (i < x.keys.size() && k > x.keys.get(i)) i++;
34    if (x.leaf) { x.keys.add(i, k); return; }
35    if (x.kids.get(i).keys.size() == 2 * T - 1) {                // split a full child before descending
36        splitChild(x, i);
37        if (k > x.keys.get(i)) i++;
38    }
39    insertNonFull(x.kids.get(i), k);
40}
41static void delete(int k) {
42    delete(root, k);
43    if (root.keys.isEmpty() && !root.leaf) root = root.kids.get(0);   // the tree shrinks in height
44}
45static void delete(Node x, int k) {
46    int i = 0;
47    while (i < x.keys.size() && k > x.keys.get(i)) i++;
48    if (i < x.keys.size() && x.keys.get(i) == k) {
49        if (x.leaf) x.keys.remove(i);                            // case 1: the key is in a leaf
50        else if (x.kids.get(i).keys.size() >= T) {               // case 2a: use the predecessor
51            int pred = max(x.kids.get(i)); x.keys.set(i, pred); delete(x.kids.get(i), pred);
52        } else if (x.kids.get(i + 1).keys.size() >= T) {         // case 2b: use the successor
53            int succ = min(x.kids.get(i + 1)); x.keys.set(i, succ); delete(x.kids.get(i + 1), succ);
54        } else { merge(x, i); delete(x.kids.get(i), k); }        // case 2c: merge both children around the key
55    } else if (!x.leaf) {
56        if (x.kids.get(i).keys.size() == T - 1) {                // the child needs a spare key before we descend
57            if (i > 0 && x.kids.get(i - 1).keys.size() >= T) borrowFromLeft(x, i);          // case 3a
58            else if (i < x.keys.size() && x.kids.get(i + 1).keys.size() >= T) borrowFromRight(x, i);
59            else { if (i == x.keys.size()) i--; merge(x, i); }                               // case 3b
60        }
61        delete(x.kids.get(i), k);
62    }
63}
64static void merge(Node x, int i) {               // kids[i] + keys[i] + kids[i+1] become kids[i]
65    Node y = x.kids.get(i), z = x.kids.get(i + 1);
66    y.keys.add(x.keys.remove(i));
67    y.keys.addAll(z.keys);
68    y.kids.addAll(z.kids);
69    x.kids.remove(i + 1);
70}
71static void borrowFromLeft(Node x, int i) {
72    Node c = x.kids.get(i), s = x.kids.get(i - 1);
73    c.keys.add(0, x.keys.get(i - 1));
74    x.keys.set(i - 1, s.keys.remove(s.keys.size() - 1));
75    if (!s.leaf) c.kids.add(0, s.kids.remove(s.kids.size() - 1));
76}
77static void borrowFromRight(Node x, int i) {
78    Node c = x.kids.get(i), s = x.kids.get(i + 1);
79    c.keys.add(x.keys.get(i));
80    x.keys.set(i, s.keys.remove(0));
81    if (!s.leaf) c.kids.add(s.kids.remove(0));
82}
83static int min(Node x) { while (!x.leaf) x = x.kids.get(0); return x.keys.get(0); }
84static int max(Node x) { while (!x.leaf) x = x.kids.get(x.kids.size() - 1); return x.keys.get(x.keys.size() - 1); }

Live state

0 splits0 merges0 borrows

max keys

No condition evaluated on this step

Execution trace (dry run table)Show 19 steps

Step	Line	State	What happens
1	L1	t=2 max keys=3	A B-tree of minimum degree t = 2: every node except the root holds 1 to 3 keys, every internal node with m keys has m + 1 children, and all leaves are at the same depth. With t = 2 this is the 2-3-4 tree.
2	L34	t=2 max keys=3 inserted=10	10 goes into the leaf at position 0.
3	L34	t=2 max keys=3 inserted=20	20 goes into the leaf at position 1.
4	L34	t=2 max keys=3 inserted=5	5 goes into the leaf at position 0.
5	L26	t=2 max keys=3 inserted=6	The root is full: create a new empty root above it and split the old root. This is the only way a B-tree grows taller.
6	L16	t=2 max keys=3 median=10	Split the full node: its median 10 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
7	L1	t=2 max keys=3 inserted=6	Descend into child 0 of this node.
8	L34	t=2 max keys=3 inserted=6	6 goes into the leaf at position 1.
9	L1	t=2 max keys=3 inserted=12	Descend into child 1 of this node.
10	L34	t=2 max keys=3 inserted=12	12 goes into the leaf at position 0.
11	L1	t=2 max keys=3 inserted=30	Descend into child 1 of this node.
12	L34	t=2 max keys=3 inserted=30	30 goes into the leaf at position 2.
13	L1	t=2 max keys=3 inserted=7	Descend into child 0 of this node.
14	L34	t=2 max keys=3 inserted=7	7 goes into the leaf at position 2.
15	L1	t=2 max keys=3 inserted=17	Descend into child 1 of this node.
16	L35	t=2 max keys=3 inserted=17	The child is full (3 keys): split it before descending, so there is always room to push a key up.
17	L16	t=2 max keys=3 median=20	Split the full node: its median 20 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
18	L34	t=2 max keys=3 inserted=17	17 goes into the leaf at position 1.
19	L1	keys=8 height=1 t=2	8 keys in a tree of height 1: 2 splits, 0 borrows, 0 merges.

26.04.7

External memory motivation

Reading a disk page takes thousands of times longer than a comparison in memory, so the cost model of external-memory algorithms counts **page reads**. A balanced binary tree with a billion keys is about 30 levels deep, so a lookup can touch 30 pages. A B-tree with minimum degree 500 (nodes of up to 999 keys, which fit in a few kilobytes) has height at most log base 500 of (10^9 + 1) / 2, which is about 3.22, so **at most 3** (4 levels): a lookup reads at most 4 pages, and the top levels are usually cached in memory.

That is the design rule behind database and file-system indexes: make nodes as wide as a page, so the tree is shallow. The B-tree height bound h <= log_t((n + 1) / 2) is exactly the quantity the code computes.

Java

1// upper bound on the height (edges) of a B-tree with n keys and minimum degree t
2static int maxHeight(long n, int t) {
3    return (int) Math.floor(Math.log((n + 1) / 2.0) / Math.log(t));
4}
5// maxHeight(1_000_000_000L, 500) == 3: four levels, so a lookup reads at most 4 pages
6// maxHeight(1_000_000_000L, 2) == 28: a 2-3-4 tree is much deeper

Practice ladder

Now try it yourself

Easy

Design a B-tree page layout (concept)
Search in a Sorted Array of Pages

Medium

Implement B-tree search and insert
Implement a B-tree range count

Advanced

Implement B-tree deletion
Implement an LSM versus B-tree comparison (concept)

Key takeaways

A B-tree of minimum degree t keeps t - 1 to 2t - 1 keys per node and all leaves at one depth.
Insertion splits full nodes on the way down; the tree grows only when the root splits.
Deletion borrows from or merges with siblings so no node falls below the minimum.
The height is at most log_t((n + 1) / 2): a billion keys with t = 500 need at most 4 levels.
B-trees minimise page reads, which dominate the cost on disk.