LUNAROPS · OPERATIONAL UPLINK 100% UPTIME 1,247d POSTS 893 JEFF.MOON@LUNAROPS.DEV UTC --:--:--

Database Indexes Explained

21 min read Data & Databases
databasespostgresqlindexesb-treequery-plannerperformanceginbrin
Contents

An index is not free storage that makes things faster. It is a second, redundant copy of part of your data, kept permanently in sync with the table, and that synchronization is paid for on every INSERT, UPDATE, and DELETE that touches an indexed column. The whole game of indexing is a trade: you spend write throughput, disk space, and maintenance overhead to buy read latency. If you do not understand both sides of that trade, you will end up with a table that has fourteen indexes, half of which the planner never uses, all of which slow down every write, and a VACUUM that can never quite keep up.

The other thing nobody tells you early enough is that creating an index does not guarantee the database will use it. The query planner makes a cost-based decision every time a query runs, and it will cheerfully ignore your beautiful index and scan the whole table if it estimates that the index is the slower path. Frequently it is right. A query that returns 40% of a table is almost always faster as a sequential scan, because random index lookups into the heap are expensive and a sequential read is the thing storage hardware is best at. The index exists; the planner declines to use it; the junior engineer files a bug. There is no bug. There is a selectivity estimate.

This article is Postgres-centric because Postgres exposes the most index types of any mainstream open-source database and gives you EXPLAIN (ANALYZE) to see exactly what the planner chose and why. But the principles — ordering versus equality, write amplification, selectivity, the cost model — transfer to MySQL/InnoDB, SQL Server, Oracle, and SQLite with only the names changed. We will go through each index type by what it is actually good at, then be honest about what indexes cost on write, then dig into how the planner decides, because that last part is where most of the confusion lives.

The B-tree: the default, and usually the right one

When you write CREATE INDEX with no USING clause, you get a B-tree. Specifically a B+-tree variant (Lehman & Yao’s high-concurrency B-link tree, the basis of Postgres’s implementation), where all the actual keys live in the leaf nodes and the internal nodes hold only separator keys to route the search. The leaves are linked in a doubly-linked list, which is the single most important structural fact about a B-tree: because the leaves are sorted and chained, the index supports not just equality lookups but ordered range scans, ORDER BY without a sort, MIN/MAX as a single leaf descent, and prefix matches on text.

                          B-tree (logical structure)

                        +---------------------------+
   internal (root)      |   [ 40 | 80 | 120 ]       |   separator keys
                        +----|------|------|--------+
              +--------------+      |      +------------------+
              v                     v                         v
     +-----------------+   +-----------------+      +-----------------+
     | [10 | 22 | 35]  |   | [55 | 68 | 77]  | ...  | [130|150|175]   |  internal
     +--|---|---|---|--+   +-----------------+      +-----------------+
        v                          ...
   +----------------+     +----------------+     +----------------+
   | 10 12 18 | --> | 22 27 31 | --> | 35 38 ... |  ...  leaf pages
   |  heap TIDs |   |  heap TIDs |   |  heap TIDs |
   +----------------+     +----------------+     +----------------+
        \________________ doubly-linked leaf chain ________________/
                    (enables range scans + ordered output)

Each leaf entry stores the indexed key plus a TID (tuple identifier: the physical (block, offset) location of the row in the heap). A point lookup descends from root to leaf in O(log n) page reads — for a table of a billion rows that is roughly 4 to 5 page accesses, most of which are cached. A range scan finds the lower bound the same way, then walks the leaf chain sequentially until it passes the upper bound.

1
2
3
4
5

-- The default. Equality, ranges, ORDER BY, prefix LIKE, MIN/MAX.
CREATE INDEX idx_orders_created_at ON orders (created_at);

-- Range scan this supports cleanly:
SELECT * FROM orders WHERE created_at >= '2026-06-01' AND created_at < '2026-07-01';

Multi-column indexes and the column-order rule

A multi-column B-tree sorts by the first column, then breaks ties with the second, and so on — exactly like sorting a spreadsheet by column A then column B. This produces the single rule that trips up more people than anything else in indexing: a multi-column index can only use a column for an efficient seek if every column to its left is constrained by an equality predicate.

1

CREATE INDEX idx_events_tenant_time ON events (tenant_id, occurred_at);

This index is excellent for WHERE tenant_id = 42 AND occurred_at >= '...' because tenant_id is pinned by equality, so all rows for tenant 42 are physically contiguous in the index and occurred_at is sorted within them. It is useless as a seek for WHERE occurred_at >= '...' alone, because the occurred_at values are scattered across every tenant’s slice of the index — there is no single contiguous range to scan. The leading column is the gatekeeper. Put the columns most likely to be filtered by equality first, and the column used for ranges or ordering last. Get this backwards and you have built an index the planner will skip.

