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

For more on query performance, see [query execution plans](/blog/technical/query-execution-plans/). To understand how indexes fit into broader schema design, explore [schema design](/blog/technical/schema-design/) and [relational databases](/blog/technical/relational-databases/).

Real-world Failure Scenarios

Scenario 1: The Covering Index That Doubled Storage Costs

What happened: A developer added a covering index to speed up a high-frequency query that selected 8 columns. The index grew to 40GB on a 60GB table, doubling the effective storage footprint and slowing down writes significantly. The query was 20% faster but storage costs were unacceptable.

Root cause: The covering index included columns that changed frequently (status, updated_at), causing index maintenance overhead on every write. The INCLUDE clause added 6 columns to a table with already 12 indexes, multiplying write amplification.

Impact: Storage costs increased by 40GB. Write throughput decreased by 30% on the indexed table. The query improvement did not justify the storage and write overhead.

Lesson learned: Covering indexes are not free. Each included column adds storage and slows writes. Only use covering indexes when the read performance gain is measured and justified, and when write throughput is not a bottleneck.

Scenario 2: The Partial Index That the Planner Ignored

What happened: A partial index on rare status values was created to speed up queries for those specific rows. Query plans showed the planner was ignoring the partial index and doing sequential scans instead. The rare status queries that should have been fast were still slow.

Root cause: PostgreSQL statistics do not track partial indexes well. The planner underestimated how selective the partial index was and chose a sequential scan because it appeared cheaper. Stale statistics after a large data load made the problem worse.

Impact: Slow queries for rare status values persisted despite the partial index existing. The team spent 2 days debugging before identifying the statistics issue.

Lesson learned: Partial indexes are invisible to PostgreSQL statistics. Always verify that partial indexes are actually being used with EXPLAIN ANALYZE, and run ANALYZE after creating them to ensure the planner has current information.

Scenario 3: The Dropped Index That Caused a Cascade of Slow Queries

What happened: A DBA dropped an unused index to reduce write overhead. Within hours, multiple queries that the application depended on became dramatically slower. The queries had never been flagged as slow because they ran infrequently, but when triggered they were now doing full table scans.

Root cause: The queries were infrequent but expensive. They relied on an index that appeared unused based on low idx_scan counts but was actually essential for those specific query patterns. The idx_scan metric had not captured the queries because they ran during off-peak hours.

Impact: Several business-critical reports timed out during the next morning’s batch run. The index was re-added immediately, but the incident took 3 hours to fully diagnose and resolve.

Lesson learned: Before dropping any index, verify it is not used by any query pattern, including infrequent or batch queries. Check pg_stat_statements for actual query patterns, not just pg_stat_user_indexes. Monitor for at least one full business cycle (including batch jobs) before dropping any index.

Further Reading

• PostgreSQL Documentation: Indexes — Official documentation on PostgreSQL index types and usage
• Use The Index, Luke — Definitive book on SQL indexing by Markus Winand
• PostgreSQL pgstattuple Extension — Tool for measuring index effectiveness and bloat
• PostgreSQL Monitoring — How to track index usage and query performance

Conclusion

Indexes are the primary tool for optimizing query performance in relational databases. B-tree indexes excel at range queries and sorted access. Hash indexes work best for simple equality lookups. Composite indexes enable efficient queries on multiple columns, but column order matters. Covering indexes can eliminate table lookups entirely for specific queries. Partial indexes reduce storage overhead for selective conditions. The right indexing strategy depends on understanding your query patterns, data distribution, and write-to-read ratio. Always measure the impact with real workloads before committing to an indexing strategy.