Database Indexes: B-Tree, Hash, Covering, and Beyond

Without indexes, every query scans every row. With the right indexes, the database finds rows in milliseconds. The wrong indexes waste space and slow writes. This covers the index types, when to use them, and when not to.

How B-Tree Indexes Work

flowchart TD
    Root["Root: [15]"]
    L1A["Leaf A: [5, 10]"] --> Root
    L1B["Leaf B: [15, 20]"] --> Root
    L1C["Leaf C: [25, 30, 35]"] --> Root
    L1A --> L1AL["5 → row_ptr"]
    L1A --> L1AR["10 → row_ptr"]
    L1B --> L1BL["15 → row_ptr"]
    L1B --> L1BR["20 → row_ptr"]
    L1C --> L1CL["25 → row_ptr"]
    L1C --> L1CM["30 → row_ptr"]
    L1C --> L1CR["35 → row_ptr"]

B-trees cluster data at leaf nodes, with internal nodes routing lookups. A lookup for WHERE id = 20 traverses root → Leaf B → returns the row pointer. Range queries like WHERE id > 15 AND id <= 25 follow the same path to 15, then scan forward through Leaf B and Leaf C.

Why Indexes Exist

A table scan reads every row to find matches. For 100 rows this is fine. For 100 million rows it is prohibitively slow. An index is a separate data structure the database maintains, sorted by indexed columns, allowing fast lookups.

The tradeoff is space and maintenance. Indexes consume disk space. When rows are inserted, updated, or deleted, the database must update every index on that table.

B-Tree Indexes

B-tree is the default and most common index type. Most databases use B-tree for primary indexes, foreign key indexes, and general-purpose queries.

B-trees maintain sorted order, making them effective for range queries. WHERE created_at > '2024-01-01' uses a B-tree index efficiently. The database traverses the tree to the start of the range and reads sequentially.

Equality queries also work well. WHERE email = 'user@example.com' finds the row directly through the B-tree structure.

CREATE INDEX idx_users_email ON users(email);

B-trees handle most query patterns. If you are not sure what index type to use, start with B-tree.

Hash Indexes

Hash indexes compute a hash of the indexed value and store mappings to row locations. They are faster than B-trees for equality queries because they do not traverse a tree, they compute an address and read directly.

CREATE INDEX idx_sessions_token ON sessions USING HASH (token);

Hash indexes have limitations. They do not maintain sorted order, so range queries (WHERE created_at > '2024-01-01') cannot use hash indexes efficiently. Hash indexes also cannot help with prefix matching (WHERE name LIKE 'John%').

Session stores and caches use hash indexes. Any use case where you look up by exact value and never need range operations fits hash indexes well.

Composite Indexes

A composite index spans multiple columns. The index is sorted by the first column, then the second within each first-column value.

CREATE INDEX idx_orders_customer_date ON orders(customer_id, order_date DESC);

This index supports queries filtering by customer_id alone, or by customer_id and order_date together. It does not help queries that only filter by order_date.

Column order matters. Put the most selective column first, or the column used in equality conditions first. A query filtering on customer_id and order_date can use the full index. A query filtering only on order_date cannot use the index because order_date is the second column.

Covering Indexes

A covering index includes all columns needed by a query, not just the indexed ones. The database can satisfy the query entirely from the index without reading the table.

CREATE INDEX idx_orders_covering ON orders(customer_id)
    INCLUDE (order_id, order_date, total_amount);

This index covers queries like:

SELECT order_id, order_date, total_amount
FROM orders
WHERE customer_id = 123;

The database reads only the index, not the table. For high-frequency queries that select few columns, covering indexes provide significant speedups.

Covering indexes add overhead. They consume more space and slow down writes because more data must be written to the index. Use them for frequently executed queries, not every query.

Partial Indexes

A partial index covers only rows matching a condition. This reduces size and maintenance overhead while speeding up specific queries.

CREATE INDEX idx_orders_pending ON orders(created_at)
WHERE status = 'pending';

This index only indexes pending orders. Queries filtering by status=‘pending’ and created_at benefit. Other queries do not.

Partial indexes suit tables with skewed distributions. If most rows have a common status and you frequently query the rare statuses, partial indexes focus on what matters.

