B+Tree Indexing

Module promise

By the end of this module, a learner should be able to look at a database index and reason about it like an implementer, not like a user of a black box.

They should be able to answer questions like:

• Why does an index over millions of rows often need only a few page reads?
• Why does equality search route right when the key equals an internal separator?
• Why do leaf links make WHERE created_at BETWEEN ... fast?
• What exactly happens when an insert overflows a page?
• How can a test detect that a B+Tree is subtly broken even when Get works for a few keys?
• Why do databases bulk-load indexes instead of always inserting one row at a time?

This module starts from zero, but it does not stop at toy knowledge. The problems move from page arithmetic to search, range scan, insertion, invariant validation, and bottom-up bulk loading.

0. The pain before the data structure

Imagine a table with 100,000,000 rows.

You run:

SELECT * FROM transfers WHERE transaction_id = 88192377;

Without an index, the database may have to inspect page after page until it finds the row. That is not a clever algorithm. It is a full scan.

A binary search tree sounds better, but a normal pointer-heavy tree is the wrong mental model for a database. Databases do not want to chase one pointer per comparison. They read and write pages: commonly kilobytes at a time. Once a page is in memory, comparing dozens or hundreds of keys inside it is cheap compared with fetching another page.

A B+Tree is the page-aware answer:

• each node is a page,
• each page contains many sorted keys,
• internal pages route the search,
• leaf pages hold the actual key/value entries,
• leaves are linked so range scans can move sideways without repeatedly returning to the root.

A B+Tree is not “a fancy binary tree.” It is a disk/page layout discipline.

1. Vocabulary

Page

A fixed-size block of storage. In a real database, page size might be 4KB, 8KB, 16KB, or configurable. In the exercises, a node stands in for a page.

Key

The indexed value or tuple prefix used for ordering. In the exercises, keys are integers. In real databases, keys may be composite values like (tenant_id, created_at, id).

Value / payload

The data stored beside a key in the leaf. In a real secondary index, this might be a row identifier, primary key, tuple pointer, or included column payload. In this module, it is an integer value.

Internal node

A routing page. It stores sorted separator keys and child pointers.

For keys [10, 20, 40], the children represent ranges:

child 0: keys < 10
child 1: 10 <= keys < 20
child 2: 20 <= keys < 40
child 3: 40 <= keys

Equality goes right. If the search key is 20, it belongs in child 2, not child 1.

Leaf node

A data page. In this module, all actual key/value entries live in leaves.

Fanout

The number of children an internal page can point to. High fanout is the main reason B+Trees are shallow.

Height

The number of levels from root to leaves. A one-page tree with only a root leaf has height 1.

Separator key

A key stored in an internal node to decide which child to visit next. In this module, a separator is the first key of the child to its right.

Leaf link

A pointer from one leaf to the next leaf in sorted order. This makes range scans efficient.

2. Why fanout changes everything

Suppose an internal page can hold 200 child pointers.

Then:

• height 1: one leaf page,
• height 2: roughly 200 leaf pages,
• height 3: roughly 40,000 leaf pages,
• height 4: roughly 8,000,000 leaf pages,
• height 5: roughly 1,600,000,000 leaf pages.

This is the reason a database index over a huge table can still feel small. Every extra level multiplies the number of reachable pages by fanout.

The first exercise, btree-page-math, makes this concrete. It asks you to estimate leaf capacity, internal fanout, and height from simple page numbers.

The point is not to memorize exact database formulas. The point is to internalize the shape:

more keys per page -> bigger fanout -> lower height -> fewer page reads

3. Sorted keys inside a page

Every node stores sorted keys.

For a leaf:

keys:   [3, 8, 12]
values: [30, 80, 120]

The value for key 8 is 80.

For an internal node:

keys:     [10, 20]
children: [c0, c1, c2]

The keys do not store records. They route:

key < 10        -> c0
10 <= key < 20  -> c1
20 <= key       -> c2