Covering indexes and index-only scans

Normally an index scan is a two-step dance: find the TID in the index, then fetch the actual row from the heap to get the other columns. That heap fetch is a random read and it is the expensive part. If every column the query needs is already in the index, Postgres can skip the heap entirely — an index-only scan. You can force this by adding non-key payload columns with INCLUDE:

1
2
3
4
5

-- Key column drives the search; included columns ride along to avoid heap fetches.
CREATE INDEX idx_orders_cover ON orders (customer_id) INCLUDE (status, total_cents);

-- This can now be served entirely from the index, no heap access:
SELECT status, total_cents FROM orders WHERE customer_id = 9912;

The INCLUDE columns are stored only in the leaf pages, not in the internal nodes, so they do not bloat the search structure or impose ordering. One caveat with a sharp edge: index-only scans still need to check tuple visibility via the visibility map, so a heavily-updated table whose visibility map is stale (lagging autovacuum) will fall back to heap fetches anyway. Index-only is a VACUUM-dependent optimization, not a free lunch.

Partial indexes

If you only ever query a subset of rows, index only that subset. A partial index is smaller, faster to maintain, and the planner can match it when the query’s WHERE clause implies the index predicate:

1
2
3

-- Only ~2% of orders are 'pending', but they're queried constantly.
CREATE INDEX idx_orders_pending ON orders (created_at)
  WHERE status = 'pending';

This index might be 1/50th the size of a full index on created_at, and every order that is not pending costs nothing to maintain in it. Partial indexes are one of the highest-leverage, most underused features in Postgres.

Hash indexes: equality only, and finally usable

A hash index stores the 32-bit hash of the indexed value and supports exactly one operator: =. No ranges, no ordering, no LIKE, no ORDER BY. In exchange, a lookup is O(1) expected — compute the hash, jump to the bucket — rather than the B-tree’s O(log n) descent, and the index is often smaller because it stores a fixed-width hash instead of the full key (a big win when the key is a long text string or a UUID stored as text).

1
2

CREATE INDEX idx_sessions_token ON sessions USING hash (token);
SELECT * FROM sessions WHERE token = 'a7f3...';   -- the only thing this helps

Hash indexes were discouraged for years for one concrete, embarrassing reason: before PostgreSQL 10 they were not WAL-logged. That meant they were not crash-safe and were not replicated to standbys — after a crash or on a replica you had to REINDEX them. Nobody wanted that, so the universal advice was “just use a B-tree.” Since version 10 hash indexes are fully WAL-logged, crash-safe, and replicated, and the implementation got meaningfully better. Today a hash index on a long, high-cardinality key queried only by equality (session tokens, content hashes, opaque external IDs) can be both smaller and faster than the equivalent B-tree. The honest caveat: a B-tree on the same column also handles equality perfectly well and gives you ranges and ordering for free, so the B-tree remains the safe default. Reach for hash when the column is genuinely equality-only and the size/speed difference measures out in your favor.

GiST: the generalized search tree

GiST (Generalized Search Tree) is not one index — it is a framework for building balanced-tree indexes over data types where “less than” is not the relevant question. The internal nodes hold a predicate that is true for everything in the subtree below, and the operator class for each data type defines what that predicate means and how to test it. This abstraction lets one index structure serve geometry, ranges, full-text, and nearest-neighbor search.

The killer applications:

  • Geometric and spatial data. “Find all points within this bounding box,” “does this polygon overlap that one.” This is the foundation PostGIS builds on; an R-tree-over-GiST handles 2D/3D spatial containment and overlap that a B-tree fundamentally cannot express.
  • Range types. Indexing tstzrange, int4range, etc., to answer “which reservations overlap [14:00, 16:00)” with the && overlap operator. Combined with an exclusion constraint, GiST is how you enforce “no two bookings for the same room may overlap” at the database level.
  • Nearest-neighbor (KNN) search. GiST supports the distance operator <-> as an ordering operator, so ORDER BY location <-> point '(5,5)' LIMIT 10 walks the tree in increasing-distance order and stops after ten — no full scan, no sort.
1
2
3
4
5
6
7
8

-- Prevent overlapping room bookings, enforced by a GiST exclusion constraint:
ALTER TABLE bookings
  ADD CONSTRAINT no_overlap
  EXCLUDE USING gist (room_id WITH =, during WITH &&);

