Database Indexing: How a B-Tree Index Speeds Up Lookups

A returns desk scans the serial number on a dishwasher, and the screen sits there for a few seconds. The table behind it holds 100,000 serial numbers. The database did what it always does when it has no better idea: it read rows from the top, comparing each serial to the one scanned, until it found a match. On average that is about half the table per scan. This lesson builds the better idea from scratch, in about forty lines of Python, so you can count exactly how much work it saves.

Why reading every row is the real cost

A database does not read single rows from disk. It reads fixed-size pages (a few kilobytes each) and each page holds many rows. When people say a full scan is slow, they mean it touches every page of the table. Comparing values inside a page is cheap because the page is already in memory. Fetching another page is the expensive step, so the number of pages touched is the number worth watching.

An index is a second, smaller structure that stores the indexed column's values in sorted order, each one with a pointer back to its row. Sorted order is the whole trick: if you know the list is sorted, you never need to look at most of it.

Sorted is not enough: why a plain binary search is the wrong shape

Binary search on one big sorted array needs about 17 comparisons for 100,000 keys, which sounds perfect. The catch is that a database cannot keep a 100,000-entry array as one block it can jump around in. The entries live on pages, and every jump to a new page is a disk read. A search that hops across 17 distant pages is no good even though the comparison count is small.

A B-tree (almost always the B+tree variant in practice) fixes this by making each node exactly one page and filling it with hundreds of entries. The root page lists the first key of each child page. A child page either lists more children or, at the bottom, holds the actual keys with row pointers. Because every node is wide, the tree is very shallow, and a lookup reads one page per level.

root page      [ 10M | 18M | 26M | 35M | ... ]
                  |      |      |      |
leaf pages   [10M..18M) [18M..26M) [26M..35M) ...
              keys sorted inside each page, and the leaf
              pages are chained left to right for ranges

Build one and count

The script below makes 100,000 random serial numbers, stores them unsorted in 256-key pages (the table), and builds a two-level index over a sorted copy. It then looks up 200 serials both ways and reports comparisons and pages read. The page size of 256 is an arbitrary choice for the demo; real pages are measured in bytes, so the number of keys per page depends on how wide the key is.

import random

PAGE = 256  # keys that fit on one "disk page"

class Meter:
    def __init__(self):
        self.comparisons = 0
        self.pages = 0

def scan_lookup(pages, target, m):
    for page in pages:
        m.pages += 1
        for key in page:
            m.comparisons += 1
            if key == target:
                return True
    return False