When to Index

Index columns that appear in WHERE clauses. If you frequently filter by status, index status. If you join on customer_id, index customer_id.

Index columns used in ORDER BY. Databases can avoid sorting steps if an index provides the required order.

Index foreign keys. Joins perform much better when the database can look up rows by indexed values.

Index columns with high selectivity. An index on a boolean column that is 99% true provides little benefit because most rows match. An index on an account number that is unique is maximally selective.

Capacity Estimation: B-Tree Depth and Size

B-tree depth determines how many disk reads a lookup requires. Most B-trees stay shallow even with large tables.

Depth calculation: a B-tree with a branching factor of roughly 100–300 entries per internal node reaches depth 3 with 1 million to 270 million leaf entries. In practice, a B-tree index on an ID column with 100 million rows typically has depth 3 or 4. Each depth level corresponds to one disk I/O operation, so an index lookup does 3–4 disk reads, compared to a table scan which reads every data page.

Index size estimation: the index entry storage is roughly key_size + 8 bytes per row for the ctid/toast pointer plus B-tree overhead. A 4-byte INTEGER key with a 6-byte PostgreSQL ctid totals about 18 bytes per entry. For 100 million rows, that is roughly 1.8 GB for the leaf level, plus internal node overhead of maybe 5–10% more. A composite index on two 4-byte integers is 26 bytes per entry, or 2.6 GB for 100 million rows.

For covering indexes with INCLUDE columns, add the included column sizes. A covering index on customer_id (4 bytes) with INCLUDE of order_id (4 bytes), order_date (8 bytes), and total_amount (8 bytes) is effectively 32 bytes per row, not 12.

If your table is 10 GB and the indexed columns represent 20% of row size, the index will be roughly 2 GB. If you are unsure, most databases provide commands to estimate index size before creating it.

Index Type Trade-offs

Index Type	Best for	Avoid when	Notes
B-tree (default)	Range queries, equality, sorted output	Suffix/prefix matching requires hash or GIN	Default choice — use unless you have a reason not to
Hash	Fast equality lookups, session stores	Range queries, sorted output, prefix matching	Memcached, Redis, DynamoDB use hash internally
Composite (B-tree)	Queries filtering on leading column, or both columns	Queries on second column only	Column order matters — put equality columns first
Covering (B-tree with INCLUDE)	High-frequency queries with small SELECT lists	Writes, queries selecting many columns	Adds storage and slows writes
Partial	Skewed distributions, rare status values	Common values (most rows match)	Dramatically reduces index size
GiST (PostgreSQL)	Geometric, full-text, range types	Simple equality	Not a general-purpose index
GIN (PostgreSQL)	JSONB, arrays, full-text search	Simple scalar columns	Slow to build, fast to query

Common Production Failures

Wrong index selected by the query planner: Sometimes the planner picks a suboptimal index — a partial index with a different WHERE clause, or a composite index on the wrong column order. Query plans that looked fine on small tables behave differently at scale. Monitor slow queries and use EXPLAIN ANALYZE to verify the index actually gets used.

Index bloat from frequent updates: Heap-only tuples (HOT updates) that cannot reuse dead tuples cause index bloat over time. In PostgreSQL, monitor pg_stat_user_indexes for increasing idx_scan counts without corresponding query speedup. Heavy UPDATE workloads on columns with moderate cardinality can bloat indexes faster than expected.

Covering index column order mistakes: Adding columns to the INCLUDE clause of a covering index without considering query patterns wastes space and slows writes. INCLUDE columns should be the most frequently selected non-indexed columns, not an afterthought.

Forgetting that partial indexes are invisible to statistics: PostgreSQL’s statistics collector does not track partial indexes well. The planner may underestimate selectivity for partial indexes on rare values, leading to table scans when the index would be faster. Verify planner choices with EXPLAIN ANALYZE, not assumptions.

When NOT to Index

Do not index columns you never filter on. Indexes consume space and slow writes without helping reads.

Do not index low-selectivity columns unless you specifically need them. An index on a gender column or a status column with three values rarely helps.

Do not over-index write-heavy tables. Each index must be updated on every insert, update, and delete. Tables with heavy write loads need fewer indexes.

Index Maintenance Overhead

