Database Indexing: Making Queries Fast

Open the IRCTC app and check your PNR status, or open your bank's UPI app and search for a transaction from three months ago. The answer shows up in a fraction of a second, even though the database behind that app is not storing your one ticket or your one transaction — it is storing crores of them, from lakhs of different people, all mixed together in one giant table. Somehow, out of all those rows, the system finds exactly the one you asked for almost instantly. That is not magic, and it is not just "fast computers." It is a data structure called an index, and understanding how it works will change how you think about every database table you ever design.

To see why an index matters, we first need to see what happens without one — because the "slow way" is the default way, and every database starts out doing it unless you tell it otherwise.

When "just look through everything" stops working

Imagine your school keeps a single table called students with one row per student: roll number, name, and marks. Suppose this table exists at the state level — one shared database used by an education portal covering every government school in a district, with 80,000 student rows in it. A clerk wants to pull up the record for roll number 4471029.

If the database has no index on the roll number column, here is exactly what it does: it opens the table at row 1, checks "is this roll number 4471029? No." Moves to row 2. Checks again. No. Row 3. No. This continues, one row at a time, until it either finds a match or reaches the very last row. This is called a full table scan (or linear scan), and it is the only option a database has for a column with no index — it has no way to "guess" where in the 80,000 rows the answer might be, so it has to look at everything until it stumbles onto the right one, or proves the row doesn't exist by checking all 80,000.

In the worst case — the roll number is the very last row, or doesn't exist at all — that is 80,000 comparisons for a single lookup. Do that for every clerk, every teacher, every parent checking a result, thousands of times a day, and the system grinds to a crawl. This is the exact problem indexing solves, and to understand the solution properly, it helps to start from something you already know.

The book index you already know

Open the back pages of any thick textbook and you'll find a section literally called "Index" — an alphabetically sorted list of terms, each followed by a page number. If you want to find every place "Photosynthesis" is mentioned in a 400-page biology book, you do not flip through all 400 pages reading each one. You jump to the index, find "Photosynthesis" (which sits alphabetically, so you can jump roughly to the P section immediately), read off the page numbers, and turn straight to those pages.

A database index works on exactly this principle, and the name is not a coincidence — it was borrowed directly from this idea. An index is a separate, much smaller structure that stores the values of one column (like roll number) in sorted order, with each value pointing to where the full row actually lives in the table. The database doesn't reorganize your entire table to do this — it builds and maintains this compact, sorted lookup structure on the side, the same way a book's index sits at the back without rearranging the chapters.

The key insight is: searching becomes fast not because the computer got smarter, but because sorted data lets you skip huge portions of the search space instead of checking every entry. Let's make that precise with numbers.

A hands-on example: searching a sorted class list

Here is a tiny table of 8 students, sorted by roll number — small enough that we can count every single comparison by hand:

roll_no | name          | marks
--------|---------------|------
101     | Aditi Sharma  | 78
105     | Rohan Mehta   | 65
110     | Kabir Singh   | 91
115     | Sneha Reddy   | 55
120     | Farhan Ali    | 88
125     | Meera Iyer    | 73
130     | Vikram Nair   | 60
135     | Priya Das     | 95

We want to find the row where roll_no = 125 (Meera Iyer).

Method 1 — linear scan (no index). Start at row 1 and compare each roll number to 125, in order:

101 = 125? No   (comparison 1)
105 = 125? No   (comparison 2)
110 = 125? No   (comparison 3)
115 = 125? No   (comparison 4)
120 = 125? No   (comparison 5)
125 = 125? Yes! (comparison 6) -> found

It took 6 comparisons to find a row that was sitting 6th out of 8. If Meera Iyer's row had been last, it would have taken all 8.

Method 2 — binary search on the sorted index. Because the roll numbers are sorted, we don't need to check them one by one. We can check the middle value first, and immediately eliminate half the remaining rows depending on whether our target is bigger or smaller:

Rows are positions 1-8: [101,105,110,115,120,125,130,135]

Step 1: low=1, high=8, mid=4 -> value at position 4 is 115
        Is 125 = 115? No. Is 125 > 115? Yes -> search only positions 5-8
        (comparison 1 — right half of the table just got thrown away)

Step 2: low=5, high=8, mid=6 -> value at position 6 is 125
        Is 125 = 125? Yes! -> found
        (comparison 2)

It took 2 comparisons instead of 6. On this tiny table the saving looks small, but notice why it worked: each comparison didn't just rule out one row — it ruled out an entire half of the remaining table in one shot. That "cut in half every time" behaviour is the entire secret, and it scales in a way linear scanning never can.

From comparisons to a formula: why halving matters

