PK

PKBytes

Explore tracks
Chapter 26: Self-Balancing Search Trees and B-Trees
26.05Intermediate / Advanced5 topics16 min3 interactive animations

B+ trees

B+ trees: internal and leaf nodes, chained leaves, range scans, index pages and how they differ from B-trees.

Learning goals

  • Describe what internal nodes and leaves store in a B+ tree
  • Follow a leaf split and compare it with an internal split
  • Run a range scan with one descent and a walk along the leaf chain
  • Estimate fan-out and index depth from the page size
  • State the trade-offs against a plain B-tree

Prerequisites

B-trees and storage indexes

Most database indexes are B+ trees. They put every record in the leaves and link the leaves in order, which makes range queries and full scans as cheap as reading a sequential file.

26.05.1

Internal vs leaf nodes

In a **B+ tree** the internal nodes hold only **separator keys** that guide the search, and **all the data** lives in the leaves. A separator that equals a key may appear in an internal node and again in a leaf: it is a copy. Because internal nodes carry no data, they can hold more separators per page, which makes the tree shallower.

Run the “Leaf split, separator copied up” preset: inserting 10, 20, 30, 40 with at most 3 keys per node overflows the leaf, which splits into [10 20] and [30 40]; the separator 30 is **copied** up to the new root and is still in the right leaf. When an **internal** node overflows, its middle separator **moves** up instead, because internal keys carry no data to preserve.

Java
1static final int CAP = 3;                        // maximum keys per node
2static class Node {
3    boolean leaf = true;
4    List<Integer> keys = new ArrayList<>();
5    List<Node> kids = new ArrayList<>();         // internal nodes only
6    Node next;                                   // leaves only: the next leaf in key order
7}
8static Node root = new Node();
9static Object[] insert(Node n, int k) {          // null, or {separator, new right sibling} after a split
10    if (n.leaf) {
11        int i = 0;
12        while (i < n.keys.size() && n.keys.get(i) < k) i++;
13        if (i < n.keys.size() && n.keys.get(i) == k) return null;
14        n.keys.add(i, k);
15        if (n.keys.size() <= CAP) return null;
16        int mid = (n.keys.size() + 1) / 2;
17        Node right = new Node();
18        right.keys.addAll(n.keys.subList(mid, n.keys.size()));
19        n.keys.subList(mid, n.keys.size()).clear();
20        right.next = n.next; n.next = right;     // splice the new leaf into the chain
21        return new Object[]{right.keys.get(0), right};            // the separator is COPIED up
22    }
23    int i = 0;
24    while (i < n.keys.size() && k >= n.keys.get(i)) i++;          // an equal key lives in the right subtree
25    Object[] up = insert(n.kids.get(i), k);
26    if (up == null) return null;
27    n.keys.add(i, (Integer) up[0]);
28    n.kids.add(i + 1, (Node) up[1]);
29    if (n.keys.size() <= CAP) return null;
30    int mid = n.keys.size() / 2;
31    int sep = n.keys.get(mid);                   // an internal separator MOVES up
32    Node right = new Node(); right.leaf = false;
33    right.keys.addAll(n.keys.subList(mid + 1, n.keys.size()));
34    right.kids.addAll(n.kids.subList(mid + 1, n.kids.size()));
35    n.keys.subList(mid, n.keys.size()).clear();
36    n.kids.subList(mid + 1, n.kids.size()).clear();
37    return new Object[]{sep, right};
38}
39static void add(int k) {
40    Object[] up = insert(root, k);
41    if (up != null) {                            // the root split: the tree grows in height
42        Node r = new Node(); r.leaf = false;
43        r.keys.add((Integer) up[0]); r.kids.add(root); r.kids.add((Node) up[1]);
44        root = r;
45    }
46}

B+ tree: keys in leaves, copied separators, chained leaves and range scans

Interactive · edit the input

Your input

Try

B+ tree (data only in the leaves) · 1 node

·

leaf

Node being examinedSearch pathKey in the range / new nodeChanged by a split

leaf chain (left to right)

[]
Setup