Indexes are not free. Every write operation must update every index on the table. A table with ten indexes costs ten times more to write to than a table with one index.

This matters for write-heavy workloads. Bulk inserts are much slower with many indexes. Some ETL processes drop indexes before loading and recreate them after.

Monitor index usage. Databases track whether indexes are used. Unused indexes waste space and add overhead. Drop them.

Real-World Case Study: PostgreSQL Index-Only Scans

PostgreSQL’s index-only scan feature lets a query return results entirely from the index, without touching the heap. For queries that select only indexed columns, this can cut response time dramatically.

Stack Overflow used this extensively. Their database serves millions of reads per day. A query like SELECT id, title, created_at FROM posts WHERE user_id = 123 can be served entirely from an index on (user_id) INCLUDE (id, title, created_at) — the database reads the index, finds matching rows, and returns without ever touching the main posts table. For their read-heavy workload, this cut latency in half on their most common query patterns.

The catch: visibility map. PostgreSQL only uses index-only scans on pages where it knows all rows are visible to the current transaction. Pages with recently modified rows have bits cleared in the visibility map, forcing heap access anyway. Running VACUUM frequently keeps the visibility map current. On tables with high write volumes, index-only scans might not trigger at all without aggressive autovacuum tuning.

The lesson: covering indexes with INCLUDE columns are not free — they consume more storage and slow writes. But for read-heavy tables where the same few columns are selected repeatedly, the read performance gain is worth it. Profile the actual query patterns before adding covering indexes speculatively.

Identifying Missing Indexes

Query execution plans reveal missing indexes. Most databases provide EXPLAIN or SHOW PLAN commands that display how queries execute. Look for table scans on large tables.

EXPLAIN SELECT * FROM orders WHERE customer_id = 123;

If the plan shows a table scan on orders and orders is large, you need an index on customer_id.

Slow query logs flag frequently executed slow queries. Add indexes based on what your application actually queries, not what you think it queries.

Interview Questions

Q: A query that used an index is suddenly doing a table scan. What happened?

The most common causes: statistics went stale after a large data load, causing the planner to underestimate row counts. An index was dropped or disabled. The query changed — different operator or column — and the existing index no longer matches. A different execution path is being chosen because session parameters changed (like enable_seqscan). Run EXPLAIN and compare to a known-good plan from when it was fast.

Q: How do you decide between a composite index and multiple single-column indexes?

Composite indexes are better when queries consistently filter on both columns together, or when the index can serve as a covering index for common queries. Multiple single-column indexes are better when queries filter on different combinations of columns independently. The PostgreSQL query planner can combine single-column indexes with index scans, but a composite index may be faster for some query shapes. Profile the actual queries.

Q: When would you choose a partial index over a regular index?

Partial indexes make sense when a significant portion of the table is never queried. If 95% of your orders have status=‘completed’ and you only query status=‘pending’ orders, a partial index on pending orders is dramatically smaller and faster than a full index on status. They also help when you need an index on an expression that only applies to a subset of rows. The tradeoff is that queries outside the partial index condition cannot use it.

Q: An application query is slow. You find it is doing a sequential scan on a 50-million-row table despite having an index on the filter column. Why would the planner choose a seqscan over an index scan?

For small result sets, PostgreSQL sometimes prefers sequential scan because it is faster for retrieving many rows from the same pages — index lookups require random I/O. If the query returns more than roughly 5–10% of the table, seqscan wins on modern storage. The planner also chooses seqscan when statistics are stale, or when random_page_cost is set too high relative to seq_page_cost (e.g., on SSDs where random and sequential reads have similar cost). Lower random_page_cost or increase enable_seqscan to force index use for testing.

Q: You are designing indexes for a new schema. What is your process?

Start with the queries the application actually runs, not theoretical access patterns. Identify the most frequent and most latency-sensitive queries. For each, find the filter columns and select columns. Add indexes to support the filters, and covering indexes if the same columns are selected repeatedly. Add foreign key indexes for joins. Then measure under realistic write load to see whether the indexes slow inserts enough to matter. On write-heavy tables, keep indexes lean — every unnecessary index delays writes.

For more on query performance, see query execution plans. To understand how indexes fit into broader schema design, explore schema design and relational databases.