Every time binary search makes one comparison, the number of rows left to search is cut in half. Starting from n rows, after 1 comparison there are n/2 left; after 2 comparisons, n/4; after 3 comparisons, n/8. The question "how many times can I halve n before only 1 row is left?" is precisely what the mathematical function log₂(n) (log base 2 of n) answers. You don't need to compute logarithms by hand to use this — you just need to trust the pattern, and check it against the doubling-guess game you may already know: if someone picks a number between 1 and 100 and you can only ask "is it higher or lower," you can always find it within 7 guesses, because 2⁷ = 128 ≥ 100. That's log₂(100) ≈ 6.64, rounded up to 7. Here is what that means for table sizes that actually show up in real systems:

rows in table (n)   linear scan (worst case)   with sorted index (~log2 n)
10                   10                          4
100                  100                          7
1,000                1,000                       10
10,000               10,000                      14
1,00,000             1,00,000                    17
1,00,00,000          1,00,00,000                 24

Look at the last row: a table of one crore rows — roughly the scale of a large Indian state's Aadhaar-linked school enrollment records — needs at most 24 comparisons with an index, versus up to one crore without one. That is the entire reason IRCTC or your bank can answer instantly: they are not doing crore-scale linear scans on every request. They built exactly this kind of sorted lookup structure on the columns you search by, such as PNR number or transaction reference ID.

What a database index actually is

Now we can state it precisely. A database index is an auxiliary data structure, built on one or more columns of a table, that stores those column values in sorted order together with a pointer to the location of the corresponding full row. It does not replace the table or duplicate all its data — it is a lean, separate structure whose only job is to make lookups on that column fast. When you run a query that filters or sorts by an indexed column, the database engine uses the index to jump almost directly to the matching rows, instead of scanning the whole table.

An index is always built on specific column(s) — you don't get "the table is indexed," you get "column X is indexed." A table can have several indexes, one for each column (or combination of columns) you search by often, but as we'll see shortly, that freedom comes with real costs, so you don't index everything blindly.

Creating and using an index in SQL

Suppose our students table exists in a real database, created like this:

CREATE TABLE students (
    roll_no INT PRIMARY KEY,
    name    VARCHAR(50),
    marks   INT
);

Because roll_no is declared as the PRIMARY KEY, the database automatically builds an index on it — primary keys are indexed by default in every major database system, exactly because they're the column you'll look rows up by most often. So this query is already fast:

SELECT name, marks FROM students WHERE roll_no = 125;
-- result: Meera Iyer, 73

But suppose the school portal also lets a teacher search by student name — a column that has no index by default:

SELECT roll_no, marks FROM students WHERE name = 'Meera Iyer';

Without an index on name, this forces a full table scan even though the roll number column right next to it is indexed — indexing is per-column, not per-table. To fix this, you explicitly create an index:

CREATE INDEX idx_students_name ON students(name);

After this statement runs, the database builds a sorted structure mapping every name to its row location. The next time you run the same WHERE name = 'Meera Iyer' query, the engine can use idx_students_name instead of scanning row by row. Most database systems let you check this with an EXPLAIN command placed before a query — it doesn't run the query, it just reports the plan the engine intends to use. Before the index existed, the plan would report a scan type of ALL (meaning "every row"); after creating the index, the same query's plan reports a scan type like ref (meaning "used an index to jump to matching rows directly"). Seeing that word change from ALL to an index-based type is the standard way database developers confirm an index is actually being used.

Peeking inside: how B-Trees keep indexes fast even for millions of rows

The binary search example above is a useful mental model, but real databases don't literally store the index as one giant sorted array in memory the way we did with 8 rows. There's a practical problem: if you insert a new student with roll number 112, it belongs between 110 and 115 in our sorted list — and in a plain array, inserting it there means shifting every single value after it one slot to the right. For a table with lakhs of rows, that's an enormous amount of shifting for every single insert.

To avoid this, real databases store indexes using a structure called a B-Tree (short for "balanced tree"). Instead of one long sorted line, a B-Tree is organized like a multi-level library catalog: a small root node holds a few key values that just tell you which direction to go ("values up to 115 are this way, values above 115 are that way"), and each direction leads to another node, until you reach a bottom-level "leaf" node that actually holds the sorted keys for that range along with pointers to the real rows. Because each node can hold many keys (not just one), the tree stays wide and shallow — even a table with a crore rows typically needs a B-Tree only 3 or 4 levels deep. Finding a row means visiting just 3 or 4 nodes, top to bottom, following the direction pointed to at each level.

This matters for a subtle but important reason: each node visit in a B-Tree usually corresponds to one read from disk, and disk reads are the slowest part of the whole operation — far slower than the in-memory comparisons we counted earlier. So the real measure of an index's speed isn't "number of comparisons," it's "number of node visits," and a B-Tree keeps that number tiny (3-4) regardless of whether the table has ten thousand rows or ten crore rows, while also allowing new values to be inserted by rearranging a small local part of the tree instead of shifting an entire array.

The catch: indexes are not free

It's tempting to conclude "indexes only make things faster, so I should index every column." This is wrong, and it's one of the most common mistakes beginners make when they first learn about indexing.