A B+ tree keeps every key in the leaves, which are chained left to right; internal nodes hold only separators. Nodes hold at most 3 keys here.

Step 1 / 15
Java
1static final int CAP = 3;                        // maximum keys per node
2static class Node {
3    boolean leaf = true;
4    List<Integer> keys = new ArrayList<>();
5    List<Node> kids = new ArrayList<>();         // internal nodes only
6    Node next;                                   // leaves only: the next leaf in key order
7}
8static Node root = new Node();
9static Object[] insert(Node n, int k) {          // null, or {separator, new right sibling} after a split
10    if (n.leaf) {
11        int i = 0;
12        while (i < n.keys.size() && n.keys.get(i) < k) i++;
13        if (i < n.keys.size() && n.keys.get(i) == k) return null;
14        n.keys.add(i, k);
15        if (n.keys.size() <= CAP) return null;
16        int mid = (n.keys.size() + 1) / 2;
17        Node right = new Node();
18        right.keys.addAll(n.keys.subList(mid, n.keys.size()));
19        n.keys.subList(mid, n.keys.size()).clear();
20        right.next = n.next; n.next = right;     // splice the new leaf into the chain
21        return new Object[]{right.keys.get(0), right};            // the separator is COPIED up
22    }
23    int i = 0;
24    while (i < n.keys.size() && k >= n.keys.get(i)) i++;          // an equal key lives in the right subtree
25    Object[] up = insert(n.kids.get(i), k);
26    if (up == null) return null;
27    n.keys.add(i, (Integer) up[0]);
28    n.kids.add(i + 1, (Node) up[1]);
29    if (n.keys.size() <= CAP) return null;
30    int mid = n.keys.size() / 2;
31    int sep = n.keys.get(mid);                   // an internal separator MOVES up
32    Node right = new Node(); right.leaf = false;
33    right.keys.addAll(n.keys.subList(mid + 1, n.keys.size()));
34    right.kids.addAll(n.kids.subList(mid + 1, n.kids.size()));
35    n.keys.subList(mid, n.keys.size()).clear();
36    n.kids.subList(mid + 1, n.kids.size()).clear();
37    return new Object[]{sep, right};
38}
39static void add(int k) {
40    Object[] up = insert(root, k);
41    if (up != null) {                            // the root split: the tree grows in height
42        Node r = new Node(); r.leaf = false;
43        r.keys.add((Integer) up[0]); r.kids.add(root); r.kids.add((Node) up[1]);
44        root = r;
45    }
46}
47static List<Integer> range(int lo, int hi) {
48    Node n = root;
49    while (!n.leaf) {                            // descend to the leaf that would hold lo
50        int i = 0;
51        while (i < n.keys.size() && lo >= n.keys.get(i)) i++;
52        n = n.kids.get(i);
53    }
54    List<Integer> out = new ArrayList<>();
55    for (; n != null; n = n.next) {              // then walk the chained leaves
56        for (int key : n.keys) {
57            if (key > hi) return out;
58            if (key >= lo) out.add(key);
59        }
60    }
61    return out;
62}

Live state

0 splits0 leaves read

max keys

3

No condition evaluated on this step
Execution trace (dry run table)Show 15 steps
StepLineStateWhat happens
1L1max keys=3A B+ tree keeps every key in the leaves, which are chained left to right; internal nodes hold only separators. Nodes hold at most 3 keys here.
2L14max keys=3 inserted=1010 goes into the leaf [10] (1 of at most 3 keys).
3L14max keys=3 inserted=2020 goes into the leaf [10 20] (2 of at most 3 keys).
4L14max keys=3 inserted=55 goes into the leaf [5 10 20] (3 of at most 3 keys).
5L14max keys=3 inserted=66 goes into the leaf [5 6 10 20] (4 of at most 3 keys).
6L21max keys=3 separator=10The leaf overflowed: split it into [5 6] and [10 20]. The separator 10 is COPIED up; it also stays in the right leaf, because leaves hold all the data.
7L41max keys=3 separator=10The root split, so a new root with the single separator 10 is created: the tree is one level taller.
8L14max keys=3 inserted=1212 goes into the leaf [10 12 20] (3 of at most 3 keys).
9L14max keys=3 inserted=3030 goes into the leaf [10 12 20 30] (4 of at most 3 keys).
10L21max keys=3 separator=20The leaf overflowed: split it into [10 12] and [20 30]. The separator 20 is COPIED up; it also stays in the right leaf, because leaves hold all the data.
11L28max keys=3 separator=20The parent takes the new separator 20: 2 of at most 3 keys.
12L14max keys=3 inserted=77 goes into the leaf [5 6 7] (3 of at most 3 keys).
13L14max keys=3 inserted=1717 goes into the leaf [10 12 17] (3 of at most 3 keys).
14L14max keys=3 inserted=2525 goes into the leaf [20 25 30] (3 of at most 3 keys).
15L1keys=9 height=1 splits=29 keys in 3 leaves, tree height 1, 2 splits.
26.05.2

