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

  1. Without an index on order_date, the plan says SCAN orders: every row is read.
  2. CREATE INDEX idx_orders_date ON orders(order_date) builds a sorted list of dates, each pointing to its row.
  3. Now the plan says SEARCH orders USING INDEX idx_orders_date (order_date=?): the database jumps to the date.
  4. A lookup by the primary key uses the table's own key: SEARCH … USING INTEGER PRIMARY KEY.
  5. 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

Common mistakes

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.