Database Indexes

An index is a separate data structure that a database maintains alongside a table so it can find rows without scanning every single one. Without an index, looking up a row by a value means the database engine reads the entire table from start to end — a "full table scan" — checking every row against your condition. On a table with a few hundred rows this is instant; on a table with fifty million rows it can take minutes.

Most relational databases implement indexes using a B-tree (balanced tree) structure. A B-tree keeps indexed values in sorted order across a tree of pages, so the engine can jump directly to the relevant branch instead of reading everything, in roughly logarithmic time rather than linear time. Some databases also offer hash indexes, full-text indexes, or specialized indexes (like GIN/GiST in PostgreSQL for JSON or geometric data), but the B-tree is the default and most common case you will encounter.

Why it matters

A query that takes ten seconds on a large table can take ten milliseconds with the right index. An index is the first thing to check when a query is slow, and the most common fix. It is not free, though: every index slows down writes, so knowing where to add one, and where not to, is a core skill.

How a B-Tree Index Speeds Up Reads

Think of a B-tree index like the index at the back of a textbook: instead of reading every page to find "transactions", you look up "T" in the index and jump straight to the right pages. A database B-tree stores indexed column values in sorted order, with each node pointing to a range of child nodes. Searching for a value means comparing against a handful of nodes as you descend the tree, rather than comparing against every row. This is why an indexed lookup on a huge table can return in milliseconds while an unindexed lookup on the same table might take seconds or longer.

The Write-Side Cost

Indexes are not free. Every time you INSERT, UPDATE, or DELETE a row, the database must also update every index that covers the changed columns, to keep the index's sorted structure consistent with the table's actual data. A table with five indexes means every write potentially touches six data structures instead of one. This is why indexing is a trade-off, not something to apply blindly to every column.

• Reads become faster — the engine can locate matching rows without scanning the whole table.
• Writes become slower — every INSERT/UPDATE/DELETE must also maintain each affected index.
• Storage grows — an index is extra data stored on disk, separate from the table itself.

When to Add an Index

Add an index on columns that are frequently used in WHERE clauses, JOIN conditions, ORDER BY clauses, or as foreign keys — especially on large, read-heavy tables. Avoid indexing columns that are rarely queried, columns on small tables (a full scan of 200 rows is already fast), or columns on tables with very heavy write traffic where the index-maintenance cost would outweigh the read benefit. Primary keys are indexed automatically by virtually every database; the real decision is about secondary indexes on other columns.

Examples

-- A users table with 5 million rows, frequently filtered by email during login
CREATE INDEX idx_users_email ON users (email);

-- This query now uses the index instead of scanning all 5 million rows
SELECT id, name, email
FROM users
WHERE email = 'asha@example.com';

id: 348221 | name: Asha Verma | email: asha@example.com
(1 row returned in ~2ms using idx_users_email, versus ~800ms with a full table scan)

-- Orders are frequently queried by customer_id and then filtered by status
CREATE INDEX idx_orders_customer_status ON orders (customer_id, status);

SELECT id, total_amount
FROM orders
WHERE customer_id = 1029 AND status = 'PENDING';

id: 88213 | total_amount: 149.99
id: 88450 | total_amount: 39.50
(2 rows returned quickly via idx_orders_customer_status)

Exercise

Orders are looked up by customer constantly. Create an index named idx_orders_customer on customer_id, and a composite index named idx_orders_customer_status on customer_id and status. Then run the query the indexes are meant to serve: the ids of customer 1's paid orders, in order.

Expected output: id, 1, 3 (one per line)

CREATE TABLE orders (id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT);
INSERT INTO orders (id, customer_id, status) VALUES
  (1, 1, 'paid'),
  (2, 2, 'paid'),
  (3, 1, 'paid'),
  (4, 1, 'pending');

-- TODO: index on customer_id

-- TODO: composite index on customer_id and status

-- TODO: ids of customer 1's paid orders, ordered by id

CREATE TABLE orders (id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT);
INSERT INTO orders (id, customer_id, status) VALUES
  (1, 1, 'paid'),
  (2, 2, 'paid'),
  (3, 1, 'paid'),
  (4, 1, 'pending');

CREATE INDEX idx_orders_customer ON orders (customer_id);

CREATE INDEX idx_orders_customer_status ON orders (customer_id, status);

SELECT id
FROM orders
WHERE customer_id = 1 AND status = 'paid'
ORDER BY id;

Quick quiz

Interview questions