Database indexing explained: B-trees, composite and covering indexes, and reading a query plan

Key points

• A B-tree has a fan-out of hundreds of entries per page, so even a table of billions of rows is only a few levels deep.
• Every index is updated on every insert and on updates to its columns, and it takes disk and memory. Drop the ones nothing uses.
• In a composite index, equality columns go first and the range or sort column after them. Only a leading prefix of the columns narrows the scan.
• A covering index, built with INCLUDE, can answer a query without touching the table: an index-only scan.
• The planner skips an index when a query matches a large share of rows, when statistics are stale, or when the query wraps the column in a function.
• In EXPLAIN ANALYZE, compare estimated rows with actual rows first: a large gap explains most bad plans.

How a B-tree index finds a row

Without an index, the only way to find the orders of customer 4217 is to read every row of the table. An index keeps a sorted copy of one or more columns, each entry pointing to its row, so the database can jump to the right place instead. In PostgreSQL that pointer is a tuple id: a page number and a slot in the table’s heap.

The B-tree, introduced by Bayer and McCreight in "Organization and Maintenance of Large Ordered Indexes" (1972), was designed for data on disk, where reading a page costs far more than searching inside one. Each node is a whole page. Internal pages hold keys and pointers to the level below; leaf pages hold the index entries and are linked to their neighbors. The paper’s result is that lookups, inserts and deletes take time proportional to log base k of the index size, where k depends on the page size. PostgreSQL’s documentation notes that typically over 99% of a B-tree’s pages are leaves.

The base of that logarithm is what makes B-trees fast. A PostgreSQL page is 8 kB by default, and an entry for a bigint key takes around 20 bytes with its overhead, so one page can hold a few hundred entries. With a fan-out of about 400:

A lookup reads one page per level, and the upper levels are almost always in memory, so finding one row among millions costs a handful of page reads. A range query descends once and then walks the linked leaves in order, which is also why an index can return rows already sorted. When a page fills, it splits in two and a pointer is added to its parent; when the root splits, the tree grows one level taller. The tree stays balanced: every leaf is the same distance from the root.

MySQL’s InnoDB stores tables differently. The table itself is a B-tree ordered by the primary key, the clustered index, with the full rows in its leaves. Every secondary index entry stores the primary key columns rather than a row address, so a lookup through a secondary index descends two trees. InnoDB’s documentation draws the practical conclusion: a long primary key makes every secondary index bigger, so keep it short. A primary key inserted in random order, such as a random UUID, also spreads inserts across the whole tree instead of appending at the end.

What an index costs

• Writes. Every insert adds an entry to every index on the table, and a delete leaves entries to clean up. In PostgreSQL an update that changes an indexed column writes new entries in every index; PostgreSQL’s documentation notes that indexes can also prevent heap-only tuple (HOT) updates, the fast path that skips index maintenance when no indexed column changes.
• Storage and memory. An index competes with table data for the database’s memory. A set of indexes bigger than the table is common and usually a sign that some are unused.
• Building. A plain CREATE INDEX blocks inserts, updates and deletes on the table until it finishes. CREATE INDEX CONCURRENTLY lets writes continue, takes longer and cannot run inside a transaction block.
• Planning. More indexes give the planner more plans to consider, and occasionally a worse one to pick.

PostgreSQL keeps usage counters per index in the pg_stat_user_indexes view. An index whose idx_scan stays at zero over a representative period, and that does not enforce a unique or primary key constraint, is a candidate for removal.

Composite indexes and column order

A composite index on (customer_id, created_at) is sorted by customer_id first, and by created_at within each customer, like a phone book sorted by last name and then first name. That order decides which queries it can serve. PostgreSQL’s documentation states the exact rule: equality conditions on leading columns, plus an inequality on the first column without an equality condition, limit the part of the index that is scanned. Conditions on later columns are still checked inside the index, which saves table visits, but they do not shrink the scan.

Hence the usual rule: equality columns before range columns. With the order reversed, (created_at, customer_id), the query for one customer’s last month reads every order from every customer in that month and discards most of them. Among several equality columns, order matters less for the lookup itself; choose the order that lets the index serve other queries too, since a leading prefix of an index works like an index of its own. An index on (a, b) makes a separate index on (a) redundant.

PostgreSQL’s documentation also advises using multicolumn indexes sparingly: an index on one column is often enough, and indexes with more than three columns are unlikely to help unless the workload is very uniform.

-- orders(id, customer_id, status, email, created_at, total)

-- Composite: equality column first, then the range or sort column
CREATE INDEX orders_customer_created_idx
  ON orders (customer_id, created_at);

-- Covering: the same key, plus a payload column for index-only scans
CREATE INDEX orders_customer_created_cov_idx
  ON orders (customer_id, created_at) INCLUDE (total);

-- Partial: index only the rows most queries look for
CREATE INDEX orders_pending_idx
  ON orders (created_at) WHERE status = 'pending';

