B-Trees

The memory-disk gap

Main memory is fast but limited. Databases must store far more data than fits in RAM, so most data lives on disk (SSD or HDD).

• Random disk read: ~100 μs (SSD) or ~10 ms (HDD)
• Random RAM access: ~100 ns — three to five orders of magnitude faster
• Sequential disk reads are much cheaper than random — amortise seek cost over large blocks
• OS reads data in fixed-size pages (typically 4 KB); databases use 8–16 KB pages

Minimising I/O

The dominant cost in disk-based data structures is the number of disk page reads/writes. An ideal index structure:

• Keeps the tree short so search touches few pages
• Packs many keys per node so each page read yields maximum information
• Maintains balance to guarantee worst-case performance
• Exploits sequential access patterns where possible

Anatomy of a B-tree node

Each node occupies one disk page and contains interleaved keys and child pointers:

+----+----+----+----+----+----+----+----+----+
| P0 | K1 | P1 | K2 | P2 | K3 | P3 |... | Pn |
+----+----+----+----+----+----+----+----+----+

Ki = key i (sorted)
Pi = pointer to child i (disk page address)

• Keys stored in sorted order within the node
• Pointers (child page addresses) interleave with keys
• Leaf nodes have no child pointers (or null pointers)
• Each node may also store associated data values (B-tree) or just keys (B+ tree)

Typical sizing

Algorithm

BTREE-SEARCH(node, key):
    i = 0
    while i < node.num_keys
          and key > node.keys[i]:
        i += 1
    if i < node.num_keys
       and key == node.keys[i]:
        return (node, i)        // found
    if node.is_leaf:
        return NOT_FOUND
    DISK-READ(node.children[i]) // 1 I/O
    return BTREE-SEARCH(
        node.children[i], key)

Cost analysis

• Each level requires one disk read
• Within a node: binary search over keys — O(log m) comparisons (CPU, cheap)
• Total disk I/Os: O(log_t n)
• Total CPU comparisons: O(log n)

Example: searching for key 42

Algorithm overview

1. Search for the correct leaf node
2. If the leaf has room, insert the key in sorted position — done
3. If the leaf is full (m − 1 keys), split the node

Proactive (preemptive) splitting

Instead of splitting bottom-up after overflow, split any full node encountered on the way down during the search:

• At most one split per level
• The parent always has room for the promoted key
• Single-pass insertion — no need to backtrack up the tree

Insertion example (order 5)

Insert 25 into a full leaf:

Before:  [10 | 20 | 30 | 40]  ← full

Step 1: Split at median (30)

          [30]         ← promoted
         /    \
   [10|20]  [30|40]

Step 2: Insert 25

          [30]
         /    \
  [10|20|25] [30|40]   ← done

Split algorithm

SPLIT-CHILD(parent, i):
    full = parent.children[i]  // m-1 keys
    median = full.keys[t-1]
    new = allocate_page()

    // Right half → new node
    new.keys = full.keys[t .. m-1]
    new.children = full.children[t .. m]

    // Left half stays
    full.num_keys = t - 1

    // Promote median to parent
    insert median at parent.keys[i]
    parent.children[i+1] = new

    DISK-WRITE(full)    // 3 writes
    DISK-WRITE(new)     // per split
    DISK-WRITE(parent)

Split cost

Borrowing from a sibling

Before (right sibling has spare keys):

  Parent:  [...| 30 |...]
             /       \
  Child: [10|20]  [35|40|50|60]

After rotation:

  Parent:  [...| 35 |...]
             /       \
  Child: [10|20|30] [40|50|60]

Key 30 demoted, key 35 promoted.

Merging two nodes

Before (both have t-1 keys):

  Parent:  [...| 30 |...]
             /       \
  Child: [10|20]   [35|40]

After merge:

  Parent:  [...]     ← 30 pulled down
             |
  Merged: [10|20|30|35|40]

Algorithm

RANGE-QUERY(tree, low, high):
    leaf = search for leaf containing low
    results = []
    while leaf is not null:
        for each (key, val) in leaf:
            if key > high:
                return results
            if key >= low:
                results.append((key, val))
        leaf = leaf.next_leaf
    return results

Cost analysis

k = result size, b = keys per leaf

Why this matters

SELECT * FROM orders
WHERE order_date
  BETWEEN '2025-01-01' AND '2025-03-31'
ORDER BY order_date;

• B+ tree on order_date: find the first matching leaf, then scan sequentially
• The leaf linked list provides data already sorted — no additional sort step
• Adjacent leaves are often physically adjacent on disk — sequential I/O

Two-to-three split

When node overflows and sibling is full:

Before:  [A B C D] [E F G H]  ← both full

Redistribute across three nodes:

After:   [A B C] [D E] [F G H]
         separator keys promoted

Benefits

The external memory model

• Memory holds M elements
• Disk transfers data in blocks of B elements
• Cost metric: number of block transfers (I/Os)

Fanout and tree height

Fanout f = page_size / (key + ptr)

Example: 16 KB page, 8B keys, 8B ptrs
f = 16384 / 16 = 1024

Height for n = 10^9:
h = ceil(log_1024(10^9))
  = ceil(3.0) = 3

I/O costs comparison

Other databases

Other file systems

The write amplification problem

B-trees write an entire page for each modified key. If a page holds 500 keys but only one changed, you still write the full page.

Fractal trees (Buffered B-trees)

Each internal node has a message buffer. Writes are inserted into the buffer at the root and lazily pushed down.

     [30 | 60]
     buffer: [ins(45), del(12)]
    /    |    \
 [...]  [...] [...]
 Messages trickle down over time

Other write-optimised structures

Choosing page size

• Larger pages = higher fanout = shallower tree = fewer I/Os
• Larger pages = more wasted space if nodes are sparse
• SSD: 4–16 KB pages work well
• HDD: larger pages amortise seek latency

Bulk loading

Instead of inserting one by one, build bottom-up:

1. Sort all keys
2. Fill leaf pages sequentially (100% full)
3. Build internal pages from leaf separators
4. Result: compact tree, one sequential write pass

Concurrency control

Key takeaways

• B-trees are the dominant on-disk index structure because they minimise disk I/O through high fanout and guaranteed balance
• Order-1000 B-tree can index a billion keys in 3–4 levels
• B+ trees keep all data in leaves with a linked list — range queries and sequential scans are fast
• Proactive splitting/fix-up enable single-pass, top-down algorithms
• B-trees power indexes in virtually every relational database and many file systems
• LSM-trees trade read performance for write throughput; fractal trees reduce write amplification
• The right choice depends on workload: read-heavy → B-trees, write-heavy → LSM-trees

Recommended reading