Indexing and B-Trees

Without an index, finding a row means a sequential scan: read every row, check whether it matches. That's O(n) — completely fine for a table of a hundred rows, ruinous for one of a hundred million. An index is a separate, sorted structure the database maintains alongside the table, so a lookup can go straight to the matching rows instead of reading everything.

Why not a balanced binary search tree?

A red-black tree (see Red-Black Tree) gives O(log n) search in memory — so why doesn't a database just use one? Because an index doesn't live in memory, it lives on disk, and disk I/O is read in fixed-size blocks (a "page," typically 4–16 KB), each read costing real latency regardless of how little of it you actually needed. A binary tree's nodes are small and scattered — each level down is a separate pointer chase, very possibly a separate disk page, and a tree with a million entries is roughly 20 levels deep. Twenty disk reads per lookup is slow.

A B-tree fixes this by making each node hold many keys — as many as fit in one disk page, often hundreds — not just one. That collapses the tree's height dramatically: the same million entries fit in 3–4 levels instead of 20, because branching by hundreds instead of by two shrinks log n by the same factor. Fewer levels means fewer disk reads means faster lookups. This is the whole reason B-trees exist: they're a search tree shaped around the cost model of disk, not the cost model of memory.

A small illustration — a node holding two keys branches three ways, not two:

Read it the way you'd read a binary search tree, just with more than one key per box: everything under the left child of 10 | 20 is less than 10, everything under the middle child is between 10 and 20, everything under the right child is greater than 20 — and the same rule applies one level down inside each child. A real node holds not two keys but as many as fit in a disk page, so a single node here stands in for what would be several binary-tree levels.

Most production databases actually use a B+tree variant of this shape: all the data lives in the leaf nodes, and the leaves are linked together in a chain. Internal nodes (like the three above) hold only keys, used purely to navigate — which packs even more keys per page — and the leaf chain makes a range scan ("everything between these two values") a fast linear walk once you've found the start, instead of a tree traversal for every single row.

Why not a hash table?

A hash index is O(1) for an exact match — WHERE id = 42 — and genuinely faster than a B-tree for that one case. What it can't do at all is a range query: WHERE created_at > '2026-01-01', or ORDER BY price, or "the next row after this one." A hash function scatters keys deliberately — that's the whole point of a good hash — so nearby keys land nowhere near each other in the table. A B-tree keeps keys in sorted order by construction, so a range is just "keep walking the leaf chain until the condition stops holding." Most query workloads need range queries and sorted output somewhere, which is why B-trees are the default and hash indexes are the specialised choice, not the other way around.

When an index doesn't get used

Creating an index doesn't guarantee the database uses it. The common ways a query quietly falls back to a full scan:

• A function wrapped around the indexed column. WHERE LOWER(email) = 'x' can't use a plain index on email — the index stores the original values, not their lowercased form. (A function-based / expression index fixes this specifically, by indexing the function's output.)
• A leading wildcard. WHERE name LIKE '%smith' can't use a standard B-tree index — sorted order lets you jump to "everything starting with 'smith'" but gives you no way to jump to "everything ending with 'smith'". LIKE 'smith%' (no leading wildcard) can.
• Low selectivity. An index on a boolean column, or any column where one value covers most of the table, often gets ignored even when it exists — a scan touching 80% of the table's pages anyway isn't worth the extra hop through the index.
• Wrong column order in a composite index. An index on (country, city) serves a query filtering on country alone, or on country and city together — but not one filtering on city alone, for the same reason a phone book sorted by (last name, first name) doesn't help you find everyone named "Alex": the leading column has to be constrained for the sort order to narrow anything down.

Real-world use

• Postgres and MySQL's InnoDB both default to B+tree indexes; both also offer hash indexes explicitly for the exact-match-only case, and Postgres additionally offers GiST/GIN indexes for full-text search and array/JSON containment — different data shapes need different structures, and "which index type fits this query pattern" is itself a real system-design question once a schema is large enough to matter.
• EXPLAIN (or EXPLAIN ANALYZE) is how you actually check whether a query used an index or fell back to a sequential scan — reading one is the practical skill this article's second section is theory for.
• A composite index's column order is a genuinely common code-review comment on a schema migration: get it backwards and the index exists, costs write overhead on every insert, and never actually serves the query it was added for.

Practice it

The SQL track here judges the result set, not the query plan — a correct-but-unindexed query still passes every case, because the fixture is small enough that it doesn't need to matter. The reasoning above is what shows up when the same question gets asked about a real, large table instead.

Practice the SQL track