All Articles

SQL Indexes Explained: B-Trees, Composite Indexes, and Covering Indexes

Database Internals
#indexes#b-tree#composite-index#query-performance#sql-interview

What an Index Actually Is

An index is a separate, sorted data structure that lets the database find rows without scanning the entire table — the same idea as a book's index letting you jump to a page instead of reading cover to cover. Understanding how indexes work internally, not just when to add one, is what separates a candidate who can recite "add an index" from one who can reason about why it helps and when it won't.

The B-Tree: How Most Indexes Actually Work

The default index type in virtually every relational database is a B-tree (balanced tree). It stores indexed values in sorted order across a tree of nodes, with each node pointing to its children, and the leaf nodes ultimately pointing back to the actual row locations in the table.

  • Looking up a value means starting at the root and following pointers down the tree, narrowing the search range at each level — a lookup on a table with a million rows takes roughly 20 comparisons instead of up to a million (a full scan), because tree depth grows logarithmically, not linearly, with row count
  • B-trees also naturally support range queries (WHERE price BETWEEN 10 AND 50) and sorted output, since the leaf nodes are linked in sorted order — this is why B-tree is the default over a hash index for most columns
  • Hash indexes (available on some databases for specific use cases) are faster for exact-match equality lookups but cannot support range queries or sorting at all — they're a narrower tool, used far less often than B-tree

Single-Column Indexes

CREATE INDEX idx_orders_customer_id ON orders (customer_id);

-- Now this query can use the index to jump directly to matching rows
SELECT * FROM orders WHERE customer_id = 482;

Composite (Multi-Column) Indexes

A composite index covers multiple columns together, and column order is critical — a composite index is only usable from its leftmost column inward, the same way a phone book sorted by (last name, first name) is useless for searching by first name alone.

CREATE INDEX idx_orders_customer_status ON orders (customer_id, status);

-- Can use the index: filters on the leading column
SELECT * FROM orders WHERE customer_id = 482;

-- Can use the full index: filters on both columns, in order
SELECT * FROM orders WHERE customer_id = 482 AND status = 'shipped';

-- CANNOT use this index efficiently: skips the leading column
SELECT * FROM orders WHERE status = 'shipped';

Rule of thumb for column order: put the column used in equality filters (=) before columns used in range filters (>, BETWEEN), and generally put the most selective column (the one that narrows the result set the most) earlier — though the equality-before-range rule usually matters more in practice than raw selectivity.

Covering Indexes and Index-Only Scans

A covering index includes every column a query needs — not just the columns being filtered on, but also the columns being selected — so the database never has to go back to the actual table at all.

-- Include email in the index itself, even though it's not part of the WHERE filter
CREATE INDEX idx_users_status_covering ON users (status) INCLUDE (email);

SELECT email FROM users WHERE status = 'active';
-- Fully satisfied by the index alone — an "index-only scan," the fastest possible read

PostgreSQL uses INCLUDE for non-key columns in a covering index; MySQL and SQL Server achieve the same effect by simply adding the extra columns to the composite index definition itself. This is a strong lever for read-heavy, narrow queries that run extremely frequently.

Unique Indexes

A UNIQUE constraint (see our constraints guide) is implemented internally as a unique index — it enforces no-duplicates and speeds up lookups on that column simultaneously, at no extra cost beyond the index itself.

CREATE UNIQUE INDEX idx_users_email ON users (email);

Partial (Filtered) Indexes

Indexes only a subset of rows matching a condition — smaller, faster to maintain, and ideal when queries consistently filter on a specific slice of the data.

-- PostgreSQL: partial index
CREATE INDEX idx_orders_pending ON orders (created_at) WHERE status = 'pending';

-- SQL Server: filtered index, same idea
CREATE INDEX idx_orders_pending ON orders (created_at) WHERE status = 'pending';

If 95% of orders are eventually marked 'shipped' or 'delivered' and most operational queries only ever look at 'pending' orders, a partial index on just that slice is dramatically smaller — and therefore faster to scan and cheaper to maintain — than indexing the entire table.

The Write-Performance Tradeoff

Every index speeds up reads on the columns it covers but slows down every INSERT, UPDATE, and DELETE that touches the indexed columns, because the index structure itself must be updated too, in addition to the underlying table row.

  • A table with 10 indexes pays a real write-amplification cost on every insert — worth measuring on genuinely write-heavy tables
  • Periodically audit for unused indexes using system views (pg_stat_user_indexes in PostgreSQL, sys.dm_db_index_usage_stats in SQL Server) and drop them — an unused index is pure write overhead with zero benefit
  • Don't index columns with very low cardinality (e.g. a boolean flag with a 90/10 split) unless paired with a partial index targeting the smaller slice — a full index on a low-cardinality column often isn't selective enough for the optimizer to prefer it over a sequential scan anyway

Reading EXPLAIN to Confirm Index Usage

EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 482;

-- Look for:
-- "Index Scan using idx_orders_customer_id" — the index IS being used
-- "Seq Scan on orders" — the index is NOT being used (missing, or the planner decided it wasn't worth it)

An index existing doesn't guarantee it's used — the query planner may still choose a sequential scan if the table is small enough, or if the filter isn't selective enough to be worth the extra index lookup overhead. Always verify with EXPLAIN rather than assuming.

Common Mistakes

  • Indexing every column "just in case" — creates significant write overhead for indexes that are rarely or never actually used by real queries.
  • Wrong column order in a composite index — putting a range-filtered column before an equality-filtered one, or leading with a column that isn't used in the most common queries at all.
  • Wrapping an indexed column in a function in the WHERE clause (e.g. WHERE DATE(created_at) = '2024-01-15') — this makes the index on that column unusable; see the sargability discussion in our query optimization guide.
  • Assuming an index always helps — on a small table, or a low-selectivity filter, a sequential scan can genuinely be faster than an index lookup plus a round trip back to the table; the query planner usually gets this right, but it's worth understanding why.

Common Interview Questions

  1. How does a B-tree index make lookups faster? By storing values in sorted order across a balanced tree, turning an O(n) full scan into an O(log n) traversal.
  2. Why does column order matter in a composite index? A composite index can only be used from its leftmost column inward — a query that only filters on a trailing column can't use it efficiently, same as a phone book sorted by last name can't be searched by first name alone.
  3. What's a covering index, and why is it faster? An index that includes every column a query needs, so the database never has to fetch the underlying table row at all — an "index-only scan."
  4. Why shouldn't you index every column in a table? Every index adds write overhead to every insert/update/delete on that column, and an index that's never actually used by a real query is pure cost with no benefit.

Frequently Asked Questions

Do indexes get automatically created for foreign keys?

Not always — PostgreSQL does NOT automatically index foreign key columns (a common surprise), while MySQL's InnoDB engine does create one automatically. Always verify explicitly rather than assuming, since an unindexed foreign key column can make joins and cascading deletes painfully slow.

How many indexes is "too many" on one table?

There's no universal number — it depends entirely on the table's read/write ratio. A reporting table that's rarely written to can reasonably carry many indexes; a high-throughput transactional table should carry only the ones proven necessary by real query patterns.

Practice Index Design

Indexing decisions are where SQL knowledge becomes real database engineering judgment. Try it hands-on with our SQL practice questions, or work through a full performance-tuning scenario in our case studies. For the broader optimization techniques indexes support, see our complete query optimization guide.

Back to All Articles