How does a database index actually work and when to use it?

Cover these key points to impress the interviewer

An index is a database structure that speeds up data retrieval operations on a table - You should understand that an index is a separate data structure maintained by the database specifically to enable faster lookups.

Without an index, finding a record requires a full table scan with O(n) linear time complexity - You should be able to explain what happens during an unindexed query - the database must check every single row sequentially. Great candidates connect this to algorithmic complexity, showing they understand the scalability implications as tables grow.

Indexes enable sub-linear time complexity (typically O(log n)) for lookups - You should articulate the specific performance improvement that indexes provide. Strong answers go beyond "faster" to quantify how much faster!

Indexes come at a cost - they require additional storage space and slower write operations - You should always discuss trade-offs when recommending any technical solution. The best responses acknowledge that indexes aren't universally beneficial - they're a strategic choice that you need to make based on the trade-offs.

You should create indexes on columns that are frequently used in WHERE clauses or JOIN conditions - You should demonstrate practical knowledge of when to apply indexing.

Primary keys are typically indexed by default, but other columns need explicit indexing - You should understand which columns get automatic indexing and which require deliberate action.

Let me start with the fundamental problem that indexes solve. Imagine you have a database table with millions of user records, and you need to find all users who live in Bengaluru. Without an index on the city column, what does the database have to do? It has no choice but to perform a full table scan - it literally opens up the table and examines every single row, one by one, checking whether the city column matches "Bengaluru." This is O(n) linear time complexity. With a million rows, you're making a million checks. With ten million rows, ten million checks. You can see how this scales terribly.

A database index fundamentally changes this equation. An index is a separate data structure that the database maintains alongside your table. It contains a copy of the selected column's data, but sorted and organized in a way that enables dramatically faster lookups. Instead of scanning through every row linearly, the database can use the index to jump directly to the relevant data using binary search, typically achieving O(log n) logarithmic time complexity. The difference is staggering - finding a record in a million-row table might take a million operations without an index, but only about 20 operations with a proper index.

The classic analogy here is the index at the back of a book. If you want to find every mention of "dependency injection" in a programming textbook, you have two options. You could read through every single page looking for those words, or you could flip to the index, look up "dependency injection" (probably at the beginning of the index section since it starts with “d”) and see a list like "pages 45, 78, 134, 201." You'd immediately jump to those specific pages. The index at the back of the book takes up additional pages - that's the storage cost - but it saves you enormous time when you need to find something specific.

However, and this is crucial for a complete answer, indexes aren't free. First, they consume additional storage space because the database is maintaining this separate lookup structure. Second, and often more importantly, they slow down write operations. Every time you INSERT a new row, UPDATE a value in an indexed column, or DELETE a row, the database must update not just the table but also the index structure. This means indexes are a trade-off: you're exchanging storage space and write performance for dramatically improved read performance.

So when should you use an index? You should create indexes on columns that are frequently used in WHERE clauses, JOIN conditions, or ORDER BY statements in your queries. These are the operations where indexes provide the most value. However, you should avoid over-indexing - don't index columns that are rarely queried or that change frequently, because you'll pay the write performance and storage costs without getting meaningful read performance benefits. One more thing to note: primary keys are typically indexed automatically by the database, but other columns require you to explicitly create indexes. This is an important design decision you make when optimizing your database schema.

The landscape of technical interviews is evolving rapidly. With AI assistants becoming commonplace in development workflows, interviewers are shifting their focus. They're less interested in whether you can recall syntax or API details - AI can provide that instantly. What they're really probing for is whether you understand the foundational concepts deeply enough to make sound architectural decisions. Questions about indexing trade-offs, performance implications, and when to apply specific optimizations are perfect for evaluating this kind of deep understanding. This is exactly what I focus on in my courses at Java Brains - not just teaching you what to do, but helping you understand why it works, so you can reason about these concepts confidently in any interview scenario. The All Access Pass gives you this foundational understanding across the entire backend engineering stack.

Till next time,

Java Brains Interview Question of the Day