Database indexes
A structure, most often a sorted B-tree, that the database searches instead of reading the whole table, paid for with extra work on each write. A strong design names the columns it indexes and what they cost.
What it is
An index is a structure the database maintains for a table so that it can find the rows matching a condition without reading the table from top to bottom. Without one, a query for a single id means a scan of the whole table, row by row. With an index on that column, the database walks a few levels of a search tree and lands on the matching entries, which in most layouts hold a pointer or key that leads on to the row. Once the index exists the database maintains it as rows change, and the query planner decides per query whether using it beats a sequential scan, a decision that rests on the table statistics it keeps, so those statistics need to stay current.
Kinds of index. The default in PostgreSQL 17 is the B-tree, and most MySQL 8.4 index types are stored as B-trees too. A B-tree handles <, <=, =, >= and > on any data that sorts, which is why it also serves range queries and ORDER BY. A hash index stores a 32-bit hash of the value and serves the = operator and nothing else. GIN is an inverted index for values made of many parts, such as arrays (see Inverted indexes). BRIN stores a summary per range of physical blocks and works best when a column's values follow the physical order of the rows, which a timestamp column written in arrival order often does.
| Shape | What it does | Where it bites |
|---|---|---|
Single column | A B-tree over one column; each entry holds the key and what is needed to reach the row | Each write that touches the column updates it |
Multicolumn (a, b) | Sorted by a, then b within equal a; equality on leading columns plus one inequality narrows the scan | Weak for queries that constrain b without a |
Unique | Rejects a second row with an equal key; a primary key or unique constraint creates one for you | B-tree is the one type that can be unique; nulls count as distinct unless you say otherwise |
Partial | Built over the rows that satisfy a predicate | The planner must see that the query's condition implies the predicate; beyond simple cases it needs a literal match |
Covering (INCLUDE) | Carries extra payload columns so a query can be answered from the index without touching the table | Duplicates data; the gain is largest when the table changes slowly |
Where the row lives. In MySQL 8.4's InnoDB, the primary key is the clustered index: the row data sits in its leaf pages, so a primary-key lookup lands on the page holding the row. A secondary index entry carries the indexed columns plus the primary key, and a lookup through it finds the primary key first, then searches the clustered index for the row; a long primary key therefore makes each secondary index larger. In PostgreSQL 17 an index entry points at a heap row, and the database may skip the heap visit when the query references nothing but index columns and the page is marked all-visible; tables with a large share of unchanging rows get the most from this.
What it costs. Each insert, update and delete has to update each index on the table, and unneeded indexes waste space as well as planning time while the optimizer weighs them. Building an index on a big table takes a while, and in PostgreSQL 17 the default build blocks writes until it finishes; a concurrent build avoids that with caveats of its own.
When to use it
Index the columns your hottest queries filter on, join on or sort by. A join condition on an indexed column can speed the join, and a sort on the leftmost prefix of an index can read the index in order instead of sorting. For a multicolumn B-tree, put the columns with equality conditions first and the range column after them, since equality on the leading columns plus one inequality on the next column is what narrows the scan; a three-column index on (c1, c2, c3) serves lookups on c1, on c1 and c2, and on all three.
Use a unique index when the design relies on one row per key, for example a short code that maps to a long URL. The same index serves the point lookup and the constraint: when a second row with an equal key arrives, the insert fails, and when the first inserter hasn't committed yet the second waits to see whether that transaction commits or rolls back before the check is decided. The application then catches the failure and retries with a fresh key, which pairs with how you generate the key in the first place (see Unique ID generation).
Reach for a partial index when a small subset of rows takes most of the reads, such as unbilled orders among millions of billed ones: the index holds entries for just the matching rows, so it is smaller, and updates to rows outside the predicate skip it. Reach for a covering index when one frequent query needs a few columns beyond the search key from a table that changes slowly, so the lookup can be answered from the index without the table.
When not to
Leave a column unindexed when the table is small or when the typical query reads most of its rows: reading the table sequentially is then faster than hopping through an index, and the planner tends to ignore the index anyway. The same holds for a value that matches more than a few percent of the rows; an index on a low-cardinality status column mostly pays its write cost for nothing, unless you narrow it to the rare value with a partial index.
Be sparing on write-heavy tables such as event or log ingestion, since each index adds to the cost of each insert; if the main read is a time range over data written in order, a BRIN index, which stores a summary per range of blocks rather than an entry per row, is a lighter fit. Avoid a hash index when you need ranges or sorted output, since it serves = and nothing else. Skip a partial index when the predicate value arrives as a query parameter: a prepared x < ? does not match a predicate x < 2 at planning time, so the index goes unused. And keep wide payload columns out of INCLUDE lists, which bloat the index and can make an insert fail when an entry exceeds the index's size limit.
Compared
| Index | Fits | Pick the plainer option when | Cost |
|---|---|---|---|
Single-column B-tree | Equality, ranges and ordering on one column | The table is small or the query returns most rows: a sequential scan wins | One more structure to maintain per write |
Multicolumn B-tree (a, b) | Queries that pin a, or a and b together | Queries mix a, b and both: two single indexes combined through bitmaps serve all three | Larger entries; weak for lookups on b without a |
Unique | One row per key plus point lookups | Duplicates are legitimate: a plain index skips the check | A concurrent insert of the same key waits on the first transaction |
Partial | A small, hot subset of rows | The predicate is a parameter or the hot subset shifts over time: a full index needs no rebuild | Usable when the query's condition matches the predicate; may need recreating if the hot subset moves |
Covering (INCLUDE) | A frequent query needing a few extra columns from a slow-changing table | The table changes often: fewer pages stay all-visible, so more lookups touch the heap anyway and the payload earns little | Duplicated data; a bigger index; an oversized entry fails the insert |
Hash | Pure equality lookups | You need | No ranges, no ordering |
BRIN | Huge tables whose values track physical order | Values are scattered across the table: a B-tree finds rows precisely | Coarse; points at block ranges rather than rows |
In a picture
How to say it in an interview
The common mistake
Quiz
Questions that use this
Related
Sources
- PostgreSQL 17 documentation: 11.1. Introduction (Indexes)
- PostgreSQL 17 documentation: 11.2. Index Types
- PostgreSQL 17 documentation: 11.3. Multicolumn Indexes
- PostgreSQL 17 documentation: 11.5. Combining Multiple Indexes
- PostgreSQL 17 documentation: 11.6. Unique Indexes
- PostgreSQL 17 documentation: 11.8. Partial Indexes
- PostgreSQL 17 documentation: 11.9. Index-Only Scans and Covering Indexes
- PostgreSQL 17 documentation: 62.5. Index Uniqueness Checks
- MySQL 8.4 Reference Manual: 17.6.2.1 Clustered and Secondary Indexes
- MySQL 8.4 Reference Manual: 10.3 Optimization and Indexes
- MySQL 8.4 Reference Manual: 10.3.1 How MySQL Uses Indexes