Databases

Understanding Database Indexes by Building a Tiny B-Tree

Build a small B+ tree in Python to understand indexed lookups, leaf splits, range scans, and composite indexes from the inside out.

·
8 min read
·
AI-assisted

AI tooling disclosure

Generative AI materially contributed to this article.

Human review confirmed by the author.

Understanding Database Indexes by Building a Tiny B-Tree

An index is not magic. It is a sorted data structure that the database keeps up to date for you. In this post we build one from scratch in about 80 lines of Python, test it, and then watch a real database (SQLite) behave exactly the way our toy does.

Everything here uses only the Python standard library and was run on Python 3.13.

The problem: scanning

Take a users table with 500,000 rows and ask for one user by email. With no index, the database has no choice but to read every row until it finds a match. SQLite's query plan calls this a SCAN.

I measured it (SQLite 3.53.1, in-memory, 500k rows, average of 20 lookups):

Query plan

Time per lookup

No index

SCAN users

~22.6 ms

Index on email

SEARCH users USING INDEX idx_email (email=?)

~0.002 ms

That is roughly a 10,000x difference, and the gap grows with the table. Timings depend on your machine, so treat the ratio, not the absolute numbers, as the point.

Why a tree?

We need a sorted structure so we can jump to a key instead of walking to it. A sorted array supports binary search, but inserting into the middle means shifting everything after it. A binary tree fixes inserts, but it is deep, and on disk every level costs a page read.

