Loading...
Spaceplay← →stepRreset
See how database indexes speed up queries with an interactive visualization. Compare a full table scan against a B-tree lookup, watch the tree descend to a leaf, and see why writes get slower as indexes pile up.
Loading visualization...
A database index is a separate, sorted data structure that maps column values to the rows that hold them, so a query can jump to matching rows in a handful of page reads instead of scanning the whole table.
A table on disk is a heap: rows sit in pages in whatever order they were inserted. Finding every row where email equals a given value means reading every page and comparing every row, and that work grows in direct proportion to the table size. An index is a second structure, maintained alongside the table, that keeps the values of one or more columns in sorted order together with a pointer to each row.
Almost every relational database implements the default index as a B-tree. Internal pages hold separator keys and child pointers, leaf pages hold the actual keys with their row pointers (a page number and slot in PostgreSQL, a primary key value in InnoDB secondary indexes), and all leaves sit at the same depth. Because a single 8 KB page holds hundreds of keys, a tree that covers millions of rows is only three or four levels tall, so a lookup costs three or four page reads regardless of how many rows exist.
The query planner decides whether to use an index. It keeps statistics per column (number of distinct values, most common values, a histogram) and estimates how many rows a predicate will select. A highly selective predicate on an indexed column is served by an index scan. A predicate that matches a large fraction of the table is often cheaper as a sequential scan, since following thousands of row pointers into random heap pages costs more than reading the pages in order.
Indexes are not free. Every INSERT, every DELETE, and every UPDATE that touches an indexed column must also modify each affected index, and a full leaf page has to split, which writes two leaves and updates the parent. Indexes also take disk space and buffer pool memory. The engineering task is to create the few indexes that match the predicates and sort orders queries actually use, and to remove the ones that only slow writes down.
Interview framing: define Database Indexing in one sentence, then explain one concrete runtime behavior and one common pitfall with a short code example.
An index on (last_name, first_name) sorts by last_name first. A filter on first_name alone has no leading prefix to descend by, so the planner cannot use the index and scans the table, even though the column is in the index.
Fix: Order columns so that the ones used with equality in most queries come first, followed by the column used for a range or sort. Create a second index if two query shapes need different leading columns.
WHERE lower(email) = ... or WHERE date(created_at) = ... compares an expression, not the column the index stores. The planner cannot prove the expression preserves the index order, so the index is ignored.
Fix: Either rewrite the predicate to compare the raw column, or create an expression index on lower(email) so the stored keys match the predicate exactly.
Each index is another B-tree to update on every write. A table with ten indexes turns a single row insert into ten index inserts plus occasional page splits, and the extra pages compete for buffer pool memory with the data itself.
Fix: Add indexes only for predicates and sorts that appear in real query plans, check usage statistics such as pg_stat_user_indexes, and drop indexes that are never scanned.
A filter like status = 'active' that matches 90 percent of the rows would force the executor to follow a row pointer into a random heap page for nearly every row, which is slower than reading the heap in order. The planner correctly chooses a sequential scan and the index sits unused.
Fix: Index columns whose values narrow the result down, or use a partial index (WHERE status = 'pending') that only covers the small, frequently queried subset.
Common interview prompts with concise model answers.
Each internal page holds hundreds of separator keys, so every level divides the remaining search space by hundreds. A tree over a million rows is typically three or four levels tall, so a point lookup reads three or four index pages plus one heap page. A sequential scan on the same table reads every page, tens of thousands of them, and doubles when the table doubles.
An index on (a, b, c) can serve predicates on a, on a and b, or on a, b, and c, because the keys are sorted by a first. A predicate on b alone or on c alone cannot descend the tree, since matching values are scattered under every a. Equality on a combined with a range on b still works, but a range on a followed by equality on b only uses the index for a.
CREATE INDEX users_name_idx ON users (last_name, first_name);
-- uses the index (full key)
SELECT * FROM users WHERE last_name = 'Lovelace' AND first_name = 'Ada';
-- uses the index (leading prefix)
SELECT * FROM users WHERE last_name = 'Lovelace';
-- cannot use the index: no leading column
SELECT * FROM users WHERE first_name = 'Ada';A covering index contains every column the query reads, either as key columns or as INCLUDE columns. The executor can answer from the leaf entries and skip the heap fetch, as long as the visibility map shows the heap page has no rows that need a visibility check. This removes the random heap reads that make index scans expensive on wide result sets.
CREATE INDEX orders_customer_idx
ON orders (customer_id) INCLUDE (total, created_at);
-- every referenced column is in the index: Index Only Scan
SELECT total, created_at FROM orders WHERE customer_id = 42;The planner compares estimated costs, not just applicability. If the statistics say the predicate selects a large share of the table, the random heap fetches of an index scan cost more than a sequential read of the whole table. Stale statistics, a function around the column, or a type mismatch that forces a cast can also make the index unusable.
The leaf splits: roughly half its keys stay, the other half move to a newly allocated leaf, and the first key of the new leaf is copied into the parent as a separator. If the parent is also full it splits the same way, and a split of the root adds a new level. This keeps every leaf at the same depth, which is the balance property that guarantees the logarithmic lookup cost.
-- one row, three indexes: one heap write plus three B-tree inserts,
-- each of which may split a full leaf and update its parent
INSERT INTO users (id, email, last_name, first_name)
VALUES (13, 'donald@example.com', 'Knuth', 'Donald');Continue with these concepts to strengthen your mental model.
-- users: 12 rows stored in 3 heap pagesSELECT * FROM usersWHERE email = 'ada@example.com'; -- build a sorted B-tree over emailCREATE INDEX users_email_idx ON users (email); -- same query, now with a usable indexSELECT * FROM usersWHERE email = 'ada@example.com'; -- only the indexed column: no heap fetchSELECT email FROM usersWHERE email = 'ada@example.com';waiting
waiting
waiting
waiting