Database Indexing: Optimize Query Performance

Every time someone checks a PNR on IRCTC, a query runs against a bookings table holding well over a hundred million rows accumulated over years of ticketing. The query is trivial to write: SELECT * FROM bookings WHERE pnr_number = 4521789034;. The question this chapter answers is what happens physically on disk between typing that query and getting an answer in under a second, instead of the minute or more it would take if the database simply read the table from the top. The answer is a data structure called a B+ tree index, and understanding it requires nothing more exotic than the balanced trees and asymptotic reasoning you already have from your data structures work — applied to a new constraint: data that lives on disk, not in RAM.

The cost of not having an index

A relational table is stored on disk as a heap file: a sequence of fixed-size blocks (also called pages), each block holding as many rows as fit. Disks are not read byte by byte — the smallest unit a database ever fetches is one block, typically 8 KB. This single fact is the reason indexing works the way it does, so hold onto it.

Take a concrete size. Suppose the IRCTC bookings table has 10,000,000 rows, each row (PNR, passenger details, train number, journey date, coach, seat, status) averaging 200 bytes, stored in 8192-byte blocks.

rows per block  = floor(8192 / 200) = 40
total blocks    = 10,000,000 / 40   = 250,000

Without an index, finding the row with a given PNR means a full table scan: the engine reads block 1, checks its 40 rows, reads block 2, checks its 40 rows, and so on, until it finds a match or exhausts the file. If the matching row is equally likely to be anywhere, the expected number of blocks read before finding it is about half the file — roughly 125,000 block reads. If the PNR doesn't exist, or the query is an aggregate like COUNT(*) WHERE status = 'CANCELLED', every one of the 250,000 blocks must be read. At a conservative 5 milliseconds per random block read, 125,000 reads is over ten minutes. That is the cost an index exists to eliminate.

Why a plain binary search tree doesn't fix this

You already know that a balanced binary search tree turns an O(n) linear search into an O(log₂ n) search. For 10,000,000 rows, log₂(10,000,000) ≈ 23.3, so a balanced BST would need about 24 comparisons to find a key. That looks like a huge win over 125,000 — until you remember the one fact above: every node visit that isn't already sitting in memory costs one disk block read. A binary tree has two children per node, so each level of the tree lives in a different block. Walking 24 levels means 24 separate disk reads. That's better than 125,000, but far from optimal — and disk seeks are slow enough that shaving that number further matters a great deal in practice.

The fix is to stop forcing the tree to have exactly two children per node. A block is 8192 bytes regardless of how many keys you pack into it — so pack in as many keys and child pointers as will fit, and let each node span dozens or hundreds of children instead of two. This is a B+ tree: a balanced, multi-way search tree where each internal node is sized to exactly one disk block, and where all the actual data pointers live in the leaves, which are additionally chained together in sorted order (a detail that matters for range queries like BETWEEN and ORDER BY, covered below). Increasing the branching factor (the "fan-out") from 2 to a few hundred doesn't just shrink the tree a little — because tree height is a logarithm of the fan-out, multiplying the fan-out by 100 divides the height by roughly log(100), collapsing 24 levels down to 3 or 4.

Worked example: computing the actual I/O savings

Build the index on pnr_number. Assume PNR is stored as an 8-byte integer and each leaf/internal entry needs one 8-byte pointer alongside it (a row pointer in the leaves, a child-block pointer in internal nodes). That's 16 bytes per entry.

index entries per block (fan-out) = floor(8192 / 16) = 512

leaf blocks needed  = ceil(10,000,000 / 512) = 19,532
level-2 blocks       = ceil(19,532 / 512)     = 39
level-1 (root) blocks = ceil(39 / 512)         = 1

Three levels — root, one internal level, and the leaves — are enough to index all 10 million PNRs, because 512³ = 134,217,728, comfortably above 10,000,000, while 512² = 262,144 is not. Finding a given PNR means: read the root block (1 I/O), find which of its up-to-512 key ranges contains the target and follow that pointer to read the correct level-2 block (1 I/O), find which of its ranges contains the target and read the correct leaf block (1 I/O). The leaf entry holds the row pointer (RID — a block number plus a slot number) for the actual row, so the engine performs one more I/O to fetch the row itself from the heap file.

total I/O for indexed lookup = 3 (tree traversal) + 1 (heap fetch) = 4 block reads

Compare that to the roughly 125,000 block reads for the average full scan, or 250,000 for the worst case:

125,000 / 4 = 31,250   (average-case speedup)
250,000 / 4 = 62,500   (worst-case speedup)