-- Expression: serves WHERE lower(email) = lower($1)
CREATE INDEX orders_email_lower_idx ON orders (lower(email));

-- GIN on a jsonb column, for @> containment queries
CREATE INDEX products_attrs_idx ON products USING gin (attrs jsonb_path_ops);

-- A foreign key column, built without blocking writes
CREATE INDEX CONCURRENTLY order_items_order_id_idx ON order_items (order_id);

Covering indexes and index-only scans

A normal index scan finds entries in the index and then fetches each matching row from the table. If every column the query needs is in the index, PostgreSQL can skip the table: an index-only scan. INCLUDE adds columns as payload, stored in the leaf entries but not part of the search key, so SELECT created_at, total FROM orders WHERE customer_id = 42 can be answered from orders_customer_created_cov_idx alone.

• The index type must support it. B-tree always does; GiST and SP-GiST do for some operator classes; GIN cannot, because its entries hold only parts of each value.
• Visibility still has to be checked. PostgreSQL keeps a visibility map with one bit per table page, set by vacuum when every row on the page is visible to all transactions. Rows on pages without the bit set are fetched from the table anyway, and EXPLAIN ANALYZE counts them as Heap Fetches. On a table with heavy updates, index-only scans only pay off if vacuum keeps up.
• A unique index with INCLUDE enforces uniqueness on the key columns only, not on the payload.
• Be conservative with payload columns, especially wide ones: they make the index bigger and slower to search, and an index entry over the size limit makes the insert fail.

Partial and expression indexes

A partial index covers only the rows that match its WHERE clause. If a queue table holds millions of finished jobs and a few hundred pending ones, an index WHERE status = 'pending' stays small and is cheap to keep up to date, because rows outside it never touch it. A partial unique index enforces a rule on a subset, such as one active subscription per user.

The planner uses a partial index only if it can prove the query’s WHERE clause implies the index’s predicate, and it is not a theorem prover: write the condition the same way. Because the check happens at planning time, a condition whose value arrives as a parameter of a generic prepared plan never matches. PostgreSQL’s documentation also warns against creating many partial indexes, one per category, as a substitute for partitioning: one index with the category as its leading column does the job better.

An expression index stores the result of an expression rather than a column. An index on lower(email) serves WHERE lower(email) = 'ana@example.com', and a plain index on email does not. The query has to use the same expression, and the expression is computed on every insert and on updates that cannot use HOT, so writes get a little slower.

Beyond B-trees: hash, GIN, GiST and BRIN

CREATE INDEX builds a B-tree unless you choose another type with USING. The others exist for data a sorted list cannot serve well.

GIN is an inverted index: it maps each element, such as an array item, a JSON key or a word, to the rows that contain it. For jsonb the default operator class, jsonb_ops, supports key-existence operators such as ?; jsonb_path_ops supports fewer operators, mainly containment with @> and the JSON path operators, and the documentation says it performs better for them. GIN updates are slow by nature, since one row can add many entries, so by default new entries go to a pending list that is merged later; a large pending list slows searches until it is cleaned up.

For full-text search, a GIN index on a tsvector column serves @@ queries. Ranking is a separate question: PostgreSQL’s built-in ranking is not BM25 (hybrid search with BM25 and vectors). For document-shaped data in general, see PostgreSQL vs MongoDB.

Selectivity: when the planner ignores your index

The planner does not use an index because it exists; it uses it when its cost estimate says the index is cheaper. Reading through an index means jumping between table pages, which the default settings price at four times a sequential page read (random_page_cost = 4.0 against seq_page_cost = 1.0). For a query that matches a small share of the rows, the index wins easily. For one that matches a large share, reading the whole table in order is cheaper, and the planner is right to do it. In between, PostgreSQL often uses a bitmap scan: it collects matching row locations from the index, sorts them into table order, then reads each page once.

The share of rows a condition matches is its selectivity, and the planner estimates it from statistics that ANALYZE collects: the most common values of each column, a histogram of the rest, the number of distinct values and how closely the physical row order follows the column’s order. Autovacuum runs ANALYZE in the background, but after a bulk load or a large delete the statistics can be badly out of date until it does.

• Low selectivity. An index on a boolean or a status with three values rarely helps, except for a rare value, which is the job of a partial index.
• Small tables. PostgreSQL’s documentation points out that 100 rows probably fit on one page, and no plan beats reading one page.
• Test data. A tiny or artificial dataset produces plans you will not see in production. Test on a copy with realistic size and distribution.
• Correlated columns. The planner assumes conditions are independent, so city = 'Paris' AND country = 'France' looks rarer than it is. Extended statistics (CREATE STATISTICS) fix this.

To check whether an index can be used at all, set enable_seqscan = off in a test session and run the query again. If the planner still avoids the index, the query does not match it; if it now uses it and runs faster, the cost estimates are off, and the statistics or cost settings deserve a look.