def search(seq, target, m):
    """Binary search that counts its comparisons; returns insertion point."""
    lo, hi = 0, len(seq)
    while lo < hi:
        mid = (lo + hi) // 2
        m.comparisons += 1
        if seq[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

class TwoLevelIndex:
    def __init__(self, sorted_keys):
        self.leaves = [sorted_keys[i:i + PAGE] for i in range(0, len(sorted_keys), PAGE)]
        self.root = [leaf[0] for leaf in self.leaves]   # first key of every leaf

    def lookup(self, target, m):
        m.pages += 1                                    # read the root page
        leaf_no = max(search(self.root, target, m) - 1, 0)
        m.pages += 1                                    # read one leaf page
        leaf = self.leaves[leaf_no]
        pos = search(leaf, target, m) - 1
        return pos >= 0 and leaf[pos] == target

    def range(self, low, high, m):
        m.pages += 1
        leaf_no = max(search(self.root, low, m) - 1, 0)
        found = []
        while leaf_no < len(self.leaves):
            m.pages += 1
            for key in self.leaves[leaf_no]:
                if key > high:
                    return found
                if key >= low:
                    found.append(key)
            leaf_no += 1                                # leaves sit next to each other
        return found

random.seed(7)
serials = random.sample(range(10_000_000, 99_999_999), 100_000)
heap_pages = [serials[i:i + PAGE] for i in range(0, len(serials), PAGE)]   # unsorted table
index = TwoLevelIndex(sorted(serials))

probes = random.sample(serials, 200)
scan_m, idx_m = Meter(), Meter()
for p in probes:
    assert scan_lookup(heap_pages, p, scan_m)
    assert index.lookup(p, idx_m)

print(f"{'':12}{'comparisons':>12}{'pages read':>12}   (average per lookup, 200 lookups)")
print(f"{'full scan':12}{scan_m.comparisons/200:>12.1f}{scan_m.pages/200:>12.1f}")
print(f"{'two-level':12}{idx_m.comparisons/200:>12.1f}{idx_m.pages/200:>12.1f}")

rm = Meter()
hits = index.range(50_000_000, 50_100_000, rm)
print("range 50,000,000..50,100,000 ->", len(hits), "keys, pages read:", rm.pages)
assert hits == [k for k in sorted(serials) if 50_000_000 <= k <= 50_100_000]

             comparisons  pages read   (average per lookup, 200 lookups)
full scan        48851.8       191.3
two-level           16.7         2.0
range 50,000,000..50,100,000 -> 97 keys, pages read: 2

Read the two columns separately. Comparisons fell from roughly 48,000 to 17, which is the figure binary search would have given too. The pages read column is the one that matters on disk: 191 pages down to 2, one for the root and one leaf. The last line shows the second superpower. A range query finds the first key with one descent, then walks neighbouring leaf pages, so BETWEEN and ORDER BY on the indexed column are cheap too.

How deep does the tree get?

Two levels was enough for 100,000 keys because each page held 256 of them. Each extra level multiplies capacity by the page's fan-out, so depth grows with the logarithm of the table size. The helper below counts the page reads a lookup needs for two assumed fan-outs. These are assumptions for illustration: how many entries really fit on a page depends on the key size and the database.

def levels(n_rows, fanout):
    """How many page reads a lookup needs in a tree where every page holds `fanout` entries."""
    pages, count = 1, fanout
    while count < n_rows:
        pages += 1
        count *= fanout
    return pages

print(f"{'rows':>14} {'fanout 100':>11} {'fanout 400':>11}")
for n in (10_000, 1_000_000, 100_000_000, 10_000_000_000):
    print(f"{n:>14,} {levels(n, 100):>11} {levels(n, 400):>11}")

          rows  fanout 100  fanout 400
        10,000           2           2
     1,000,000           3           3
   100,000,000           4           4
10,000,000,000           5           4

A table a million times larger costs only two or three extra page reads (compare 10,000 rows with 10 billion in the output). That is why an indexed lookup feels flat as data grows while a full scan grows in direct proportion. Upper levels are touched by every query, so they tend to stay in memory, and the real disk cost is often just the leaf and the table row.

Staying sorted when rows arrive: page splits

The toy index is built once from sorted data. A live index has to accept inserts at arbitrary positions. When a leaf page is full and a new key belongs in it, the database splits the page into two half-full pages and adds a new separator key to the parent. If the parent is full it splits as well, and if the root splits the tree grows one level taller. All leaves therefore stay at the same depth, which is what balanced means, and a lookup never takes longer than the height of the tree.

This is also the first hint of the price of an index. Every insert, delete and update to an indexed column has to find the right leaf and maybe split it. The last lesson measures that cost, and SQL Fundamentals covers the queries these indexes serve.

Where an index does not help

• Tiny tables. If the whole table fits on a handful of pages, scanning it costs about the same as using the index, and planners know it.
• Low-selectivity columns. An index on a yes/no column returns half the table per lookup, and reading half the table through an index is slower than scanning it.
• Queries that cannot use sort order. A filter such as WHERE email LIKE '%@example.test' has no usable starting point in a sorted list.
• Columns you never filter, join or sort on. The index would cost writes and give nothing back.

Common mistakes

• Indexing every column just in case. Symptom: inserts that took milliseconds now take noticeably longer and the database file balloons, while no read query got faster.
• Assuming the primary key covers everything. Symptom: a query by email or serial_no shows a full scan (Seq Scan in PostgreSQL, type: ALL in MySQL, SCAN in SQLite) even though id is indexed.
• Expecting an index on a boolean or status flag to help. Symptom: the index exists, yet the plan ignores it, because the planner correctly estimates it would read most of the table anyway.
• Judging speed on ten sample rows. Symptom: everything looks instant in development and the same query times out against production-sized data.

How this shows up in projects and interviews

In a real team, adding an index is the most common fix for a slow endpoint, and the useful skill is knowing which one and proving it helped. Interviewers like to ask why databases use B-trees instead of hash tables or binary trees. A solid answer has three parts: pages make wide shallow trees efficient on disk, sorted leaves support ranges and ordering, and balanced splitting keeps every lookup at the same depth. A hash index answers equality only. Be ready to say what you would measure, namely pages read or the plan, rather than guessing.