Four block reads instead of six figures is the entire reason IRCTC, a UPI transaction log, or a Swiggy orders table can answer a point lookup on a table with tens of millions of rows in single-digit milliseconds. The diagram below shows exactly this traversal.

Creating and reading the index

The SQL to build this index is a single statement, and because PNR values are unique, declaring it UNIQUE lets the query planner recognise that at most one row can ever match:

CREATE UNIQUE INDEX idx_bookings_pnr
  ON bookings(pnr_number);

Running EXPLAIN before and after shows the planner switching strategies. Before the index exists:

EXPLAIN SELECT * FROM bookings WHERE pnr_number = 4521789034;

id | select_type | table    | type | possible_keys | key  | rows     | Extra
1  | SIMPLE      | bookings | ALL  | NULL           | NULL | 10000000 | Using where

type: ALL means a full table scan; rows: 10000000 is the planner's estimate of how many rows it must examine. After the index exists:

EXPLAIN SELECT * FROM bookings WHERE pnr_number = 4521789034;

id | select_type | table    | type  | possible_keys    | key              | rows | Extra
1  | SIMPLE      | bookings | const | idx_bookings_pnr | idx_bookings_pnr | 1    | NULL

type: const is MySQL's label for the fastest possible access path — an equality match on a unique index, resolved in effectively constant time regardless of table size, exactly as the 4-I/O calculation above predicts. This is the same idea as hashing or binary search giving O(1) or O(log n) lookup instead of O(n) — except the constraint being optimized against is disk I/O count, not comparison count.

Composite indexes and the leftmost-prefix rule

A ticketing platform also needs to answer "show all bookings for train 12951 on 2026-08-22." A composite index covers this:

CREATE INDEX idx_train_date
  ON bookings(train_number, journey_date);

The B+ tree built from this definition sorts entries first by train_number, and only within equal train_number values by journey_date — exactly like sorting a list of (surname, first name) pairs. This has a direct consequence: a query filtering on train_number = 12951 alone, or on both columns, can use this index efficiently, because both cases correspond to a contiguous range in the sorted order. A query filtering on journey_date = '2026-08-22' alone cannot use this index efficiently, because rows for that date are scattered across every train_number range in the tree — there is no contiguous slice to jump to. This is the leftmost-prefix rule: a composite index on (A, B) accelerates lookups on A, and on (A, B) together, but not on B alone. Students who need date-only lookups fast must add a separate index on journey_date.

Common misconception: "adding an index always makes the query faster"

It doesn't, and the reason is worth deriving rather than memorizing. Consider a status column with three roughly equally frequent values: CONFIRMED, WAITLIST, CANCELLED. A query like WHERE status = 'CANCELLED' matches about 10,000,000 / 3 ≈ 3,333,333 rows — this is called low selectivity (selectivity = distinct values / total rows = 1/3 here, a large fraction).

Suppose an index on status exists anyway. The index itself is cheap to walk, but every matching entry still needs a separate fetch from the heap file to retrieve the full row (unless the index happens to be clustered — covered next). The question is how many distinct heap blocks those 3,333,333 matching rows are spread across. With 40 rows per block and roughly 1-in-3 rows matching, the expected number of matches in any given block is 40 × (1/3) ≈ 13.3, and the probability that a block has zero matches is (2/3)⁴⁰ ≈ 9 × 10⁻⁸ — essentially zero. In other words, virtually all 250,000 blocks contain at least one CANCELLED row, so satisfying this query touches nearly every block in the table regardless of whether the index is used. The only difference is that the index forces those 250,000-ish block visits to happen as scattered, unordered fetches driven by row pointers — random I/O — instead of the sequential, predictable block-after-block sweep of a plain full scan. Random I/O has meaningfully higher overhead per read than sequential I/O on essentially all storage hardware, spinning disks especially but SSDs too. So the query planner correctly ignores the status index and does a full scan instead — you can verify this by checking that EXPLAIN reports type: ALL even with the index present, once possible_keys lists it but key shows NULL or a different choice.

The general rule this derivation supports: an index earns its keep only on columns with high selectivity relative to the query pattern — few enough matching rows that jumping straight to them beats sweeping past everything. A rough working threshold used by real planners is somewhere around 5–10% of the table; well above that, expect the optimizer to prefer a full scan even with an index sitting right there. This is also why every additional index has a cost that's easy to forget: each INSERT, UPDATE, or DELETE must also update every index on the table, turning an O(1) heap append into an O(log_b n) tree update per index — multiplied across however many indexes exist. A table that is written to far more often than it is read from a given column should often not be indexed on that column at all.

Clustered vs. non-clustered: removing the extra hop