Leaf chaining

The leaves are linked into a **chain** in key order (a singly or doubly linked list). The animation draws the chain as a row of leaves under the tree. When a leaf splits, the new leaf is spliced in right after the old one, so the chain stays sorted without touching the internal nodes.

The chain turns the leaf level into a sorted file: you can read all keys in order, from the smallest leaf to the largest, without ever visiting an internal node again. In the “Sorted input fills the leaves” preset the 10 sorted keys end in 5 chained leaves, in a tree of height 2 after 5 splits.

B+ tree: keys in leaves, copied separators, chained leaves and range scans

Interactive · edit the input

Your input

Try

B+ tree (data only in the leaves) · 1 node

·

leaf

Node being examinedSearch pathKey in the range / new nodeChanged by a split

leaf chain (left to right)

[]
Setup

A B+ tree keeps every key in the leaves, which are chained left to right; internal nodes hold only separators. Nodes hold at most 3 keys here.

Step 1 / 15
Java
1static final int CAP = 3;                        // maximum keys per node
2static class Node {
3    boolean leaf = true;
4    List<Integer> keys = new ArrayList<>();
5    List<Node> kids = new ArrayList<>();         // internal nodes only
6    Node next;                                   // leaves only: the next leaf in key order
7}
8static Node root = new Node();
9static Object[] insert(Node n, int k) {          // null, or {separator, new right sibling} after a split
10    if (n.leaf) {
11        int i = 0;
12        while (i < n.keys.size() && n.keys.get(i) < k) i++;
13        if (i < n.keys.size() && n.keys.get(i) == k) return null;
14        n.keys.add(i, k);
15        if (n.keys.size() <= CAP) return null;
16        int mid = (n.keys.size() + 1) / 2;
17        Node right = new Node();
18        right.keys.addAll(n.keys.subList(mid, n.keys.size()));
19        n.keys.subList(mid, n.keys.size()).clear();
20        right.next = n.next; n.next = right;     // splice the new leaf into the chain
21        return new Object[]{right.keys.get(0), right};            // the separator is COPIED up
22    }
23    int i = 0;
24    while (i < n.keys.size() && k >= n.keys.get(i)) i++;          // an equal key lives in the right subtree
25    Object[] up = insert(n.kids.get(i), k);
26    if (up == null) return null;
27    n.keys.add(i, (Integer) up[0]);
28    n.kids.add(i + 1, (Node) up[1]);
29    if (n.keys.size() <= CAP) return null;
30    int mid = n.keys.size() / 2;
31    int sep = n.keys.get(mid);                   // an internal separator MOVES up
32    Node right = new Node(); right.leaf = false;
33    right.keys.addAll(n.keys.subList(mid + 1, n.keys.size()));
34    right.kids.addAll(n.kids.subList(mid + 1, n.kids.size()));
35    n.keys.subList(mid, n.keys.size()).clear();
36    n.kids.subList(mid + 1, n.kids.size()).clear();
37    return new Object[]{sep, right};
38}
39static void add(int k) {
40    Object[] up = insert(root, k);
41    if (up != null) {                            // the root split: the tree grows in height
42        Node r = new Node(); r.leaf = false;
43        r.keys.add((Integer) up[0]); r.kids.add(root); r.kids.add((Node) up[1]);
44        root = r;
45    }
46}
47static List<Integer> range(int lo, int hi) {
48    Node n = root;
49    while (!n.leaf) {                            // descend to the leaf that would hold lo
50        int i = 0;
51        while (i < n.keys.size() && lo >= n.keys.get(i)) i++;
52        n = n.kids.get(i);
53    }
54    List<Integer> out = new ArrayList<>();
55    for (; n != null; n = n.next) {              // then walk the chained leaves
56        for (int key : n.keys) {
57            if (key > hi) return out;
58            if (key >= lo) out.add(key);
59        }
60    }
61    return out;
62}

