Database Indexing: Making Queries Lightning Fast

Picture your school's admission office. Every student who has ever enrolled has one index card, and the cards are filed in the drawer in the exact order the students walked in and submitted their forms -- first-come, first-filed. Now the exam section calls: "We need the marks card for admission number 3427, right now." The clerk has no choice but to start at the front of the drawer and check card after card -- 3427? No. 3427? No. -- until, maybe hundreds of cards later, the right one turns up. If it's the very last card in the drawer, the clerk has to check every single one before finding it.

That is exactly what a database does when you run a query like SELECT * FROM Students WHERE admission_no = 3427; and the table has no index on admission_no. The database engine performs what is called a full table scan: it reads every row, in whatever physical order they happen to sit in, comparing each one to 3427, until it finds a match or runs out of rows. For a class of 40 students this is instant and nobody notices. For a state board's exam-result table with lakhs of rows, or a bank's transaction table with crores of rows, a full table scan is the difference between an answer in a fraction of a second and an answer that takes minutes. An index is the structure a database builds so it almost never has to do a full scan. This chapter builds that idea from the ground up, with real numbers, so that "index" stops being a mysterious performance trick and becomes something you can reason about precisely.

The Dictionary Trick You Already Know

You have used an index your whole life without calling it that. Suppose you need to look up the word "photosynthesis" in a printed dictionary with, say, 60,000 entries. You do not start at "aardvark" and read every single entry until you happen to reach "photosynthesis" -- that would be absurd, and yet it is precisely what a full table scan does. Instead, you exploit one fact: the dictionary is sorted. You flip open to roughly the middle and land on, say, a page starting with "M". Since "photosynthesis" starts with "P", which comes after "M" in the alphabet, you know immediately that the word cannot be anywhere in the first half of the book, so you throw that half away without reading a single entry in it. You flip into the remaining half, land somewhere around "S", realize "P" comes before "S", throw away that new half's second portion, and repeat. Within five or six flips you are standing on the right page. Each flip does not just move you forward -- it eliminates roughly half of everything that's still left to search. That single idea -- sorted data lets you eliminate half the remaining possibilities with each check -- is the entire mechanical basis of a database index.

Turning the Trick Into Numbers: Linear Scan vs. Binary Search

Let's make this precise with algebra a Class 9 student can follow. Call the number of rows in a table n. A full table scan checks rows one at a time with no shortcuts, so in the worst case -- the row you want is the very last one, or doesn't exist at all -- it makes exactly n comparisons. On average, if the matching row is equally likely to be anywhere in the table, it takes about n / 2 comparisons, because you'd expect to find it roughly halfway through.

Here is that worst case traced in code, using ten student roll numbers stored in the arbitrary order they happen to sit in the table, with a search for roll number 738:

table_rows = [452, 118, 799, 233, 561, 87, 950, 304, 615, 738]
target = 738

comparisons = 0
for value in table_rows:
    comparisons += 1
    if value == target:
        break

print(comparisons)   # 10 -- had to check every single row

738 happens to sit last in this unsorted list, so every one of the ten rows gets compared before a match is found -- exactly what "worst case" means for a linear scan.

Now compare that with a binary search, the algorithm version of the dictionary flip, run over the same ten values kept in a separate, sorted structure -- an index:

index = [87, 118, 233, 304, 452, 561, 615, 738, 799, 950]
target = 738

low, high = 0, len(index) - 1
comparisons = 0