Reading EXPLAIN and EXPLAIN ANALYZE

EXPLAIN shows the plan the planner chose, with estimates. EXPLAIN ANALYZE runs the query and adds what actually happened. Because it runs the statement, wrap an UPDATE or DELETE in BEGIN and ROLLBACK. Since PostgreSQL 18, ANALYZE also turns on BUFFERS, which reports pages read. Here is a query for one customer’s latest orders, before any index exists (parallel workers turned off to keep the plan short):

EXPLAIN ANALYZE SELECT created_at, total FROM orders
WHERE customer_id = 4217 ORDER BY created_at DESC LIMIT 20;

Limit  (cost=48536.31..48536.36 rows=20 width=14) (actual time=118.901..118.906 rows=20.00 loops=1)
  Buffers: shared hit=2112 read=21422
  ->  Sort  (cost=48536.31..48536.57 rows=104 width=14) (actual time=118.899..118.902 rows=20.00 loops=1)
        Sort Key: created_at DESC
        Sort Method: top-N heapsort  Memory: 26kB
        ->  Seq Scan on orders  (cost=0.00..48534.00 rows=104 width=14) (actual time=0.412..118.840 rows=97.00 loops=1)
              Filter: (customer_id = 4217)
              Rows Removed by Filter: 1999903
Planning Time: 0.118 ms
Execution Time: 118.931 ms

Read it from the innermost node outward. The sequential scan read every page of a two-million-row table, Rows Removed by Filter shows almost all of that work was thrown away, and a sort was needed for the ORDER BY. After creating orders_customer_created_cov_idx from the examples above:

Limit  (cost=0.43..4.92 rows=20 width=14) (actual time=0.024..0.041 rows=20.00 loops=1)
  Buffers: shared hit=4
  ->  Index Only Scan Backward using orders_customer_created_cov_idx on orders  (cost=0.43..23.79 rows=104 width=14) (actual time=0.023..0.037 rows=20.00 loops=1)
        Index Cond: (customer_id = 4217)
        Heap Fetches: 0
        Index Searches: 1
        Buffers: shared hit=4
Planning Time: 0.162 ms
Execution Time: 0.058 ms

How to read it
  cost=0.43..4.92     estimate in planner units: startup..total; not milliseconds
  rows=104            estimated rows; compare with actual rows below it
  actual time         milliseconds per loop; multiply by loops for the total
  rows=20.00          actual rows, an average per loop (two decimals since PG 18)
  Backward            the index is read in reverse to satisfy ORDER BY ... DESC
  Index Cond          conditions used to navigate the index
  Filter              conditions checked after fetching rows (none here)
  Heap Fetches: 0     no table pages visited: a true index-only scan
  Buffers             hit = pages found in memory, read = pages fetched from disk or the OS

The index scan’s estimate of 104 rows against 20 actual is not a bad estimate: the Limit above it stopped the scan early. Outside that case, a large gap between estimated and actual rows is the first thing to look for in a slow plan. The planner chose joins, scan types and memory for the estimate, so when the estimate is off by orders of magnitude, the rest of the plan is built on it. Stale statistics, correlated columns and functions on columns are the usual causes. Cost numbers are only comparable between plans for the same query.

Common indexing mistakes

-- A function on the column hides it from a plain index on created_at
SELECT * FROM orders WHERE date(created_at) = '2026-11-03';
-- Rewrite as a range on the bare column
SELECT * FROM orders
WHERE created_at >= '2026-11-03' AND created_at < '2026-11-04';

-- A leading wildcard: a B-tree cannot seek to '%son@example.com'
SELECT * FROM users WHERE email LIKE '%son@example.com';
-- Use a trigram index instead (the pg_trgm extension)
CREATE INDEX users_email_trgm_idx ON users USING gin (email gin_trgm_ops);

• Wrapping the indexed column in a function or a cast. Rewrite the condition on the bare column, or create an expression index that matches it exactly.
• Leading wildcards. A B-tree can serve LIKE 'abc%', but not LIKE '%abc'. In a database whose collation is not C, even the prefix form needs an index built with text_pattern_ops.
• Comparing values of different types. In MySQL, comparing a string column with a number converts each value and stops the index from being used for the lookup; in PostgreSQL, match the parameter type to the column type.
• Indexing low-selectivity columns on their own. Use them as a later column in a composite index, or as the predicate of a partial index.
• Wrong column order in a composite index: a range column ahead of an equality column.
• Too many indexes: overlapping ones such as (a) beside (a, b), and ones nothing uses. Each one slows every write.
• Unindexed foreign keys. PostgreSQL indexes primary keys and unique constraints automatically, but not the referencing side of a foreign key, so joins on it and deletes from the parent table scan the child table.

Indexes are the first fix for a slow read; a cache is the next one, with its own trade-offs (caching strategies). BYD Tech builds web apps: the code lives in the client’s GitHub from day one, and AI-assisted work is reviewed by an engineer.