Database Indexes

How an index lets a database find rows without reading the whole table: B-trees, composite and covering indexes, hash, partial and expression indexes, what every index costs on writes, and when not to add one.

Overview

An index is a second copy of some of a table's data, kept in an order that makes it fast to search, with a pointer from each entry back to its row. Without one, a query that looks for the orders of one customer has to read every row of the table and throw away the ones that do not match. With one, the database reads a few pages of the index and then only the rows it needs.

Indexes are the most common fix for a slow query, and the most common cause of a slow write. Every index has to be updated when rows are inserted, changed or deleted, it takes disk space and memory, and the planner may decide not to use it. Knowing which index a query needs, and what it costs, is a core skill for backend and system design interviews.

This chapter uses PostgreSQL, whose documentation is the main source here, and one running example: a table of one million orders. Every SQL block runs, in order, on PostgreSQL 17, and the plans described are the ones PostgreSQL 17 chose for that table with default settings. MySQL's InnoDB and log-structured stores such as RocksDB and Cassandra come in where they differ.

What you will be able to do

  • Explain how a B-tree finds one row, and how it reads a range, in a few page reads.
  • Choose the column order of a composite index from the queries it must serve.
  • Use covering, partial, expression and hash indexes where each one fits, and say why.
  • Predict when the planner will skip an index, and read the plan to check.
  • Weigh the write cost of an index, and know when not to add one.

Key concepts

  • B-tree and B+tree
  • Range scans
  • Composite indexes
  • Leftmost prefix
  • Covering indexes
  • Index-only scans
  • Selectivity
  • Partial and expression indexes
  • Write cost and HOT
  • LSM trees

Interview questions

  • How does a B-tree index find a row, and why do databases use B-trees rather than binary trees or hash tables?
  • Given an index on (a, b, c), which queries can use it?
  • How would you index WHERE user_id = ? AND created_at > ? ORDER BY created_at DESC LIMIT 20?
  • What is a covering index, and why might an index-only scan still read the table?
  • Why would the database ignore an index you just created?
  • How do indexes slow down writes in PostgreSQL, and what is a HOT update?
  • How do you add an index to a large production table without downtime?
  • When would you use a partial index, and when an expression index?
  • A service ingests 200,000 events a second and rarely reads them. B-tree or LSM storage?
  • Why is a hash index rarely the right choice in PostgreSQL?

Sign up free to read the full topic

More System Design topics

Start free on Cariara · Coding problems · System design studio