Live state

0 splits0 leaves read

max keys

3

No condition evaluated on this step
Execution trace (dry run table)Show 15 steps
StepLineStateWhat happens
1L1max keys=3A B+ tree keeps every key in the leaves, which are chained left to right; internal nodes hold only separators. Nodes hold at most 3 keys here.
2L14max keys=3 inserted=1010 goes into the leaf [10] (1 of at most 3 keys).
3L14max keys=3 inserted=2020 goes into the leaf [10 20] (2 of at most 3 keys).
4L14max keys=3 inserted=55 goes into the leaf [5 10 20] (3 of at most 3 keys).
5L14max keys=3 inserted=66 goes into the leaf [5 6 10 20] (4 of at most 3 keys).
6L21max keys=3 separator=10The leaf overflowed: split it into [5 6] and [10 20]. The separator 10 is COPIED up; it also stays in the right leaf, because leaves hold all the data.
7L41max keys=3 separator=10The root split, so a new root with the single separator 10 is created: the tree is one level taller.
8L14max keys=3 inserted=1212 goes into the leaf [10 12 20] (3 of at most 3 keys).
9L14max keys=3 inserted=3030 goes into the leaf [10 12 20 30] (4 of at most 3 keys).
10L21max keys=3 separator=20The leaf overflowed: split it into [10 12] and [20 30]. The separator 20 is COPIED up; it also stays in the right leaf, because leaves hold all the data.
11L28max keys=3 separator=20The parent takes the new separator 20: 2 of at most 3 keys.
12L14max keys=3 inserted=77 goes into the leaf [5 6 7] (3 of at most 3 keys).
13L14max keys=3 inserted=1717 goes into the leaf [10 12 17] (3 of at most 3 keys).
14L14max keys=3 inserted=2525 goes into the leaf [20 25 30] (3 of at most 3 keys).
15L1keys=9 height=1 splits=29 keys in 3 leaves, tree height 1, 2 splits.
26.05.3

Range scans

A **range scan** for [lo, hi] descends **once** to the leaf that would contain lo, then walks the chain to the right, reading keys until one exceeds hi. The cost is the height for the descent plus one page per leaf visited: O(log n + k / B) page reads for k results and B keys per page. A plain B-tree would have to climb back up and down through internal nodes to move between leaves.

The “Range scan [7, 20]” preset on the keys 10, 20, 5, 6, 12, 30, 7, 17, 25 returns [7, 10, 12, 17, 20] by reading 3 leaves after one descent. The “Range scan with no matches” preset ([21, 29] over 10, 20, 30, 40, 50) still reads 2 leaves: the one where 21 would be and the next one, which shows a key above 29.

Java
1static List<Integer> range(int lo, int hi) {
2    Node n = root;
3    while (!n.leaf) {                            // descend once to the leaf that would hold lo
4        int i = 0;
5        while (i < n.keys.size() && lo >= n.keys.get(i)) i++;
6        n = n.kids.get(i);
7    }
8    List<Integer> out = new ArrayList<>();
9    for (; n != null; n = n.next) {              // then walk the chained leaves
10        for (int key : n.keys) {
11            if (key > hi) return out;
12            if (key >= lo) out.add(key);
13        }
14    }
15    return out;
16}

Best

O(log n)

Average

O(log n + k)

Worst

O(log n + k)

Space