-- 10 nearest stores to a point, ordered by distance, using the index:
CREATE INDEX idx_stores_geo ON stores USING gist (location);
SELECT id FROM stores ORDER BY location <-> point '(40.71,-74.00)' LIMIT 10;

GiST is lossy by default: its internal predicates (bounding boxes) are approximations, so the index produces candidate rows that must be rechecked against the exact condition. That recheck is usually cheap and the alternative — a sequential scan over millions of geometries — is not.

SP-GiST: the space-partitioned cousin

SP-GiST (Space-Partitioned GiST) handles data that partitions naturally and non-uniformly — quadtrees, k-d trees, radix tries. Where GiST builds balanced, overlapping bounding boxes, SP-GiST builds unbalanced, non-overlapping partitions. It shines for data with clustering and natural hierarchy: points that cluster in space, IP address ranges (inet), text indexed as a trie for prefix search. If your data is spatial-but-clumpy or you are doing prefix/IP-range work, SP-GiST can beat GiST; for general 2D geometry GiST is still the default choice.

BRIN: huge tables, tiny index, one big assumption

BRIN (Block Range INdex) is the index for the situation where the table is enormous and the data is physically sorted on disk. Instead of storing an entry per row, BRIN stores a summary per block range — by default, the min and max value across each consecutive group of 128 table pages. For a query like WHERE created_at >= X, BRIN reads its tiny summary, finds the block ranges whose [min, max] could possibly contain matching rows, and tells the heap to scan only those ranges. Everything else is skipped without ever being read.

The numbers are the point. A B-tree on a billion-row append-only events table might be tens of gigabytes. The equivalent BRIN can be a few megabytes — often four or five orders of magnitude smaller — because it stores one tiny tuple per 128-page range instead of one per row.

1
2
3
4
5
6
7

-- Append-only, time-ordered table: rows arrive roughly in created_at order.
CREATE INDEX idx_events_brin ON events USING brin (created_at)
  WITH (pages_per_range = 128);

-- Smaller ranges = more precise pruning, larger index:
CREATE INDEX idx_events_brin_fine ON events USING brin (created_at)
  WITH (pages_per_range = 32);

The trade is brutal and absolute: BRIN only works if the indexed column correlates strongly with physical row order on disk. On a perfectly time-ordered append-only table, each block range has a tight [min, max] and pruning is surgical. If rows arrive out of order, or the table gets updated and re-shuffled, the block ranges develop wide, overlapping [min, max] windows, every range “could match,” and BRIN degenerates into a sequential scan with extra steps. BRIN is the right answer for time-series, log, and event tables; it is the wrong answer for anything with random insertion order. (pg_stats.correlation near ±1 for the column is the signal that BRIN will pay off.)

GIN: the inverted index for “many values per row”

GIN (Generalized Inverted Index) flips the relationship. A B-tree maps one row to one key. GIN handles columns that contain many indexable values per row — arrays, jsonb documents, full-text tsvectors — by building an inverted index: for each distinct element (each array value, each JSON key/value, each lexeme), it stores the list of rows that contain it. Ask “which rows contain the tag urgent” and GIN goes straight to the posting list for urgent.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

-- Array containment: "rows whose tags include 'urgent'"
CREATE INDEX idx_docs_tags ON documents USING gin (tags);
SELECT id FROM documents WHERE tags @> ARRAY['urgent'];

-- JSONB: index the whole document for containment and key-exists queries.
-- jsonb_path_ops is smaller and faster for @> but only supports containment.
CREATE INDEX idx_events_payload ON events USING gin (payload jsonb_path_ops);
SELECT id FROM events WHERE payload @> '{"status":"failed","retryable":true}';

-- Full-text search:
CREATE INDEX idx_articles_fts ON articles USING gin (to_tsvector('english', body));
SELECT id FROM articles WHERE to_tsvector('english', body) @@ plainto_tsquery('index bloat');

GIN is what makes @> (containment), ? (key exists), and @@ (text match) fast. The cost lives on the write side, and it is real: inserting one row with twenty array elements means twenty posting-list updates. To soften that, GIN buffers pending entries in a fastupdate list and merges them in batches, which keeps inserts cheap but means a query may have to scan that unmerged pending list on top of the main index until the next merge. You can tune the merge threshold with gin_pending_list_limit. For workloads that are read-heavy and update the indexed column rarely, GIN is transformational; for high-churn JSONB it deserves a hard look at the write cost. (For “subscriptions matching this document,” there is also GiST-based tsquery indexing, but for plain text search GIN is the standard.)

A nod to columnstore indexes

