Indexing basics
45 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A student table has two million rows and the login query takes seconds. "Why is it slow, and what would you add?" is one of the most common database questions, and the interviewer wants the reason, not just the word "index".
Why indexes speed up reads and slow down writes
An index is a separate, sorted data structure that lets the database find rows by a column's value without reading the whole table, like the index at the back of a textbook that sends you straight to page 214.
Searching one email in a million rows can mean checking every row. The program counts the comparisons for a full scan and for an index search.
Example 1 · Full scan vs index search: comparisons counted
def scan_comparisons(rows, target): for count, row in enumerate(rows, start=1): if row == target: return count return len(rows)
def index_comparisons(sorted_rows, target): # Hand-written binary search: interviews expect you to be able to write it. lo, hi, count = 0, len(sorted_rows) - 1, 0 while lo <= hi: mid = (lo + hi) // 2 count += 1 if sorted_rows[mid] == target: break if sorted_rows[mid] < target: lo = mid + 1 else: hi = mid - 1 return count
for n in (1_000, 1_000_000): ids = list(range(1, n + 1)) # roll numbers 1..n target = n # worst case: the last row print(f"{n:,} rows: scan {scan_comparisons(ids, target):,} comparisons, " f"index {index_comparisons(ids, target)} comparisons")1,000 rows: scan 1,000 comparisons, index 10 comparisons 1,000,000 rows: scan 1,000,000 comparisons, index 20 comparisons
What this code does
- A scan may have to check every row; a search on sorted data halves the range each step, so it needs about log₂ n steps.
- A real B+ tree is even shorter than binary search because each node holds hundreds of keys; the point is the jump from n to log n.
Without an index the database does a full table scan: it checks every row. With an index on email it searches a sorted structure in about log(n) steps, so a million rows need roughly 20 comparisons instead of a million. Revise: Table scan vs index (opens in a new tab) and The cost of indexes (opens in a new tab).
The cost comes on writes: every INSERT, DELETE and UPDATE of an indexed column must also update each index, and every index takes disk space and memory. Use this checklist:
- Faster: WHERE lookups, JOIN conditions, ORDER BY and GROUP BY on indexed columns, MIN/MAX.
- Slower: INSERT, DELETE and UPDATE of indexed columns (each index is maintained).
- Costly: storage and buffer-pool memory for each index.
- Rule of thumb: index selective columns used in frequent queries.
Predict the output
Reads and writes
Read the situation, then pick the answer you would say aloud.
Round 1 of 2
About how many comparisons does the index search need?
Clustered vs non-clustered indexes
A clustered index decides the physical order of the table's rows: the rows are stored in the index's order, so a table can have only one. In MySQL InnoDB the primary key is the clustered index and its leaf pages hold the full rows.
InnoDB stores whole rows inside the primary key's index, while a secondary index stores only the key needed to find them. The program simulates both lookups.
Clustered (PRIMARY KEY roll_no): leaf pages = full rows in roll_no orderSecondary (idx_email): leaf = (email, roll_no) -> then clustered lookupCovering: SELECT roll_no FROM student WHERE email = ? -> index onlyExample 2 · Clustered and secondary index lookups, simulated
# Clustered index: primary key -> full row, kept in key order.inserted = { 103: ("Rahul", "rahul@c.edu", "CSE"), 101: ("Priya", "priya@c.edu", "ECE"), 102: ("Arun", "arun@c.edu", "CSE"),}clustered = dict(sorted(inserted.items()))
# Secondary index: email -> primary key (not the row).by_email = {row[1]: pk for pk, row in clustered.items()}
print("Rows in clustered (PK) order:")for pk, (name, email, branch) in clustered.items(): print(f" {pk} | {name:<5} | {email:<11} | {branch}")
email = "priya@c.edu"pk = by_email[email]name, _, branch = clustered[pk]print(f"Secondary index: {email} -> PK {pk}")print(f"Clustered lookup: {pk} | {name} | {email} | {branch}") # step 2print(f"Covering query (only PK needed): {pk}, no second step")Rows in clustered (PK) order: 101 | Priya | priya@c.edu | ECE 102 | Arun | arun@c.edu | CSE 103 | Rahul | rahul@c.edu | CSE Secondary index: priya@c.edu -> PK 101 Clustered lookup: 101 | Priya | priya@c.edu | ECE Covering query (only PK needed): 101, no second step
What this code does
- The rows were inserted as 103, 101, 102 but are stored in primary-key order, as InnoDB does with its clustered index.
- A lookup by email takes two steps: the secondary index gives the primary key, and the clustered index gives the row. If the query needs only the email and the key, the first step already answers it (a covering index).
A non-clustered (secondary) index is a separate structure whose entries point to the rows, and a table can have many. In InnoDB its leaf holds the indexed value plus the primary key, so a lookup by email finds the primary key first and then looks the row up in the clustered index: a bookmark lookup. If the index already holds every column the query needs, it is a covering index and the second step is skipped. Revise: Creating indexes (opens in a new tab).
Order of execution
A lookup by email in InnoDB
Tap the steps in the order InnoDB performs them.
B-tree and B+ tree at interview level
A B+ tree is a balanced search tree in which every node is a disk page holding many keys, internal nodes only route, and all row pointers sit in the linked leaf level. It is the structure behind most database indexes.
A node with room for 100 keys has about 100 children, so the tree is wide and very short. The program computes how many levels a B+ tree needs for a given number of rows.
Example 3 · How tall is a B+ tree?
import math
def levels(rows, fanout): count, reach = 1, fanout # rows reachable with this many levels while reach < rows: reach *= fanout count += 1 return count
fanout = 100 # keys (children) per 16 KB page, roughfor rows in (50, 10_000, 1_000_000, 100_000_000): lv = levels(rows, fanout) print(f"{rows:>13,} rows -> {lv} {'level' if lv == 1 else 'levels'} (page reads per lookup)")print("Binary search on 100,000,000 sorted keys: ~" + str(math.ceil(math.log2(100_000_000))), "steps") 50 rows -> 1 level (page reads per lookup)
10,000 rows -> 2 levels (page reads per lookup)
1,000,000 rows -> 3 levels (page reads per lookup)
100,000,000 rows -> 4 levels (page reads per lookup)
Binary search on 100,000,000 sorted keys: ~27 stepsWhat this code does
- Each extra level multiplies the reach by the fanout, so even 100 million rows need only 4 page reads, and the top levels usually stay cached in memory.
- The fanout of 100 is a round number for the sum; real fanout depends on key size and page size (InnoDB pages are 16 KB by default).
Three levels can index about a million rows and four levels about a hundred million. In a B-tree, keys and data pointers can sit in any node; in a B+ tree the leaves are linked in a list, which makes range queries such as cgpa BETWEEN 8 AND 9 fast: find the first leaf, then walk the linked leaves. Hash indexes answer equality lookups in O(1) on average but cannot do ranges or ordering.
Predict the output
Pick the index structure
Read the need, then pick the answer.
Round 1 of 2
Which query gains most from the linked leaves of a B+ tree?
When an index is not used
EXPLAIN is a MySQL statement that shows the plan the query optimiser chose for a query: which index it uses (key), how many rows it expects to read (rows) and whether it scans the whole table (type: ALL).
Having an index does not mean MySQL uses it. EXPLAIN shows the plan for four queries on a 10,000-row table, and two of them cannot use their index.
Example 4 · EXPLAIN: when MySQL uses the index and when it does not
Runs in: MySQL 8
CREATE TABLE student ( roll_no INT PRIMARY KEY, name VARCHAR(40), email VARCHAR(60), branch CHAR(3), cgpa DECIMAL(4,2), KEY idx_email (email), KEY idx_branch_cgpa (branch, cgpa));SET SESSION cte_max_recursion_depth = 20000;INSERT INTO studentWITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i + 1 FROM n WHERE i < 10000)SELECT i, CONCAT('Student', i), CONCAT('s', i, '@college.edu'), ELT(1 + i % 5, 'CSE', 'ECE', 'EEE', 'MEC', 'CIV'), 5 + (i % 500) / 100 FROM n;EXPLAIN SELECT name FROM student WHERE email = 's42@college.edu';EXPLAIN SELECT name FROM student WHERE UPPER(email) = 'S42@COLLEGE.EDU';EXPLAIN SELECT name FROM student WHERE cgpa > 9.5;EXPLAIN SELECT name FROM student WHERE branch = 'CSE' AND cgpa > 9.5+----+-------------+---------+------------+------+---------------+-----------+---------+-------+------+----------+-------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+---------+------------+------+---------------+-----------+---------+-------+------+----------+-------+ | 1 | SIMPLE | student | NULL | ref | idx_email | idx_email | 243 | const | 1 | 100.00 | NULL | +----+-------------+---------+------------+------+---------------+-----------+---------+-------+------+----------+-------+ +----+-------------+---------+------------+------+---------------+------+---------+------+-------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+---------+------------+------+---------------+------+---------+------+-------+----------+-------------+ | 1 | SIMPLE | student | NULL | ALL | NULL | NULL | NULL | NULL | 10000 | 100.00 | Using where | +----+-------------+---------+------------+------+---------------+------+---------+------+-------+----------+-------------+ +----+-------------+---------+------------+------+---------------+------+---------+------+-------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+---------+------------+------+---------------+------+---------+------+-------+----------+-------------+ | 1 | SIMPLE | student | NULL | ALL | NULL | NULL | NULL | NULL | 10000 | 33.33 | Using where | +----+-------------+---------+------------+------+---------------+------+---------+------+-------+----------+-------------+ +----+-------------+---------+------------+-------+-----------------+-----------------+---------+------+------+----------+-----------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+---------+------------+-------+-----------------+-----------------+---------+------+------+----------+-----------------------+ | 1 | SIMPLE | student | NULL | range | idx_branch_cgpa | idx_branch_cgpa | 16 | NULL | 180 | 100.00 | Using index condition | +----+-------------+---------+------------+-------+-----------------+-----------------+---------+------+------+----------+-----------------------+
What this code does
type refwithkey idx_emailmeans the index is used (about 1 row read);type ALLwithkey NULLmeans a full scan of all 10,000 rows. Wrapping email inUPPER()turned the index off.- The composite index (branch, cgpa) is used when the query gives branch (
type range), but not for cgpa alone, because cgpa is not its leftmost column. Row estimates can differ on your machine.
The query optimiser estimates costs and picks the cheapest plan. These are the usual reasons an index is skipped, and "why is my query slow even with an index?" is a favourite question:
- A function or calculation on the column:
WHERE UPPER(email) = ...orWHERE salary * 12 > .... - A leading wildcard:
LIKE '%42@college.edu'(butLIKE 's42%'can use the index). - Composite index without its leftmost column: an index on (branch, cgpa) cannot serve
WHERE cgpa > 9.5alone. - Low selectivity or a small table: when most rows match, a full scan is cheaper; type mismatches (comparing a VARCHAR column to a number) can also block the index. Revise: When an index is not used (opens in a new tab) and Reading EXPLAIN (opens in a new tab).
Find the bug
Which query skips the index?
Each list has one condition that cannot use the index. Tap it.
There is an index on email.
Round 1 of 3Interview questions with model answers
A common written-test question gives the block size, key size and pointer size and asks for the order and the height of a B+ tree. The program works one such numerical.
Example 5 · B+ tree numerical: order and height
block, key, pointer = 4096, 8, 8# Internal node of order p holds p pointers and p - 1 keys: p*8 + (p-1)*8 <= 4096p = (block + key) // (key + pointer)print("Max children per internal node (order p):", p)
records = 10_000_000per_leaf = block // (key + pointer) # (key, record pointer) pairs per leafleaves = -(-records // per_leaf) # ceiling divisionheight, nodes = 1, leaveswhile nodes > 1: nodes = -(-nodes // p) height += 1print(f"Entries per leaf: {per_leaf}, leaves needed: {leaves}")print(f"Levels for {records} records (leaves included): {height}")Max children per internal node (order p): 256 Entries per leaf: 256, leaves needed: 39063 Levels for 10000000 records (leaves included): 3
What this code does
- Order comes from fitting p pointers and p − 1 keys into one block: 16p − 8 ≤ 4096 gives p = 256.
- With 256 entries per leaf, 10 million records need 39,063 leaves; 153 internal nodes point to those leaves, and one root points to the 153 nodes, so the tree has 3 levels in total, a typical written-test calculation.
Index questions usually come in this order: what an index is, why not index everything, clustered versus non-clustered, B+ tree versus B-tree, and a practical "this query is slow, what do you check?". Keep these four lines ready:
- Must know: index = sorted structure, O(log n) lookup instead of O(n) scan.
- Must know: one clustered index per table (InnoDB: the primary key).
- Must know: B+ tree = data in linked leaves, good for ranges.
- Must know: functions on columns, leading %, missing leftmost column → no index.
The Interview tab has the full bank, including composite indexes, covering indexes, cardinality and how indexes relate to primary and unique keys.
Next step
Check your understanding
12 quick questions