This is where many learners get their first B+Tree bug. They route equality left, because they think “less than or equal.” In this module, equality routes right because the separator is the first key of the right subtree.

Use this routing rule:

choose the first separator greater than key;
if none exists, choose the rightmost child.

In code, this is often called upper_bound.

4. Search walkthrough

Consider this tree:

                    [10 | 20]
                  /    |     \
                 /     |      \
        [1, 4, 7]  [10, 13]  [20, 25, 30]

Search for 13:

1. Start at root [10, 20].
2. Find first separator greater than 13.
3. 20 is the first greater separator, so route to child 1.
4. Search leaf [10, 13].
5. Key found.

Search for 20:

1. Start at root [10, 20].
2. First separator greater than 20 does not exist.
3. Route to rightmost child.
4. Search leaf [20, 25, 30].
5. Key found.

Search for 9:

1. Start at root [10, 20].
2. First separator greater than 9 is 10.
3. Route to child 0.
4. Search leaf [1, 4, 7].
5. Stop when keys exceed 9, or scan the whole leaf.
6. Key not found.

The btree-search problem turns this into code.

5. Range scans: the reason leaves are linked

Now consider:

SELECT * FROM transfers
WHERE created_at >= '2026-01-01'
  AND created_at <= '2026-01-31'
ORDER BY created_at;

An equality search descends to one leaf.

A range scan does this:

1. Descend once using the lower bound.
2. Scan keys in that leaf.
3. Follow Next to the next leaf.
4. Continue until the upper bound is exceeded.

Example:

root: [10 | 20]

leaf1: [1, 4, 7]     -> leaf2: [10, 13, 18] -> leaf3: [20, 25, 30]

Range [6, 22]:

• descend using 6, landing in leaf1,
• return 7,
• follow to leaf2, return 10, 13, 18,
• follow to leaf3, return 20,
• stop at 25 because it exceeds 22.

Without leaf links, the implementation would need repeated searches or a more complicated traversal. With links, the scan is local and ordered.

The btree-range-scan problem teaches this exact pattern.

6. Insert: the smallest useful version

Insertion has three jobs:

1. Find the target leaf.
2. Insert or replace the key/value entry in sorted order.
3. If a node overflows, split it and push a separator upward.

In this module, Order means the maximum number of keys in a node.

If Order = 3, a node may hold at most three keys. After inserting a fourth key, it must split.

7. Leaf split walkthrough

Suppose a leaf has:

[1, 2, 3]

Insert 4 with Order = 3:

[1, 2, 3, 4]  // overflow

Split around the middle:

left:  [1, 2]
right: [3, 4]

Promote the first key of the right leaf:

promote 3

If this leaf was the root, create a new root:

          [3]
         /   \
    [1, 2]  [3, 4]

Notice that key 3 remains in the right leaf. In a B+Tree, leaf split promotion copies the separator upward. It does not remove the key from the leaf.

This is different from many B-Tree explanations, where promoted keys may move out of the child.

8. Internal split walkthrough

Suppose an internal node overflows:

keys:     [10, 20, 30, 40]
children: [c0, c1, c2, c3, c4]

With Order = 3, four keys is too many.

Pick the middle key:

promote 30

Left internal node:

keys:     [10, 20]
children: [c0, c1, c2]

Right internal node:

keys:     [40]
children: [c3, c4]

The promoted internal separator is removed from the split node and inserted into the parent.

This is another common bug: learners copy the internal promoted key upward but also keep it in the right child. That duplicates a routing separator and corrupts ranges.

9. Split propagation

A split returns three things to the parent:

splitHappened bool
promotedKey   int
rightNode     *Node

The parent inserts promotedKey into its own keys and inserts rightNode immediately after the child that split.

If the parent then overflows, it also splits and returns a promoted key to its parent.

This can cascade up to the root.

If the root splits, the tree height increases by one.

old root split result:
left root part, promoted key, right root part

new root:
[promoted key]
   /      \
 left    right

This is the core of btree-insert.