An index is a real, separate data structure that the database has to keep in sync with the table at all times. Every time you INSERT a new row, the database doesn't just add it to the table — it must also update every single index built on that table, inserting the new value into each B-Tree in its correct sorted position. The same is true for UPDATE (if you change an indexed column's value, its position in the index must move) and DELETE (the entry must be removed from every index too). So while indexes make SELECT ... WHERE queries faster, they make INSERT, UPDATE, and DELETE slower — because more structures have to be maintained on every write.

Indexes also cost storage. Each index duplicates the indexed column's values (plus pointers) in its own structure, so a table with five indexes on it is storing a meaningful amount of extra data beyond the table itself, purely to make lookups fast.

Correcting a common misconception

Misconception: "Adding an index to a column always makes queries on that table faster, so more indexes are always better."

Why it's wrong: Indexes trade write speed and storage for read speed. A table that is written to constantly — say, a live table logging every UPI transaction as it happens, with thousands of inserts per second — pays a real cost for every extra index, because each insert now has to update every index too. If that table also has ten indexes built on columns nobody actually searches by, you've paid the storage and write-speed cost for zero benefit. The correct mental model is not "index everything" but "index the specific columns that are actually used often in WHERE, JOIN, or ORDER BY clauses, and leave the rest alone."

Choosing what to index — cardinality matters

Even among columns you do search by, some benefit far more from an index than others. This comes down to a property called cardinality: the number of distinct values a column can hold.

A column like aadhaar_number or roll_no has high cardinality — nearly every row has a different value, so an index can narrow a search down to one or a handful of rows almost immediately, exactly like our binary search example. But a column like gender, with only two or three possible values, has very low cardinality. An index on it can only ever narrow the search down to "roughly half the table" (everyone with that value) — it can't get you close to a single row the way a high-cardinality column can. Building a B-Tree on such a column still costs storage and slows down writes, while barely helping reads, because the database often still has to check a large fraction of the matching rows afterward anyway. This is why experienced database designers prioritize indexing high-cardinality columns that show up often in WHERE clauses — like roll numbers, PNR numbers, Aadhaar numbers, or transaction IDs — over low-cardinality ones.

Summary

• Without an index, a database answers a query with a full table scan — checking every row, one by one, up to n comparisons for n rows.
• An index is a separate, sorted structure built on one or more columns that maps values to row locations, the same idea as a book's index at the back — it does not rearrange the table itself.
• Sorted data enables binary search: each comparison eliminates half the remaining rows, so the number of comparisons needed grows like log₂(n) instead of n — for a table of one crore rows, that's roughly 24 steps instead of one crore.
• Real databases implement indexes as B-Trees: wide, shallow tree structures that keep lookups to just 3-4 node visits (disk reads) even at huge scale, while also allowing efficient inserts without shifting an entire sorted array.
• Primary keys are indexed automatically; other columns need an explicit CREATE INDEX statement.
• Indexes speed up reads (SELECT) but slow down writes (INSERT/UPDATE/DELETE) and use extra storage — so indexing every column is a mistake, not a best practice.
• Prioritize indexing high-cardinality columns (many distinct values, like roll numbers or Aadhaar numbers) that are frequently used in WHERE, JOIN, or ORDER BY — not low-cardinality columns like a two-valued flag.

Active recall — test yourself before checking answers

1. A table has 4,096 rows and a B-Tree index on the column you're filtering by. Roughly how many comparisons would binary search on a sorted structure of this size need in the worst case? (Hint: 2¹² = 4096.)
2. You create a table with an employee_id INT PRIMARY KEY column but never write a CREATE INDEX statement. Is employee_id indexed or not? Why?
3. A logging table receives 5,000 INSERT statements per second and is almost never queried with SELECT ... WHERE. Should you add several indexes to it "just in case"? Explain using the read/write trade-off.
4. Between a column storing "blood group" (8 possible values: A+, A-, B+, B-, AB+, AB-, O+, O-) and a column storing "PAN number" (unique per person), which is the better candidate for an index, and why does cardinality matter here?
5. Explain in your own words why a B-Tree's cost is measured in "node visits" rather than raw comparisons, and why that unit matters for performance on disk-based databases.

Answers: (1) log₂(4096) = 12, so about 12 comparisons. (2) Yes — primary keys are indexed automatically by the database engine, no explicit statement needed. (3) No — with almost no reads to speed up, every added index would only slow down each of those 5,000 inserts per second and add storage cost for no real benefit. (4) PAN number — it has far higher cardinality (nearly unique per row), so an index on it narrows a search down close to a single row, while an index on blood group can only narrow things down to one of 8 large groups. (5) Because each node visit typically means one read from disk, which is far slower than an in-memory comparison — so the real-world cost of a lookup is dominated by how many nodes (disk pages) must be read, not by how many values are compared once a page is already in memory.