Database indexing architecture, in depth: how indexes attach to storage, what each one costs on write, and how to design composite and covering indexes

What an index is, physically

An index is a sorted copy of one or more columns, each entry carrying a locator that leads back to the full row. Almost every general-purpose engine uses a B+tree for this: internal pages hold separator keys and child pointers, leaf pages hold the entries in key order, and leaves are linked to their neighbours so range scans can walk sideways without climbing the tree.

The reason B+trees dominate is fanout. PostgreSQL uses 8 KB pages and InnoDB 16 KB. Take an index on a bigint in PostgreSQL: each leaf entry is about 16 bytes plus a 4-byte line pointer, so an 8 KB page holds roughly 400 entries, or around 366 at the default 90 percent leaf fill. For 100 million rows that is about 273,000 leaf pages, and the whole tree is 4 levels deep: root, two internal levels, leaves. The root and internal levels, well under a thousand pages, stay in memory, so a lookup costs about one leaf read that might miss the cache, plus whatever the locator leads to.

Wider keys reduce fanout. A 16-byte UUID or a 40-byte text key roughly halves or quarters entries per page, which grows the tree and, more importantly, the share of it that must fit in memory. Key width is a performance decision, not a cosmetic one.

Two ways to point at a row

The locator is where engines diverge, and the difference explains most of their indexing behaviour.

Heap plus tuple identifier (PostgreSQL). Rows live in an unordered heap. Every index, including the primary key, stores a TID: the heap page number and the slot within it. A secondary lookup is one index descent plus one heap page read. All indexes are peers; none is special. The cost is that the heap has no useful order, so a range of index keys can scatter across many heap pages.

Index-organised table (InnoDB). The table is the primary key B+tree: its leaf pages hold the complete rows in key order. If you declare no primary key, InnoDB uses the first unique index on non-null columns, or generates a hidden row id. Secondary index entries store the primary key value, not a physical address. A secondary lookup therefore descends the secondary index, takes the primary key, and descends the clustered index a second time.

Consequences follow directly. In InnoDB, a wide primary key is copied into every secondary index, so a 36-character string key inflates them all. Random keys such as UUIDv4 insert into random leaf pages of the clustered index, causing page splits, whereas sequential keys append to the rightmost leaf. In exchange, primary key range scans read physically adjacent rows. In PostgreSQL, rows move without any logical key changing, so MVCC and index maintenance interact more directly.

The read path: when an index loses

An index wins when it lets the engine read far fewer pages than a full scan. That depends on selectivity, the fraction of rows that match, and on correlation, how closely heap order follows index order. PostgreSQL's planner encodes the hardware assumption in two settings whose defaults are seq_page_cost 1.0 and random_page_cost 4.0: a random page is assumed to cost four sequential ones. On SSD-backed systems many teams lower the random cost, and that alone changes plans.

The toy model below shows the shape of the decision for a 100 million row table with about 60 rows per page and no correlation. It is not the real planner, but it reproduces the crossover.

def plan_cost(rows, rows_per_page, selectivity, heap_correlation=0.0,
              seq_page=1.0, random_page=4.0):
    """Toy model of the index-versus-scan decision, in page-read units."""
    pages = rows / rows_per_page
    seq_scan = pages * seq_page
    matches = rows * selectivity
    # Uncorrelated heap: roughly one random page per match, capped at the table size.
    heap_pages = min(matches, pages) * (1 - heap_correlation) + \
                 (matches / rows_per_page) * heap_correlation
    index_scan = 4 * random_page + heap_pages * random_page   # descent + heap visits
    return seq_scan, index_scan

for sel in (0.00001, 0.001, 0.01, 0.2):
    s, i = plan_cost(100_000_000, 60, sel)
    print(f"selectivity {sel:>7}: seq {s:>12,.0f}  index {i:>12,.0f}")

At a selectivity of 0.001 percent the index needs a few thousand page reads against more than 1.6 million for the scan. At 1 percent the uncorrelated index scan touches most heap pages at random cost and loses. Engines have a middle path: PostgreSQL's bitmap heap scan collects matching TIDs, sorts them by page, and reads each heap page once in order, which is why low-selectivity predicates often show a bitmap plan. The bitmap index article covers the related on-disk bitmap structures used in analytic engines.

The write path: every index is a tax

Reads benefit from a specific index; writes pay for all of them. An insert into a table with six indexes performs seven B+tree insertions, each of which may dirty a different page, generate write-ahead log records, and occasionally split a page.

Updates are where the architectures differ most. In PostgreSQL, an update writes a new row version; see the MVCC article for why. The new version has a new TID, so every index would need a new entry. The heap-only tuple optimisation, HOT, avoids this when no indexed column changed and the new version fits on the same heap page: the indexes keep pointing at the old slot, and a redirect chain inside the page leads to the new version. Adding an index on a frequently updated column silently disables HOT for those updates and can multiply write volume and bloat. Leaving free space with a lower table fillfactor raises the HOT rate for update-heavy tables.

In InnoDB, updates happen in place in the clustered index, with old versions kept in undo logs. Secondary indexes are only touched if their columns change; the change is a delete-mark of the old entry and an insert of the new one, with purge removing marked entries later. Changing a primary key value is expensive because it rewrites the row's position and every secondary entry.

LSM-tree engines make index writes cheap by turning them into sequential appends, and pay later in compaction and read amplification; the LSM-tree article explains the trade. Either way, the rule holds: count your indexes and justify each one.

Composite indexes and column order