10. Full insertion trace with Order = 3

Insert keys 1, 2, 3:

[1, 2, 3]

Insert 4:

[1, 2, 3, 4] overflow

left:  [1, 2]
right: [3, 4]
promote 3

root:
        [3]
       /   \
  [1, 2]  [3, 4]

Insert 5:

        [3]
       /   \
  [1, 2]  [3, 4, 5]

Insert 6:

right leaf overflows: [3, 4, 5, 6]

split into:
[3, 4] and [5, 6]
promote 5

root becomes:
          [3, 5]
        /   |    \
  [1, 2] [3, 4] [5, 6]

Insert 7:

          [3, 5]
        /   |      \
  [1, 2] [3, 4] [5, 6, 7]

Insert 8:

leaf [5, 6, 7, 8] overflows
split into [5, 6] and [7, 8]
promote 7

root:
             [3, 5, 7]
          /    |    |    \
     [1,2] [3,4] [5,6] [7,8]

Insert 9:

             [3, 5, 7]
          /    |    |      \
     [1,2] [3,4] [5,6] [7,8,9]

Insert 10:

leaf [7,8,9,10] overflows
split into [7,8] and [9,10]
promote 9

root tries to become [3,5,7,9] and overflows

Now split the internal root:

[3,5,7,9]
 middle = 7

left internal:  [3,5]
right internal: [9]
promote 7

new root:
                  [7]
              /         \
          [3,5]         [9]
        /   |   \      /   \
    [1,2][3,4][5,6][7,8][9,10]

That trace is dense, but it is worth working through by hand. Most B+Tree implementation bugs are just wrong versions of one of these steps.

11. Invariant checklist

A B+Tree is correct because of its invariants. A solution that passes one happy-path lookup may still be broken.

A useful validator should check:

• every node has sorted keys,
• no node has more than Order keys,
• leaves have the same number of keys and values,
• internal nodes have len(children) == len(keys)+1,
• separator routing is correct,
• each internal separator equals the first key of its right subtree,
• all leaves are at the same depth,
• leaf Next links match the in-order leaf sequence.

The btree-validate problem makes learners write a tool that catches their own insert bugs. This is intentional. Professionals do not debug trees by staring at them; they build invariant checkers.

12. Bulk loading

Repeated inserts are general-purpose. They work for arbitrary order.

But if the input is already sorted, databases can build an index more directly:

1. Fill leaf pages from left to right.
2. Link the leaves.
3. Build the parent level from groups of children.
4. Repeat until only one root remains.

Example with leaf order 3:

pairs: 1 2 3 4 5 6 7 8

leaves:
[1,2,3] -> [4,5,6] -> [7,8]

parent separators:
[4,7]

Result:

          [4, 7]
       /    |     \
 [1,2,3] [4,5,6] [7,8]

Bulk loading is not just an academic exercise. It is the shape behind building an index on an existing table, importing sorted data, and rebuilding indexes during maintenance.

The btree-bulk-load problem asks learners to implement this bottom-up build.

13. Mapping this toy model to real databases

This module uses integer keys and in-memory pointers. Real engines add many constraints:

Composite keys

An index on (tenant_id, created_at, id) is ordered lexicographically:

tenant first, then created_at, then id

This explains the left-prefix rule. The index is very useful when the query constrains tenant_id; it is much less useful when the query only filters by created_at.

Covering indexes

If all needed columns are available inside the index leaf, the database may avoid visiting the table heap.

Secondary indexes

A secondary index leaf may store a row pointer or primary key, not the whole row.

Clustered indexes

Some systems store the table data itself in primary-key order. In that design, the primary index leaf is close to the table.

MVCC and visibility

Even if an index finds a row quickly, the engine may still need to check whether the row version is visible to the current transaction.

Page splits and write amplification

An insert may modify a leaf, one or more internal pages, sibling links, and log records. Random inserts can fragment pages. Sequential inserts can hotspot the right edge.

Prefix compression and deduplication