The 4-I/O count above included one final hop from leaf entry to heap row, because the index was non-clustered — the leaves store pointers to rows that live elsewhere, in whatever order they were inserted. A clustered index instead stores the actual row data in the leaves themselves, in indexed-key order — the table's heap file and the index are the same physical structure. Primary keys in engines like MySQL's InnoDB are clustered by default. For our PNR example, a clustered index would cut the lookup from 4 I/Os to 3, since the leaf visit is itself the final answer. The trade-off: a table can have only one clustered index (there's only one physical row order), while it can have many non-clustered indexes, and inserting into the middle of a clustered index's key range can require shifting existing rows to keep them sorted — which is precisely why auto-incrementing IDs are popular as clustered primary keys: new rows always append at the end.

Active recall

Attempt these before reading the answers.

1. A table has 2,000,000 rows of 100 bytes each, stored in 4096-byte blocks. Compute rows per block, total blocks, and the average number of block reads for a full-scan point lookup.
2. You build a B+ tree index on this table's primary key, where each index entry (key + pointer) is 20 bytes. Compute the fan-out and the height of the tree (i.e., how many index-block reads a lookup needs before reaching the heap).
3. A composite index exists on (train_number, journey_date). Explain, in terms of the tree's sort order, why WHERE journey_date = '2026-08-22' cannot use this index efficiently but WHERE train_number = 12951 AND journey_date = '2026-08-22' can.
4. A column has 50 distinct values spread evenly across 5,000,000 rows. Compute its selectivity and state, with reasoning, whether an index on it is likely to help.
5. Explain, using the fan-out numbers from this chapter, why database indexes use B+ trees with fan-out in the hundreds rather than binary search trees with fan-out 2.
6. A bookings table takes 1,000 INSERTs per second and has 5 non-clustered indexes. Explain what happens to write throughput as more indexes are added, and why.

Answers

1. rows/block = floor(4096/100) = 40. total blocks = 2,000,000 / 40 = 50,000. Average full-scan point lookup ≈ 50,000 / 2 = 25,000 block reads (worst case, or for a query that must check every row such as an aggregate: 50,000).

2. fan-out = floor(4096/20) = 204. Height check: 204² = 41,616 (too small to hold 2,000,000 keys at 2 levels), 204³ = 8,489,664 (enough). So 3 levels are needed — root, one internal level, leaves — meaning 3 index-block reads plus 1 heap fetch (if non-clustered) = 4 total, the same shape as the PNR example despite different raw numbers.

3. The tree sorts entries first by train_number, then by journey_date within each equal train_number — the same logic as sorting (surname, first-name) pairs. Rows for one specific journey_date are not contiguous in this order; they're scattered across every train_number's sub-range, so there is no single range the tree can jump to — the engine would have to scan the whole index anyway, no better than a full table scan. But train_number = 12951 (with or without the date) selects one contiguous block of the sorted order, which the tree can navigate to directly. This is the leftmost-prefix rule.

4. Selectivity = 1/50 = 2% of rows per value, i.e. about 5,000,000/50 = 100,000 matching rows per value. Since 2% is comfortably below the roughly 5–10% rule-of-thumb threshold used earlier, an index on this column is likely to help — especially compared to the earlier 1/3-selectivity status example, where the fraction of matching rows was over 15 times larger and made the index counterproductive. The exact benefit still depends on how clustered the matching rows are on disk, which is why real systems also examine table statistics, not selectivity alone.

5. Fan-out determines how quickly tree height shrinks with more keys, and each level costs one disk I/O, not one cheap in-memory comparison. A binary tree (fan-out 2) over 10,000,000 keys needs ⌈log₂(10,000,000)⌉ = 24 levels, i.e. 24 disk I/Os to reach a leaf. A B+ tree with fan-out 512, as derived earlier, needs only 3. In-memory comparisons are essentially free, so a BST's extra 21 levels of comparisons cost nothing; but each of those levels living in a separate disk block turns into 21 extra expensive disk seeks — which is the entire cost the index exists to avoid. High fan-out packs each disk read with as much useful branching as a block can physically hold.

6. Every INSERT now has to write not just one heap row but also add an entry to all 5 index trees, each requiring its own tree traversal (and occasionally splitting a full node, which cascades into rewriting the parent). Write throughput drops roughly in proportion to the number of indexes maintained, since each is a separate O(log_b n) update on a separate structure, plus extra disk writes. This is the direct cost side of indexing: every index that speeds up a read is simultaneously a tax on every write, which is why production schemas index deliberately — usually on primary keys, foreign keys, and columns that appear often in WHERE/JOIN/ORDER BY clauses — rather than indexing every column by default.

Think About It

Think about this: How would you explain database indexing: optimize query performance 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.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind database indexing: optimize query performance, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.