Database Indexes — B-Tree, Hash, Composite, and Covering Indexes
Fast recall
Quick revision
Core answer
Whether you understand the internal structure of each index type well enough to predict when the planner will use it, ignore it, or choose a sequential scan instead.
Creating a composite index on (a, b, c) and expecting it to accelerate queries filtering only on b or c — the left-prefix rule means only queries starting with column a can use it.
Explain covering indexes and index-only scans — when all required columns are in the index, the database never touches the heap, eliminating random I/O entirely.
Interview-ready guide
Interview answer
Indexes speed up queries — but the deeper question is why some indexes accelerate certain queries and are completely ignored for others. The answer lies in the data structure the index uses.
B-tree — sorted, versatile, the default
- A B-tree keeps column values in sorted order across balanced tree nodes — which means it can answer equality (
= ?), ranges (BETWEEN,>,<), prefix lookups (LIKE 'foo%'), andORDER BYall from the same structure, in O(log n) time - PostgreSQL and MySQL InnoDB use B-tree when you run
CREATE INDEXwithout specifying a type; it handles the vast majority of query patterns in production
Hash index — equality only, nothing else
- A hash index maps each key to a bucket via a hash function — which means
WHERE email = 'alice@example.com'is an O(1) lookup, faster than B-tree's O(log n), but completely useless for ranges, ordering, or prefix matching - PostgreSQL supports hash indexes; MySQL InnoDB does not; they're useful only for very specific equality-heavy workloads
Composite indexes — column order is the decision
- An index on
(customer_id, status)stores rows sorted first bycustomer_id, then bystatuswithin each customer — which means it servesWHERE customer_id = ?or both columns together, but notWHERE status = ?alone because status has no independent sort position in the index - Put the most selective equality column first; range columns last
Covering indexes — eliminate heap fetches entirely
- When the index contains every column a query selects, the database answers it from the index without reading the table — called an index-only scan, which removes the most expensive I/O step for read-heavy queries
- In PostgreSQL:
CREATE INDEX ... INCLUDE (col1, col2)adds columns to the index leaf pages without affecting the sort key
Database Indexes — B-Tree, Hash, Composite, and Covering Indexes
Direct Answer
A database index is an auxiliary data structure — separate from the table — that maps column values to row locations for fast lookups. B-Tree indexes store values in a balanced tree supporting equality and range queries in O(log n). Hash indexes map values through a hash function for O(1) equality lookups but cannot handle ranges. Composite indexes cover multiple columns with a strict left-prefix rule. Covering indexes include all columns a query needs, enabling index-only scans that skip the heap entirely.
Common Mistakes & Pitfalls
Creating a composite index on (a, b, c) and expecting it to accelerate queries filtering only on b or c — the left-prefix rule means only queries starting with column a can use it.
Check your understanding
Answer these without looking back at the article.
- When would the query planner choose a sequential scan over using an available index?
- How do you decide the column order in a composite index?
- What is the difference between INCLUDE columns and regular index columns?
Related interview prep categories
2Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.