Real indexes often compress repeated prefixes or duplicate keys. The exercises intentionally skip this so the core algorithm is visible.

14. When a B+Tree is a good fit

B+Trees are strong for:

• equality lookup,
• range lookup,
• ordered scans,
• prefix queries over composite keys,
• ORDER BY support when order matches the index,
• min/max lookups.

They are weaker when:

• the query is not selective,
• the predicate does not match the index prefix,
• the workload is heavy random writes and another storage design is better,
• the access pattern is pure point lookup and a hash index is enough,
• the workload prefers log-structured merge trees.

Do not teach B+Trees as “the best index.” Teach them as a specific trade-off: ordered data, high fanout, shallow height, excellent range scans.

15. Implementation patterns learners should steal

1. Separate routing from leaf search

Internal routing uses “first separator greater than key.”

Leaf lookup uses “first key greater than or equal to key.”

These are different.

2. Return split information upward

Do not let children mutate parents directly. Make the child return:

split, promotedKey, rightNode

That keeps the recursion understandable.

3. Keep leaf split and internal split separate

They promote differently.

Leaf split:

copy first key of right leaf upward

Internal split:

move middle separator upward

4. Test with permutations

Sorted inserts test right-edge growth. Random order tests routing. Reversed order tests left-side splitting. Replacing existing keys tests duplicate handling.

5. Build a validator

A validator turns a vague “my tree is broken” into a concrete failed invariant.

16. Problem ladder

Problem 1: btree-page-math

Learn why B+Trees are shallow. Estimate leaf capacity, internal fanout, and height.

Core idea:

height = 1 + number of internal levels needed to cover all leaf pages

Problem 2: btree-search

Implement equality lookup.

Core idea:

internal: upper_bound separator routing
leaf: lower_bound key lookup

Problem 3: btree-range-scan

Implement ordered range scan using leaf links.

Core idea:

descend once, then move sideways through leaves

Problem 4: btree-insert

Insert or replace keys while splitting overflowing nodes.

Core idea:

insert into child; if child split, absorb promoted key; if this node overflows, split too

Problem 5: btree-validate

Write an invariant checker.

Core idea:

correctness is a set of structural promises, not just successful lookup

Problem 6: btree-bulk-load

Build a B+Tree bottom-up from sorted pairs.

Core idea:

fill leaves, link leaves, group children into parent pages, repeat

17. Debugging guide

When Get fails after insertion:

1. Print the tree level by level.
2. Check internal routing for equality.
3. Check whether leaf split promoted the first key of the right leaf.
4. Check whether internal split removed the promoted key from the child.
5. Check whether child insertion placed the new right child at idx+1.
6. Check leaf Next links.
7. Run the validator.

When range scan returns duplicates:

1. Check if a leaf key was copied into both leaves incorrectly.
2. Check if Next creates a cycle.
3. Check if the range loop fails to stop after key > hi.

When sorted inserts work but random inserts fail:

1. Internal routing is likely wrong.
2. Parent child insertion index may be wrong.
3. Separator keys may not match right-subtree minimum keys.

When random inserts work but replacements fail:

1. The leaf insert path probably inserts duplicate keys instead of updating the existing value.

18. Suggested learner workflow

For each problem:

1. Read the statement once.
2. Draw the smallest example by hand.
3. Write the helper for “find position.”
4. Implement the simplest correct version.
5. Run public tests.
6. Add one personal test before checking hidden tests.
7. Read the walkthrough after getting stuck for more than ten minutes.
8. Compare against the reference solution only after you can explain the invariant.

The goal is not to hide the answer. The goal is to make the learner strong enough to recognize why the answer works.

19. What “professional level” means here

A professional learner should be able to:

• implement search, range scan, insert, validation, and bulk loading,
• explain equality routing at separators,
• estimate index height from page capacity,
• reason about why range scans are fast,
• identify common split bugs,
• connect the toy implementation to real database query planning,
• write tests that expose structural corruption.

That is the standard for this module.