O(1) beyond the output

B+ tree: keys in leaves, copied separators, chained leaves and range scans

Interactive · edit the input

Your input

Try

B+ tree (data only in the leaves) · 1 node

·

leaf

Node being examinedSearch pathKey in the range / new nodeChanged by a split

leaf chain (left to right)

[]
Setup

A B+ tree keeps every key in the leaves, which are chained left to right; internal nodes hold only separators. Nodes hold at most 3 keys here.

Step 1 / 15
Java
1static final int CAP = 3;                        // maximum keys per node
2static class Node {
3    boolean leaf = true;
4    List<Integer> keys = new ArrayList<>();
5    List<Node> kids = new ArrayList<>();         // internal nodes only
6    Node next;                                   // leaves only: the next leaf in key order
7}
8static Node root = new Node();
9static Object[] insert(Node n, int k) {          // null, or {separator, new right sibling} after a split
10    if (n.leaf) {
11        int i = 0;
12        while (i < n.keys.size() && n.keys.get(i) < k) i++;
13        if (i < n.keys.size() && n.keys.get(i) == k) return null;
14        n.keys.add(i, k);
15        if (n.keys.size() <= CAP) return null;
16        int mid = (n.keys.size() + 1) / 2;
17        Node right = new Node();
18        right.keys.addAll(n.keys.subList(mid, n.keys.size()));
19        n.keys.subList(mid, n.keys.size()).clear();
20        right.next = n.next; n.next = right;     // splice the new leaf into the chain
21        return new Object[]{right.keys.get(0), right};            // the separator is COPIED up
22    }
23    int i = 0;
24    while (i < n.keys.size() && k >= n.keys.get(i)) i++;          // an equal key lives in the right subtree
25    Object[] up = insert(n.kids.get(i), k);
26    if (up == null) return null;
27    n.keys.add(i, (Integer) up[0]);
28    n.kids.add(i + 1, (Node) up[1]);
29    if (n.keys.size() <= CAP) return null;
30    int mid = n.keys.size() / 2;
31    int sep = n.keys.get(mid);                   // an internal separator MOVES up
32    Node right = new Node(); right.leaf = false;
33    right.keys.addAll(n.keys.subList(mid + 1, n.keys.size()));
34    right.kids.addAll(n.kids.subList(mid + 1, n.kids.size()));
35    n.keys.subList(mid, n.keys.size()).clear();
36    n.kids.subList(mid + 1, n.kids.size()).clear();
37    return new Object[]{sep, right};
38}
39static void add(int k) {
40    Object[] up = insert(root, k);
41    if (up != null) {                            // the root split: the tree grows in height
42        Node r = new Node(); r.leaf = false;
43        r.keys.add((Integer) up[0]); r.kids.add(root); r.kids.add((Node) up[1]);
44        root = r;
45    }
46}
47static List<Integer> range(int lo, int hi) {
48    Node n = root;
49    while (!n.leaf) {                            // descend to the leaf that would hold lo
50        int i = 0;
51        while (i < n.keys.size() && lo >= n.keys.get(i)) i++;
52        n = n.kids.get(i);
53    }
54    List<Integer> out = new ArrayList<>();
55    for (; n != null; n = n.next) {              // then walk the chained leaves
56        for (int key : n.keys) {
57            if (key > hi) return out;
58            if (key >= lo) out.add(key);
59        }
60    }
61    return out;
62}

Live state

0 splits0 leaves read

max keys

3