Everything above is a row-store index: the heap stores complete rows and the index points into them. That layout is optimal for OLTP — fetch a few whole rows by key. It is the wrong layout for analytics, where you scan a billion rows but only touch three columns and want to SUM one of them. Columnstore indexes store each column contiguously and compressed, so an aggregate scan reads only the columns it needs, gets enormous compression ratios (because adjacent values in a column are similar), and runs over vectorized batches instead of row-at-a-time.

SQL Server has had clustered and nonclustered columnstore indexes for years; this is its standard answer for analytical workloads sitting next to OLTP. Core Postgres does not ship a native columnstore index, but the ecosystem covers it: extensions like Citus/Hydra (columnar access method) and external column-oriented engines (DuckDB, ClickHouse, Parquet on a lake) fill the analytical slot. The mental model that matters: row-store indexes optimize “find these few rows”; columnstore optimizes “aggregate these few columns over many rows.” Using the wrong one is a category error no amount of index tuning will fix.

What an index actually costs on write

Every index is dead weight on writes, and the bill comes due silently. When you INSERT a row, the database must add an entry to every index on the table. A table with eight indexes turns one logical insert into one heap write plus eight index writes — this is write amplification, and it is the dominant hidden cost of over-indexing. DELETE is similar: the row and all its index entries must eventually be removed. UPDATE is where it gets subtle and where Postgres’s MVCC design shows through.

Because Postgres never updates a row in place — an UPDATE writes a brand-new row version and marks the old one dead — a naive update would have to insert new index entries for every index, even ones on columns that did not change. The optimization that saves you is the HOT update (Heap-Only Tuple): if an update changes no indexed column and the new row version fits on the same heap page, Postgres skips the indexes entirely and chains the new version to the old one within the page. HOT updates are dramatically cheaper. This produces a concrete design rule with teeth: indexing a column that is updated frequently is doubly expensive — you pay the index maintenance on every update and you forfeit the HOT optimization for that table’s updates. Indexing a hot, high-churn last_seen_at or counter column is a classic self-inflicted wound.

Then there is bloat. Because dead row versions and dead index entries linger until VACUUM reclaims them, a heavily-updated table and its indexes accumulate dead space. Indexes do not shrink on their own; a deleted entry leaves a gap that VACUUM marks reusable but does not return to the OS. Over time an index can become several times larger than its live data warrants, which slows every scan (more pages to read) and every write (more pages to maintain). The fixes are VACUUM to keep dead tuples in check, REINDEX CONCURRENTLY to rebuild a bloated index without locking out writers, and — most importantly — not creating indexes you do not need in the first place. A summary of the trade-offs:

Index type Best for Operators Relative size Write cost
B-tree equality, ranges, ORDER BY, prefix, MIN/MAX = < <= > >= BETWEEN LIKE 'x%' medium medium
Hash equality only, on long/high-cardinality keys = small low-medium
GiST geometry, ranges, KNN, exclusion constraints && @> <-> << (per opclass) medium-large high
SP-GiST non-uniform partitioned data, IP/trie/quadtree && <@ ~>=~ (per opclass) medium medium-high
BRIN huge, physically-ordered tables (time-series) = < <= > >= BETWEEN tiny very low
GIN arrays, jsonb, full-text (many values/row) @> ? ?| ?& @@ large high (buffered)

The “relative size” and “write cost” columns are the part people skip and then regret. GIN and GiST are expensive to maintain; BRIN is nearly free but only works under its ordering assumption; the humble B-tree is the balanced default for a reason.

How the planner decides whether to use an index

Here is the part that surprises people: the planner does not “use the index because it exists.” For every query it builds candidate plans — sequential scan, index scan, index-only scan, bitmap index scan — assigns each an estimated cost in abstract units, and picks the cheapest. The estimate is driven by selectivity: what fraction of rows the predicate is expected to keep.

Selectivity comes from statistics gathered by ANALYZE (run automatically by autovacuum) and stored in pg_statistic, surfaced via pg_stats. For each column Postgres keeps the fraction of NULLs, the number of distinct values, a list of the most-common values with their frequencies, and a histogram of the value distribution. From these it estimates how many rows WHERE x = 7 or WHERE x > 100 will return. Those estimates feed the cost model, parameterized by knobs like seq_page_cost (default 1.0), random_page_cost (default 4.0 — random reads modeled as four times costlier than sequential), and cpu_tuple_cost. The crucial asymmetry: an index scan does random heap fetches (one per matching row, at random_page_cost each), while a sequential scan reads pages in order at seq_page_cost. So an index scan wins only when it touches few enough rows that the random-fetch penalty stays below the cost of just reading the whole table sequentially.

                 Planner: index scan vs. seq scan (simplified)

   query predicate ──► estimate selectivity from pg_stats
                              │
                              ▼
                   estimated rows returned
                              │
              ┌───────────────┴────────────────┐
              │ small fraction of table?         │
              ▼ yes                              ▼ no  (e.g. > ~5-10%)
   random heap fetches stay cheap        random fetches > full
   ─► INDEX SCAN (or BITMAP if           sequential read
      many scattered rows)               ─► SEQUENTIAL SCAN
              │
              ▼
   all needed cols in index? ─► INDEX-ONLY SCAN (skip heap)