while low <= high:
    mid = (low + high) // 2
    comparisons += 1
    if index[mid] == target:
        break
    elif index[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

print(comparisons)   # 2 -- only two checks needed

Trace it by hand: first, low=0, high=9, so mid=4, and index[4] is 452. Since 452 is less than 738, the entire bottom half (positions 0 to 4) is thrown away in one move, and low jumps to 5. Second comparison: low=5, high=9, so mid=7, and index[7] is exactly 738 -- found, after only two comparisons, instead of ten.

The diagram below lays both searches side by side on the same ten rows, so you can see exactly which boxes get checked in each strategy.

Notice the pattern in the trace: after the first comparison, the number of candidate rows that could still hold the answer dropped from 10 to 5. After the second, it dropped to about 2 or 3. In general, after k comparisons, at most n / 2^k candidates remain, because each comparison throws away half of whatever was left. The search ends once that remaining count reaches 1, which happens when 2^k is roughly equal to n -- in other words, when k equals log₂(n), "the number of times you can cut n in half before you're left with one item." You don't need to compute logarithms by hand to use this fact; you just need the shape of the growth, which the table below makes concrete:

• n = 10 rows: linear scan needs up to 10 comparisons; binary search needs about 4.
• n = 1,000 rows: linear scan needs up to 1,000; binary search needs about 10.
• n = 1,000,000 rows: linear scan needs up to 1,000,000; binary search needs about 20.

Doubling the table size adds roughly one extra comparison to a binary search, but doubles the worst case for a linear scan. That gap is not a minor optimization -- it is the entire reason large systems remain usable as they grow. And the difference matters even more in practice than these raw comparison counts suggest, because reading a row from a disk or an SSD typically costs a fraction of a millisecond, while reading a value already sitting in the computer's memory costs a few nanoseconds -- roughly a hundred-thousand times faster. A full table scan of a million-row table on disk can genuinely take several seconds; an indexed lookup on the same table typically finishes in well under a millisecond.

Why Real Databases Don't Just Use a Sorted List

There's a catch with a plain sorted array like the index list above: inserting a new value into the correct sorted position can require shifting every element after it. Insert a new roll number into the middle of a sorted list of a million values, and up to half a million existing values might need to shift over by one slot to make room. For a table that receives constant new rows -- every new UPI transaction, every new student admission, every new IRCTC booking -- that would make writes painfully slow even though reads became fast.

This is why real database systems (MySQL, PostgreSQL, SQLite, and nearly every other relational database) build indexes as a data structure called a B-tree rather than a plain sorted array. The name is unrelated to "binary" -- a B-tree node typically holds not two branches but hundreds, because each node is sized to match one page of disk storage, and a single disk page can comfortably hold hundreds of sorted key values. A useful way to picture it is a multi-level library catalog: the top drawer might say "Authors A-M go to Aisle 1, N-Z go to Aisle 2." Inside Aisle 1's own directory: "A-F on Shelf 3, G-M on Shelf 7." On Shelf 7, the actual sorted items sit in a row. Each level eliminates a huge chunk of the search at once -- not by half, like plain binary search, but by a factor of hundreds -- so only two or three levels are needed even for enormous collections. With a typical fanout of a couple of hundred entries per node, a table of a million rows needs a tree only about three levels deep, meaning the database engine reads roughly three or four index pages from disk to locate any row -- not twenty comparisons, and certainly not a million. B-trees also support fast insertion: a new key is placed into its correct leaf node, and only if that node overflows does it split into two, a localized operation that never requires shifting a million elements.

Creating and Using an Index in SQL

In CBSE's Computer Applications and Informatics Practices courses, you already write statements like CREATE TABLE, PRIMARY KEY, and SELECT ... WHERE. Indexing is what happens underneath those statements. Consider a table of student exam records:

-- A table storing every student's exam record
CREATE TABLE Students (
    roll_no    INT PRIMARY KEY,
    name       VARCHAR(50),
    class      INT,
    marks      INT
);

-- roll_no already has a fast index for free,
-- because PRIMARY KEY builds one automatically.

-- 'marks' has NO index yet, so this scans every row:
SELECT name FROM Students WHERE marks > 90;

-- Build an index so future searches skip the scan:
CREATE INDEX idx_marks ON Students(marks);

-- The exact same query can now use idx_marks
-- instead of reading the whole table:
SELECT name FROM Students WHERE marks > 90;

Two things are worth noticing here. First, declaring a column PRIMARY KEY is not just a rule that says "no duplicates allowed" -- it also silently builds a B-tree index on that column, which is precisely why looking up a row by its primary key is fast even on a huge table without you ever writing CREATE INDEX yourself. Second, an index is a completely separate structure from the table -- it does not rearrange the actual rows of Students on disk. It is closer to the index printed at the back of a thick textbook: the book's chapters are not reshuffled into alphabetical order just because the index exists; instead, the index is a compact, sorted side-list of terms, each pointing to the page number where the real content lives. A database index works the same way -- a sorted list of (column value, pointer-to-row) pairs, stored separately, that the engine consults first and then follows the pointer to fetch the real row.

The Hidden Cost: Why You Cannot Index Everything

If sorted structures make searching so much faster, why not index every column of every table? Because every index has to be kept accurate. Whenever a row is inserted, updated, or deleted, the database must also update every index built on that table -- finding the correct spot in each B-tree and adjusting it, occasionally splitting a node. A table with five indexes turns one INSERT into six pieces of work: one write to the table itself, plus five separate updates to keep each index's sorted structure correct. None of those five extra updates make a single query faster; they exist purely to keep indexes that somebody, somewhere, is presumably using for reads. An index also consumes real disk space, because it stores a sorted copy of the indexed column's values alongside pointers back to the rows -- a large index on a large table can itself be a significant fraction of the size of the table.

The practical rule of thumb: index a column when it is genuinely used often in a query's WHERE clause, in a JOIN condition, or in an ORDER BY. Do not index a column just because it exists. A column like remarks that is rarely searched but frequently updated is a poor candidate -- indexing it would slow down every update for a search benefit that almost never gets used.

Composite Indexes: Order Inside the Index Matters Too

An index can also span more than one column at once. Consider:

CREATE INDEX idx_class_marks ON Students(class, marks);

This builds one sorted structure where rows are ordered first by class, and within each class, by marks. It is much like a directory sorted first by city, and within each city, by surname. Such an index helps a query that filters by class alone (WHERE class = 9), and it helps even more when a query filters by both columns together (WHERE class = 9 AND marks > 80), because the engine can jump straight to the "class = 9" block and then binary-search within it by marks. But it does almost nothing for a query that filters by marks alone with no mention of class, because marks values for any one score are scattered across every class group in this ordering -- exactly as a directory sorted by city-then-surname is useless if you only know someone's surname and not their city. The column listed first in a composite index is the one the index is truly sorted by at the top level; the rest are just tie-breakers within each group of the first column.

A Misconception Worth Correcting

A natural but wrong conclusion from everything above is: "Since indexes make searches faster, adding an index to every column of a table will make the database faster overall." This is false, and the reasoning above shows exactly why. Each individual read on an indexed column does get faster in isolation. But every single write to that table -- every INSERT, UPDATE, or DELETE -- now has to update every one of those indexes, whether or not anyone ever queries by them. A table with ten indexes turns each insert into eleven pieces of work instead of one, and the extra storage for ten sorted copies of the data adds up. A database can genuinely become slower overall after "over-indexing," even though any single SELECT you test by itself looks fast -- the cost has simply moved from reads to writes, and if writes happen far more often than that particular read, the system as a whole loses. The fix is not "more indexes" but "the right indexes": built on the columns that real, frequently run queries actually filter, join, or sort by.

Where This Shows Up Around You

When you check a PNR status on IRCTC, the app is running something conceptually identical to SELECT * FROM Bookings WHERE pnr_number = '...' against a table holding a huge number of live and recent bookings. Because pnr_number is indexed, the lookup returns in a fraction of a second instead of forcing the backend to scan through booking records one at a time. The same logic sits behind a UPI app instantly showing you a past transaction by its reference number, or a bank confirming a transaction ID at the counter: the column you searched by was designed, in advance, to be indexed, precisely because engineers anticipated it would be searched constantly. Every time a large system feels instantaneous for a specific kind of lookup, there is almost certainly an index doing exactly the halving trick you traced by hand earlier in this chapter, just scaled up to millions or crores of rows and several levels of a B-tree.

Check Your Understanding

• 1. A table has 200,000 rows and no index on employee_id. What is the worst-case number of comparisons for a linear scan, and roughly how many for a binary search on a sorted index of the same column? (Answer: worst-case linear scan = 200,000 comparisons; binary search needs about log₂(200,000) ≈ 18 comparisons.)
• 2. A column called last_login_note is almost never used in a WHERE clause but is updated every time a user logs in. Should you index it? Why or why not? (Answer: no -- indexing it would slow down every login-triggered update while providing almost no read benefit, since it's rarely searched.)
• 3. You create CREATE INDEX idx_state_city ON Customers(state, city);. Will this index help a query that filters only by city, with no mention of state? Explain using the directory analogy. (Answer: generally no -- the index is sorted by state first, so city values are scattered across every state group; it cannot be binary-searched by city alone.)
• 4. Why does declaring a column as PRIMARY KEY in SQL make lookups on that column fast, even if you never write a CREATE INDEX statement yourself? (Answer: PRIMARY KEY automatically builds a B-tree index on that column as part of enforcing uniqueness.)
• 5. Explain, in your own words, why database indexes are built as B-trees instead of plain sorted arrays. (Answer: a plain sorted array requires shifting many elements on every insert; a B-tree allows new keys to be placed in a leaf node and only splits that node when it overflows, avoiding large-scale shifting, while still keeping lookups fast via its high branching factor.)

Summary

• Without an index, a database answers a WHERE query with a full table scan: up to n comparisons for n rows, and about n/2 on average.
• An index keeps a separate, sorted copy of a column's values with pointers back to the real rows, enabling something like binary search: each comparison eliminates roughly half of what's left, needing only about log₂(n) comparisons.
• Real databases implement indexes as B-trees, not plain sorted arrays, because B-trees support fast insertion (localized node splits) as well as fast lookup (high branching factor keeps the tree only a few levels deep even for millions of rows).
• PRIMARY KEY builds an index automatically; other columns need an explicit CREATE INDEX.
• Indexes are not free: every write to the table must also update every index on it, and each index consumes extra disk space -- so index the columns real queries actually filter, join, or sort by, not every column.
• A composite index like (class, marks) is sorted by the first column first; it helps queries on that first column, or on both together, but rarely helps a query that filters only by the later column.
• An index is a separate lookup structure, like a book's index page, not a reordering of the table's actual rows.

Think About It

Think about this: How would you explain database indexing: making queries lightning fast to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.