Indexes and B-trees

Your application finds a customer by email in 2 milliseconds today. Two years and fifty million rows later, the same page takes four seconds and the database’s CPU is pinned. Nothing in the code changed. What changed is the size of the table — and the missing ingredient is almost always an index.

The problem: scanning everything

Tables are stored on disk in pages, typically 8 or 16 KB each, holding many rows. Without any other structure, the only way to find rows where email = 'asha@example.com' is a full table scan: read every page and check every row. The work grows in proportion to the table. A few thousand rows is instant; fifty million is not.

An index is like the index at the back of a book: a separate, sorted structure that tells you exactly where to look.

The B+ tree

Nearly every relational database uses the B+ tree as its default index. It keeps keys sorted in a tree that is very wide and very shallow:

• The root and internal nodes hold keys that act as signposts: “smaller than 40 → go left”.
• The leaves hold every key in sorted order, each pointing to its row (or containing it).
• Leaves are linked to their neighbours, so after finding a starting point you can walk along them in order.

Search for an ID below, then try a range query:

Every lookup reads exactly one page per level. And because real nodes hold hundreds of keys, the tree stays tiny in height: with about 500 keys per node, three levels reach well over a hundred million rows, and four levels tens of billions. The root and upper levels are usually cached in memory, so a lookup often costs just one or two disk reads.

Creating and choosing indexes

CREATE INDEX idx_customers_email ON customers (email);
CREATE INDEX idx_orders_customer_created ON orders (customer_id, created_at);

Primary keys and unique constraints get indexes automatically. Beyond those, index for the queries you actually run:

• Columns used in frequent WHERE filters and JOIN conditions — foreign keys especially.
• Multi-column indexes serve queries that filter on the leading column(s). An index on (customer_id, created_at) answers “this customer’s orders, newest first” directly from the index, already sorted.
• Columns used in ORDER BY with LIMIT, so the database can read the first rows in order and stop.

Indexes are not free

Every index must be updated on every insert, update and delete of the indexed columns, and it takes disk space and memory. Don’t take that on trust — measure it. The widget below builds real SQLite databases in your browser with zero to three indexes and times the same inserts into each:

A table with fifteen indexes may read fast and write painfully slowly. Also note that an index usually can’t be used when the query wraps the column in a function — WHERE LOWER(email) = … needs an index on LOWER(email) instead.

Check with EXPLAIN

Don’t guess — ask the database how it plans to run a query:

EXPLAIN ANALYZE
SELECT id, name FROM customers WHERE email = 'asha@example.com';

The plan shows whether it uses an index scan or a sequential scan, how many rows it expected versus found, and where the time goes. Reading plans is a core skill, covered properly in module 2.

SQLite has the same idea under a different name, EXPLAIN QUERY PLAN: SCAN means reading the whole table, SEARCH … USING INDEX means an index lookup. Work through the steps below on a real 100,000-row table in your browser, watching both the plan and the time:

Fast reads are only half the story. Next: how databases keep data correct when things go wrong mid-change — transactions.