No condition evaluated on this step
Execution trace (dry run table)Show 15 steps
StepLineStateWhat happens
1L1max keys=3A B+ tree keeps every key in the leaves, which are chained left to right; internal nodes hold only separators. Nodes hold at most 3 keys here.
2L14max keys=3 inserted=1010 goes into the leaf [10] (1 of at most 3 keys).
3L14max keys=3 inserted=2020 goes into the leaf [10 20] (2 of at most 3 keys).
4L14max keys=3 inserted=55 goes into the leaf [5 10 20] (3 of at most 3 keys).
5L14max keys=3 inserted=66 goes into the leaf [5 6 10 20] (4 of at most 3 keys).
6L21max keys=3 separator=10The leaf overflowed: split it into [5 6] and [10 20]. The separator 10 is COPIED up; it also stays in the right leaf, because leaves hold all the data.
7L41max keys=3 separator=10The root split, so a new root with the single separator 10 is created: the tree is one level taller.
8L14max keys=3 inserted=1212 goes into the leaf [10 12 20] (3 of at most 3 keys).
9L14max keys=3 inserted=3030 goes into the leaf [10 12 20 30] (4 of at most 3 keys).
10L21max keys=3 separator=20The leaf overflowed: split it into [10 12] and [20 30]. The separator 20 is COPIED up; it also stays in the right leaf, because leaves hold all the data.
11L28max keys=3 separator=20The parent takes the new separator 20: 2 of at most 3 keys.
12L14max keys=3 inserted=77 goes into the leaf [5 6 7] (3 of at most 3 keys).
13L14max keys=3 inserted=1717 goes into the leaf [10 12 17] (3 of at most 3 keys).
14L14max keys=3 inserted=2525 goes into the leaf [20 25 30] (3 of at most 3 keys).
15L1keys=9 height=1 splits=29 keys in 3 leaves, tree height 1, 2 splits.
26.05.4

Index pages

A database index stores one node per **page** (commonly 4 KB to 16 KB). The **fan-out** of an internal node, how many children it has, is the page size divided by the size of one (key, child pointer) pair. With 4,096-byte pages and 16 bytes per entry that is 256 children; a leaf holds about as many (key, record pointer) entries.

The depth of the index then follows from n: each level multiplies the reach by the fan-out. With 255 keys per leaf and a fan-out of 256, a billion rows need about 3.9 million leaves, 15.3 thousand pages above them, then 60, then the root: 4 levels, so any row is reached in at most 4 page reads, usually fewer because the upper levels stay in memory.

Java
1// levels of a B+ tree index for n rows: leaves hold leafCap keys, internal nodes have fanOut children
2static int levels(long n, int leafCap, int fanOut) {
3    long pages = (n + leafCap - 1) / leafCap;    // leaf pages
4    int levels = 1;
5    while (pages > 1) {
6        pages = (pages + fanOut - 1) / fanOut;   // pages one level up
7        levels++;
8    }
9    return levels;
10}
11// levels(1_000_000_000L, 255, 256) == 4
26.05.5

B+ tree vs B-tree

Both are shallow, page-sized, multiway search trees. The differences decide which one a system uses. In a **B-tree** every key, with its data, can live in an internal node, so a lookup can stop early; in a **B+ tree** data lives only in the leaves, so every lookup reaches a leaf but internal nodes are smaller and the tree is shallower, and the leaf chain makes range scans and ordered iteration fast.

Databases and file systems overwhelmingly choose B+ trees for the range-scan behaviour and for the predictable cost of a lookup (always the same depth). B-trees appear where point lookups dominate and the data is small.

B-treeB+ tree
Where data livesin every nodeonly in the leaves
Internal node holdskeys with data and pointersseparator keys and pointers only
Fan-out for the same page sizelowerhigher, so a shallower tree
Lookup costmay stop at an internal nodealways one leaf: the same depth every time
Range scan / full scanneeds an inorder traversal up and downwalk the leaf chain
Duplicates of a keynone across nodesseparators repeat keys that exist in leaves

Practice ladder

Now try it yourself

Easy

  • Search in a B+ tree (concept)
  • Merge Sorted Pages

Medium

  • Implement B+ tree insert
  • Implement a B+ tree range query

Advanced

  • Implement B+ tree deletion
  • Bulk-load a B+ tree from sorted data

Key takeaways

  • B+ tree leaves hold all the data; internal nodes hold only separators.
  • A leaf split copies the separator up; an internal split moves it up.
  • Leaves are chained, so a range scan needs one descent and then a walk along the chain.
  • Fan-out is page size divided by entry size; a billion rows fit in about 4 levels.
  • Databases choose B+ trees for range scans and uniform lookup cost.