Indexes: how a B-tree makes lookups fast
An index is a separate, sorted copy of one or more columns, usually a B-tree, with pointers back to the rows. The database can then jump to the matching rows instead of scanning the whole table.
Why it matters
Without an index, WHERE order_date = '2024-02-12' must read every row and check it: a full table scan. On 100 million rows that is slow, and it gets slower as the table grows. An index turns it into a few quick steps.
The idea
A B-tree index keeps the column's values in sorted order, in a shallow tree. A root page points to branch pages, which point to leaf pages. The leaf pages hold each value and the row it belongs to. To find a value, the database walks from the root down — about 3 or 4 steps even for millions of rows — instead of reading everything.
The primary key is indexed automatically. Indexes speed up WHERE, JOIN … ON, ORDER BY and MIN/MAX on the indexed column.
The cost: every INSERT, UPDATE and DELETE must also update every index, and indexes take space.
The index at the back of a textbook. To find "photosynthesis" you don't read every page; you look it up alphabetically and jump to page 214. A full table scan is reading the book cover to cover.
A book index never changes once printed. A database index must be updated on every write — so a table with ten indexes is slow to write to. Index what you search by, not everything.
Syntax
CREATE INDEX index_name ON table_name (column);
CREATE UNIQUE INDEX index_name ON table_name (column);
DROP INDEX index_name;How it works
- Without an index on order_date, the plan says SCAN orders: every row is read.
- CREATE INDEX idx_orders_date ON orders(order_date) builds a sorted list of dates, each pointing to its row.
- Now the plan says SEARCH orders USING INDEX idx_orders_date (order_date=?): the database jumps to the date.
- A lookup by the primary key uses the table's own key: SEARCH … USING INTEGER PRIMARY KEY.
- For 10 rows the difference is invisible; for 100 million it is the difference between a full read and a handful of page reads.
Key points
- An index is a sorted structure (usually a B-tree) pointing back to the rows.
- It helps WHERE, JOIN … ON, ORDER BY and GROUP BY on the indexed columns.
- Primary keys and UNIQUE constraints get an index automatically; foreign keys usually don't — index them yourself.
- Every index slows down writes and uses space. Index the columns you filter and join on.
- An index helps most when it narrows the search to a small share of the rows (high selectivity).
- B-trees versus LSM trees, and indexing at scale: Database indexing in System Design.
Common mistakes
- Indexing every column "just in case", which slows every write.
- Forgetting to index foreign keys, so joins and deletes on the parent table are slow.
- Indexing a column with only a few values (like status) and expecting it to help a query that matches half the table.
Not true: Adding an index to every column makes the whole database faster.
In fact: Every index has to be updated on each INSERT, UPDATE and DELETE, so extra indexes slow writes down. Index only the columns your queries filter, join or sort on.
In the interview
An index is a separate sorted structure, typically a B-tree, mapping column values to row locations, so the database can find matching rows in logarithmic time instead of scanning the table. I index columns used in selective WHERE filters, in join keys (especially foreign keys) and in ORDER BY. I keep the trade-off in mind: every index adds work to inserts, updates and deletes, and uses storage.
Part of Unit 7: Performance: indexes and query plans in the free SQL course.