B-Trees & B+ Trees — Data Structures Course

What you'll learn

A B-tree is a balanced tree that holds many keys per node and has many children. That shape makes it short and wide — perfect for data on disk, which is why databases and file systems are built on B-trees and B+ trees.

By the end you'll be able to:

Explain why binary trees are a poor fit for disk
Describe a B-tree node and how insertion splits a full node
Say what a B+ tree adds and why databases use it

Why not binary?

Reading from disk is thousands of times slower than reading from memory, and it happens in big fixed-size blocks. A binary search tree of a billion keys is ~30 levels deep — that's up to 30 slow disk reads per lookup. A B-tree packs hundreds of keys into each node (one block), so it's only ~3–4 levels deep: far fewer disk reads.

Key idea

The idea: make each node as big as one disk block. More keys per node → fewer levels → fewer disk reads. Height is O(log_m n) where m (the branching factor) is large.

B-tree structure

A B-tree of order m obeys these rules:

Each node holds up to m − 1 sorted keys and up to m children.
A node's keys separate its children's ranges (like a multi-way BST).
All leaves are at the same depth — the tree is perfectly height-balanced.

Insertion & splitting

Insert a key into the correct leaf. If that node overflows (too many keys), it splits: the middle key moves up into the parent, and the node becomes two. Splits can cascade upward — and when the root splits, the tree grows one level taller. This is how a B-tree stays balanced:

A node split pushes the middle key up

Before — insert 15 into a full node

101520

3 keys overflow a max of 2 — the node must split.

After — the middle key rises

1020

Splitting from the bottom up keeps every leaf at the same depth.

B+ trees

A B+ tree is the database favorite. It stores all actual records in the leaves (internal nodes hold only keys for routing), and links the leaves together in a list. So it does fast point lookups and efficient range scans — "every order between March and June" — by walking the linked leaves.

Feature	B-tree	B+ tree
`Data location`	Keys in all nodes	Only in the leaves
`Leaves linked?`	No	Yes — a linked list
`Range scans`	Awkward	Excellent (walk the leaves)
`Used by`	Some file systems	Most database indexes (MySQL, Postgres)

In code

Search walks keys within a node, then descends to the right child — the same idea as a BST, just multi-way:

Language

btree_search.py

def search(node, key):
    i = 0
    while i < len(node.keys) and key > node.keys[i]:
        i += 1                                  # find the right slot
    if i < len(node.keys) and node.keys[i] == key:
        return node                             # found in this node
    if node.is_leaf:
        return None                             # not found
    return search(node.children[i], key)        # descend one level

Recap & quick check

Key takeaways

B-trees pack many keys per node to stay short and wide — ideal for disk blocks.
Order-m node: up to m−1 keys and m children; all leaves at the same depth.
Insertion splits an overflowing node, pushing the middle key up; splits can cascade.
Height is O(log_m n) with a large branching factor m, so lookups need few disk reads.
B+ trees keep data in linked leaves — great for range scans; the basis of database indexes.

Quick check

1. Why do databases prefer B-trees over binary search trees?

2. When a B-tree node overflows on insertion, it:

3. In a B-tree, all leaves are:

4. What does a B+ tree add over a B-tree?

That completes the trees. Next we generalize to arbitrary connections — the most flexible structure of all. Next up: Module 23 — Graph Fundamentals & Representations.