How an Index Works

This is the first page in the Databases section. We'll use one running example on every page: a food delivery app (like Swiggy or Zomato) with an orders table that keeps growing.

The Problem: Finding One User's Orders

Our app stores every order in one table. After a year, it has 10 million rows. A row is one record, here one order.

A user opens "My Orders". The app runs this query (a question we ask the database):

SELECT * FROM orders WHERE user_id = 42;

With no extra help, the database has only one option: read every row and check whether user_id is 42. This is called a full scan.

1orders table (10,000,000 rows)
2 
3Row 1        user_id = 7     ✗
4Row 2        user_id = 42    ✓
5Row 3        user_id = 913   ✗
6...
7Row 10,000,000  user_id = 55 ✗
8 
9→ checked 10,000,000 rows to find 12 orders

It works with 100 rows. With 10 million rows and thousands of users opening the page every second, the database gets very slow.

So we need a way to jump straight to user 42's orders without reading everything.

The Idea: An Index Is Like a Book's Index

Think of a 1,000-page textbook. To find "B-tree", you don't read every page. You go to the index at the back. It lists topics in alphabetical order with page numbers, so you find the word quickly and jump to the right page.

A database index works the same way:

• It is a separate structure, stored next to the table.
• It keeps the values of one column (like user_id) sorted.
• Each entry stores the value plus a pointer, meaning the address of the full row in the table.

Click to zoom

The index is a lookup list. Next, let's see how the database searches that list so fast.

How a B-tree Works

Both PostgreSQL and MongoDB use a B-tree as their default index. A B-tree is a sorted, balanced tree:

• Sorted: values are kept in order, like the book index.
• Balanced: every path from the top to the bottom has the same length, so every search takes about the same number of steps.

The top box is the root. The bottom boxes are leaves, which hold the actual values and pointers. Each box in between says "smaller values go left, bigger values go right".

Click to zoom

To find user_id = 42, the database starts at the root and goes down one level at a time, choosing a direction at each step. It never looks at the other branches.

How many steps for 10 million rows?

In a real database, each box (called a page) holds hundreds of values, not two. Say about 300 per page:

1Level 1 (root):   300 values
2Level 2:          300 × 300       =     90,000
3Level 3:          300 × 300 × 300 = 27,000,000
4 
527 million > 10 million
6→ only about 3 page reads to find any user_id

That is the meaning of O(log n): as the table grows, the number of steps grows very slowly. Ten times more rows adds roughly one extra step, not ten times more work.

Because the values are sorted, a B-tree also helps with more than exact matches:

Now let's compare the two ways the database can run our query.

Full Scan vs Index Scan

1Full scan:   Query → read row 1 → row 2 → ... → row 10,000,000 → 12 matches
2Index scan:  Query → B-tree root → middle → leaf → 12 pointers → 12 rows

A full scan is not always bad. If a query needs 80% of the table, reading everything in order can be faster than jumping around through pointers. The database's query planner (the part that decides how to run a query) makes this choice for you.

Next, let's create the index and prove the database actually uses it.

Creating and Checking an Index

Create an index on user_id:

CREATE INDEX idx_orders_user_id ON orders (user_id);

Then ask the database how it runs the query. EXPLAIN ANALYZE (PostgreSQL) and explain("executionStats") (MongoDB) show the plan and real timing:

EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 42;

Example output before and after (numbers are illustrative):

1BEFORE (no index)
2  PostgreSQL: Seq Scan on orders
3              Rows Removed by Filter: 9999988
4              Execution Time: ~800 ms
5  MongoDB:    stage: COLLSCAN
6              totalDocsExamined: 10000000, nReturned: 12
7 
8AFTER (with index)
9  PostgreSQL: Index Scan using idx_orders_user_id on orders
10              Execution Time: ~0.1 ms
11  MongoDB:    stage: IXSCAN
12              totalDocsExamined: 12, nReturned: 12

What to look for: in MongoDB, compare documents examined with documents returned. If the database examines 10 million to return 12, you are missing an index.

Indexes make reads fast, but they are not free. Let's see what they cost.

The Cost of an Index

An index is a second copy of some data, kept in sorted order. That has two costs:

1. Storage: the index takes extra disk space and memory (RAM).
2. Slower writes: every INSERT, UPDATE, or DELETE must also update every index on that table, so the sorted order stays correct.

1New order placed:
2  write row to orders table
3  + update idx_orders_user_id
4  + update idx_orders_restaurant_id
5  + update idx_orders_created_at
6→ 1 write becomes 4 writes

Rule of thumb: index the columns your important queries filter or sort on, and nothing more.

Now let's put this into words you can say in an interview.

Interview Angle

Common mistakes:

• Saying "indexes make everything faster". They make reads faster and writes slower.
• Forgetting that the planner may still choose a full scan, for example on a tiny table or when most rows match.
• Not mentioning how to verify with EXPLAIN ANALYZE or explain().

Summary

1No index      → full scan (Seq Scan / COLLSCAN) → reads every row → slow
2Index         → sorted B-tree + pointers to rows
3B-tree lookup → O(log n) → ~3 page reads for 10M rows
4Also helps    → ranges (>, <, BETWEEN) and ORDER BY
5Cost          → extra storage + every write updates every index
6Verify        → EXPLAIN ANALYZE / explain("executionStats")

Our orders table is fast to search by user now, but "My Orders" also needs to filter by status and sort by date. Next, we'll look at composite indexes and why the order of columns matters.