A B-tree fixes both by making nodes wide. Each node holds many keys (in a real database, one disk page's worth, often hundreds), so the tree stays very shallow.

We will build the most common database flavor, the B+tree:

  • Internal nodes hold only separator keys and child pointers. They are signposts.

  • Leaf nodes hold the actual keys and values (in a database, a pointer to the row).

  • Leaves are linked left to right, so a range scan walks along them without going back up the tree.

  • All leaves are at the same depth. The tree only grows taller when the root splits.

  • When a node holds more than max_keys keys, it splits in half and hands a separator key up to its parent.

Real databases use variants of this design, but the mechanics are the same.

The implementation

from bisect import bisect_left, bisect_right


class Node:
    def __init__(self, leaf):
        self.leaf = leaf
        self.keys = []
        self.children = []  # internal nodes: len(keys) + 1 children
        self.values = []    # leaf nodes: parallel to keys
        self.next = None    # leaf nodes: right sibling, for range scans


class BPlusTree:
    def __init__(self, max_keys=4):
        assert max_keys >= 3, "need at least 3 keys per node"
        self.max_keys = max_keys
        self.root = Node(leaf=True)
        self.height = 1  # nodes visited by every lookup

    def _find_leaf(self, key):
        node = self.root
        while not node.leaf:
            node = node.children[bisect_right(node.keys, key)]
        return node

    def get(self, key, default=None):
        leaf = self._find_leaf(key)
        i = bisect_left(leaf.keys, key)
        if i < len(leaf.keys) and leaf.keys[i] == key:
            return leaf.values[i]
        return default

    def range(self, lo, hi):
        """Yield (key, value) for lo <= key <= hi, in key order."""
        leaf = self._find_leaf(lo)
        while leaf:
            for k, v in zip(leaf.keys, leaf.values):
                if k > hi:
                    return
                if k >= lo:
                    yield k, v
            leaf = leaf.next

    def insert(self, key, value):
        split = self._insert(self.root, key, value)
        if split:  # the root itself split: the tree grows one level
            sep, right = split
            new_root = Node(leaf=False)
            new_root.keys = [sep]
            new_root.children = [self.root, right]
            self.root = new_root
            self.height += 1

    def _insert(self, node, key, value):
        if node.leaf:
            i = bisect_left(node.keys, key)
            if i < len(node.keys) and node.keys[i] == key:
                node.values[i] = value  # key exists: overwrite
                return None
            node.keys.insert(i, key)
            node.values.insert(i, value)
            return self._split_leaf(node) if len(node.keys) > self.max_keys else None

        i = bisect_right(node.keys, key)
        split = self._insert(node.children[i], key, value)
        if split is None:
            return None
        sep, right = split
        node.keys.insert(i, sep)
        node.children.insert(i + 1, right)
        return self._split_internal(node) if len(node.keys) > self.max_keys else None

    def _split_leaf(self, node):
        mid = len(node.keys) // 2
        right = Node(leaf=True)
        right.keys, node.keys = node.keys[mid:], node.keys[:mid]
        right.values, node.values = node.values[mid:], node.values[:mid]
        right.next, node.next = node.next, right
        return right.keys[0], right  # separator is copied up; it stays in the leaf

    def _split_internal(self, node):
        mid = len(node.keys) // 2
        sep = node.keys[mid]
        right = Node(leaf=False)
        right.keys, node.keys = node.keys[mid + 1:], node.keys[:mid]
        right.children, node.children = node.children[mid + 1:], node.children[:mid + 1]
        return sep, right  # separator is pushed up; it leaves this level

Four ideas carry the whole thing:

  1. Lookup (_find_leaf) walks from the root, using binary search at each node to pick the child, until it reaches a leaf. Every lookup visits exactly height nodes.

  2. Leaf splits copy the separator up. The first key of the new right leaf is also kept in that leaf, because leaves must hold every key.

  3. Internal splits push the separator up. The middle key moves to the parent and leaves this level, because internal keys are only signposts.

  4. Range scans find the leaf containing lo, then follow the next pointers. No walking back up the tree is needed.

Here it is on a small example, with a helper that prints the tree's shape:

from btree import BPlusTree

def show(node, depth=0):
    print("  " * depth + ("leaf " if node.leaf else "node ") + str(node.keys))
    for child in node.children:
        show(child, depth + 1)

t = BPlusTree(max_keys=4)
for k in [10, 20, 5, 6, 12, 30, 7, 17]:
    t.insert(k, f"row-{k}")

show(t.root)
print(t.get(12))
print(list(t.range(6, 17)))

Output:

node [10, 17]
  leaf [5, 6, 7]
  leaf [10, 12]
  leaf [17, 20, 30]
row-12
[(6, 'row-6'), (7, 'row-7'), (10, 'row-10'), (12, 'row-12'), (17, 'row-17')]

Drawn as a tree (dotted arrows are the next links between leaves):

flowchart TD
    R["10 | 17"]
    L1["5 6 7"]
    L2["10 12"]
    L3["17 20 30"]
    R --> L1
    R --> L2
    R --> L3
    L1 -.->|next| L2
    L2 -.->|next| L3

Eight keys did not fit in one leaf, so leaves split and the root became an internal node holding the signposts 10 and 17. Looking up 12 means: compare against the root's keys, go to the middle leaf, find it there.

The last insert, 17, is a leaf split in action. The leaf [10, 12, 20, 30] became [10, 12, 17, 20, 30], which is one key over max_keys=4. It splits in half, and the first key of the new right leaf (17) is copied up into the parent:

flowchart LR
    subgraph before["Before: insert 17 overflows a leaf"]
        direction TB
        B0["10"] --> B1["5 6 7"]
        B0 --> B2["10 12 17 20 30<br/>5 keys, max is 4"]
    end
    subgraph after["After: split, 17 copied up"]
        direction TB
        A0["10 | 17"] --> A1["5 6 7"]
        A0 --> A2["10 12"]
        A0 --> A3["17 20 30"]
    end
    before --> after

Does it actually work?

A data structure like this fails quietly: a bad split still returns plausible answers for a while. So the tests check three different things:

  • Against an oracle. After thousands of random inserts (with deliberate overwrites), every get must match a plain Python dict, across several node sizes from 3 to 100.

  • Against the structure's own rules. After inserts, a checker walks the whole tree and asserts that keys are sorted, no node is overfull, non-root nodes are at least half full, every key sits within its parent's bounds, all leaves are at the same depth, and the leaf chain contains exactly the sorted keys.

  • On nasty input. Sorted and reverse-sorted inserts (the classic worst case for naive trees), empty and single-element trees, string keys, and 500 random range queries compared against a brute-force filter.

The full test file is in the appendix. Running it:

$ python3 test_btree.py
ok   test_empty_and_single
ok   test_matches_dict_oracle
ok   test_range_queries
ok   test_sorted_and_reverse_inserts
ok   test_string_keys
5 tests passed

How deep does it get?

With 100 keys per node, I inserted keys in random order and recorded the tree's height:

Keys

Height

1,000

2

10,000

3

100,000

3

1,000,000

4

A million keys, four node visits. Height grows with the logarithm of the table size, and with wide nodes the base of that logarithm is large. The same arithmetic puts a billion keys at about five levels, which is why indexed lookups on huge tables still take a handful of page reads, and why the top levels of a busy index usually stay cached in memory.

The same thing in a real database

Our toy and SQLite agree. Using the 500k-row table from the start, I created a composite index on (country, created_at) and asked SQLite how it would run three queries:

country AND created_at > ?   ->  SEARCH users USING INDEX idx_country_created (country=? AND created_at>?)
country only                 ->  SEARCH users USING INDEX idx_country_created (country=?)
created_at only              ->  SCAN users

The tree is sorted by country first, then by created_at within each country. Here is the leaf level, simplified to three countries:

flowchart LR
    D["DE<br/>oldest to newest"] --> I["IN<br/>oldest to newest"] --> U["US<br/>oldest to newest"]

A query on country jumps straight to one block. A query on created_at alone would have to look inside every block. That has direct consequences, and you can see each one in the toy:

  • Leftmost-prefix rule. Filtering on country can descend the tree. Filtering on created_at alone cannot, because matching rows are scattered across every country's section. Hence the SCAN.

  • Range conditions are cheap. created_at > ? within one country is a descent plus a walk along linked leaves, exactly our range().

  • Leading wildcards defeat the index. For email LIKE '%[email protected]' SQLite also reported SCAN users, even with idx_email present. A suffix match gives the tree nothing to compare against at the top.

  • Order comes free. Leaves are already sorted, so ORDER BY on the indexed column needs no separate sort.

The cost side

Reads get faster; writes get more work. Every insert has to find its leaf and may trigger splits that cascade up the tree, and each additional index on a table is another tree to update. Index the columns you actually query by, not every column.

What this toy leaves out

This is a teaching implementation, so be clear about its limits:

  • No deletion. Real trees merge or borrow between underfull nodes. We only insert.

  • Unique keys only. Inserting an existing key overwrites it, like a unique index. Non-unique indexes need duplicate handling.

  • In memory. Real nodes are fixed-size disk pages, read through a buffer cache.

  • Single-threaded. Real engines use fine-grained latching so many readers and writers share a tree.

  • No crash safety. Real engines log changes (a write-ahead log) so a half-finished split can be recovered.

Each of those is a good follow-up post on its own.

Appendix: the full test suite

import random
from btree import BPlusTree


def check_invariants(tree):
    """Raise AssertionError if the tree breaks any B+tree rule."""
    leaf_depths = set()
    min_fill = tree.max_keys // 2

    def walk(node, depth, lo, hi):
        assert node.keys == sorted(node.keys), "keys out of order"
        assert len(node.keys) <= tree.max_keys, "node overfull"
        if node is not tree.root:
            assert len(node.keys) >= min_fill, "node underfull"
        for k in node.keys:  # every key must sit inside its parent's bounds
            assert (lo is None or k >= lo) and (hi is None or k < hi)
        if node.leaf:
            leaf_depths.add(depth)
            assert len(node.keys) == len(node.values)
            return
        assert len(node.children) == len(node.keys) + 1
        bounds = [lo] + node.keys + [hi]
        for i, child in enumerate(node.children):
            walk(child, depth + 1, bounds[i], bounds[i + 1])

    walk(tree.root, 1, None, None)
    assert leaf_depths == {tree.height}, "leaves at different depths"


def leaf_chain_keys(tree):
    node = tree.root
    while not node.leaf:
        node = node.children[0]
    keys = []
    while node:
        keys.extend(node.keys)
        node = node.next
    return keys


def test_matches_dict_oracle():
    for max_keys in (3, 4, 5, 16, 100):
        rng = random.Random(max_keys)
        tree, oracle = BPlusTree(max_keys), {}
        for _ in range(5000):
            k = rng.randrange(2000)  # small key space forces overwrites
            tree.insert(k, k * 10)
            oracle[k] = k * 10
        check_invariants(tree)
        assert leaf_chain_keys(tree) == sorted(oracle)
        for k in range(-5, 2005):
            assert tree.get(k) == oracle.get(k)


def test_range_queries():
    rng = random.Random(1)
    tree, oracle = BPlusTree(4), {}
    for _ in range(3000):
        k = rng.randrange(10_000)
        tree.insert(k, str(k))
        oracle[k] = str(k)
    for _ in range(500):
        lo, hi = sorted((rng.randrange(-100, 10_100), rng.randrange(-100, 10_100)))
        expected = [(k, oracle[k]) for k in sorted(oracle) if lo <= k <= hi]
        assert list(tree.range(lo, hi)) == expected
    assert list(tree.range(20_000, 30_000)) == []  # empty range past the end


def test_sorted_and_reverse_inserts():
    for keys in (range(1000), reversed(range(1000))):
        tree = BPlusTree(4)
        for k in keys:
            tree.insert(k, k)
        check_invariants(tree)
        assert leaf_chain_keys(tree) == list(range(1000))


def test_empty_and_single():
    tree = BPlusTree(4)
    assert tree.get(1) is None and tree.get(1, "x") == "x"
    assert list(tree.range(0, 10)) == []
    tree.insert(1, "a")
    assert tree.get(1) == "a" and tree.height == 1


def test_string_keys():
    tree = BPlusTree(4)
    words = "the quick brown fox jumps over the lazy dog".split()
    for w in words:
        tree.insert(w, len(w))
    check_invariants(tree)
    assert list(tree.range("a", "g")) == [("brown", 5), ("dog", 3), ("fox", 3)]


if __name__ == "__main__":
    tests = [v for k, v in sorted(globals().items()) if k.startswith("test_")]
    for t in tests:
        t()
        print("ok  ", t.__name__)
    print(f"{len(tests)} tests passed")

Comments(0)

Join the discussion by logging into your account.

No comments yet. Be the first to comment!

Emma Clements

Passionate developer sharing knowledge about modern web technologies and best practices.

Subscribe to Emma Clements's Newsletter

Direct email dispatches when new stories are published. Zero algorithms.