A composite B+tree sorts entries by the first column, then by the second within ties of the first, and so on. A query can use the index efficiently only for a contiguous leading prefix of columns with equality conditions, followed by at most one range condition. After a range column, later columns can still filter entries but cannot narrow the scan.

That gives the practical ordering rule: equality columns first, then the column used in a range or ORDER BY, then columns only needed for output. Selectivity matters less than folklore suggests; order is dictated by which predicates are equalities. Some engines relax the leftmost-prefix rule with skip scan, iterating over the distinct values of a leading column that the query does not constrain: MySQL added skip scan range access in 8.0.13 and PostgreSQL added B-tree skip scan in version 18. It helps when that leading column has few distinct values, and is not a reason to design indexes carelessly.

-- Orders: 100M rows. Hot query: a customer's recent open orders, newest first.
SELECT id, created_at, total
FROM orders
WHERE customer_id = $1 AND status = 'open' AND created_at >= now() - interval '30 days'
ORDER BY created_at DESC
LIMIT 20;

-- Equality columns first, then the range/sort column, then payload for covering.
CREATE INDEX CONCURRENTLY orders_cust_status_created
    ON orders (customer_id, status, created_at DESC)
    INCLUDE (id, total);              -- PostgreSQL 11+: payload only in leaf tuples

-- Verify: expect Index Only Scan, no Sort node, and low "Heap Fetches".
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, created_at, total FROM orders
WHERE customer_id = 42 AND status = 'open' AND created_at >= now() - interval '30 days'
ORDER BY created_at DESC LIMIT 20;

Walk through the example. customer_id and status are equalities, so the scan starts at the exact position for that pair. created_at DESC matches both the range and the sort, so the engine reads entries in the order the query wants and stops after 20, with no sort step. INCLUDE (id, total) stores the remaining selected columns only in leaf tuples, making the index covering without widening the internal pages.

Covering indexes and index-only scans

If every column a query needs is present in the index, the engine can skip the row lookup entirely. In InnoDB this is natural: every secondary index already contains the primary key columns, so a query selecting only indexed columns plus the key is covered.

PostgreSQL has a catch rooted in MVCC. Index entries carry no visibility information, so an index-only scan must still confirm each row version is visible. It does this through the visibility map, one bit per heap page that says whether all tuples on the page are visible to everyone. Pages marked all-visible skip the heap check; others fall back to a heap fetch, reported as Heap Fetches in EXPLAIN ANALYZE. The map is set by vacuum, so on a table vacuumed rarely, an index-only plan quietly degrades into an ordinary index scan. Tune autovacuum on tables whose hot queries rely on it; the vacuum and bloat article explains the settings.

Failure modes

• Unused and redundant indexes. An index on (a) is redundant next to one on (a, b) for most purposes, yet both are maintained on every write.
• Predicates that hide the column. WHERE lower(email) = $1 cannot use an index on email; create an expression index or store a normalised column. Implicit casts, such as comparing a text column with a number, do the same.
• Stale statistics. The planner estimates selectivity from sampled statistics. After a bulk load, run ANALYZE, or plans will be built on the old distribution.
• Blocking builds. A plain CREATE INDEX in PostgreSQL blocks writes for the duration. Use CREATE INDEX CONCURRENTLY, and check for an invalid index if it fails partway.
• Random keys in a clustered table. UUIDv4 primary keys in InnoDB fragment the clustered index and bloat every secondary index.
• An index that kills HOT. Indexing a column that changes on every update can double write volume.

Operating an index portfolio

Treat indexes as a portfolio reviewed against real workload, not as a one-time design. Start from the slowest and most frequent queries in your statement statistics, design an index per query shape using the ordering rule, and verify with EXPLAIN ANALYZE and buffer counts rather than elapsed time alone, which is noisy. Then audit regularly for indexes that are not pulling their weight:

-- 1. Indexes never used since statistics were last reset (check every replica too).
SELECT s.relname AS table_name, s.indexrelname AS index_name,
       pg_size_pretty(pg_relation_size(s.indexrelid)) AS size, s.idx_scan
FROM pg_stat_user_indexes s
JOIN pg_index i ON i.indexrelid = s.indexrelid
WHERE s.idx_scan = 0 AND NOT i.indisunique AND NOT i.indisprimary
ORDER BY pg_relation_size(s.indexrelid) DESC;

-- 2. Share of updates that were HOT (no index maintenance needed).
SELECT relname, n_tup_upd, n_tup_hot_upd,
       round(100.0 * n_tup_hot_upd / nullif(n_tup_upd, 0), 1) AS hot_pct
FROM pg_stat_user_tables
ORDER BY n_tup_upd DESC LIMIT 20;

Check usage on every replica before dropping, because a read replica may serve queries the primary never sees. In PostgreSQL, a low HOT percentage on an update-heavy table is a signal to look for an index on a frequently changing column. Record the reason for each index in a migration comment, so the next person can tell a deliberate index from an accident.

What to do next

1. Find your top ten queries by total time from statement statistics and write down their predicates and sort order.
2. For each, design one composite index: equality columns first, then range or sort, then INCLUDE payload if covering is worthwhile.
3. Verify each with EXPLAIN (ANALYZE, BUFFERS): expect no Sort node, few heap fetches and a small buffer count.
4. Run the audit queries, and drop unused or redundant indexes after checking every replica.
5. Check the HOT update percentage on your busiest tables and lower fillfactor or remove indexes on volatile columns if it is low.
6. In InnoDB, confirm primary keys are compact and roughly sequential.
7. Schedule ANALYZE after bulk loads and watch index bloat monthly.