This is why the planner “ignores” your index. If WHERE status = 'active' matches 60% of rows, an index scan would do random fetches for more than half the table — far slower than reading the table once, in order. The planner picks the seq scan. It is correct. The index is not broken; it is simply the wrong tool for a low-selectivity predicate. When many rows match but they are scattered, the planner often chooses a bitmap index scan: it walks the index to build a bitmap of matching heap pages, sorts that bitmap into physical order, then reads those pages sequentially — capturing index selectivity while avoiding pure random I/O.

Reading EXPLAIN (ANALYZE)

Stop guessing and ask the database. EXPLAIN shows the chosen plan with estimated costs and row counts; EXPLAIN (ANALYZE) actually runs the query and shows real timings and actual row counts beside the estimates.

1
2

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE customer_id = 9912;

A healthy, selective lookup looks like this:

 Index Scan using idx_orders_customer on orders
   (cost=0.43..38.21 rows=11 width=84)
   (actual time=0.028..0.061 rows=12 loops=1)
   Index Cond: (customer_id = 9912)
   Buffers: shared hit=5
 Planning Time: 0.110 ms
 Execution Time: 0.084 ms

Twelve rows out of millions, five buffer pages touched, 84 microseconds. Compare the same shape of query against a non-selective predicate, where the planner correctly refuses the index:

 Seq Scan on orders
   (cost=0.00..208333.00 rows=6012450 width=84)
   (actual time=0.015..512.880 rows=6011902 loops=1)
   Filter: (status = 'active')
   Rows Removed by Filter: 3988098
   Buffers: shared hit=2048 read=81285
 Planning Time: 0.090 ms
 Execution Time: 690.215 ms

The two numbers to obsess over: cost versus actual time tells you whether the plan was fast, and estimated rows versus actual rows tells you whether the planner’s statistics are any good. When the estimate is wildly off — it expected 11 rows and got 600,000, or vice versa — the planner is flying blind and will pick bad plans. The fix is almost always to refresh statistics with ANALYZE, raise the sampling resolution with ALTER TABLE ... ALTER COLUMN ... SET STATISTICS 1000, or, for correlated columns the planner assumes are independent, create extended statistics with CREATE STATISTICS. Rows Removed by Filter exposes wasted work the index could have eliminated; Buffers: ... read= exposes cold cache misses hitting disk. This is the feedback loop: look at the plan, see why the choice was made, fix the statistics or the index, look again.

For the deeper mechanics of how these costs map to physical I/O and how to tune the knobs, see PostgreSQL internals and tuning; for a workload-driven walkthrough of finding and fixing slow queries, see PostgreSQL performance tuning.

Verdict

Index by query, not by column. Look at the actual predicates your application runs, pick the index type whose strength matches the question being asked, and stop there. The B-tree is the default and is correct the overwhelming majority of the time — for equality, ranges, ordering, and prefixes it does everything and does it well. Reach past it only when the data shape demands it: hash for genuinely equality-only access on big keys, GiST for geometry and ranges and nearest-neighbor and exclusion constraints, SP-GiST for clumpy partitioned and trie/IP data, BRIN when the table is huge and physically ordered and you want a megabyte-sized index instead of a gigabyte one, GIN when each row holds many values to search (arrays, JSONB, full text), and a columnar engine when the workload is analytical scans rather than point lookups.

Then respect the write side. Every index is a tax on every write to its table, frequently-updated indexed columns forfeit the HOT-update optimization, GIN and GiST are expensive to maintain, and all of them bloat without VACUUM. The discipline that separates a fast database from a slow one is not adding indexes — it is being able to justify every index you keep and deleting the ones the planner never chooses (pg_stat_user_indexes.idx_scan = 0 is your hit list). Finally, never assume the index is used: run EXPLAIN (ANALYZE), compare estimated rows to actual rows, and trust the planner’s seq-scan decision on low-selectivity queries — it is almost always right, and when it is wrong the problem is stale statistics, not the planner. Indexes are a trade. Know both sides of it.

Sources

Comments