Indexing — B-tree index, hash index, full-text: Worked examples

Before we start, five words we will use a hundred times, defined from zero:

The scenario matrix

Every query this topic can throw at you falls into one of these cells. Each worked example below is tagged with the cell it covers.

#	Cell (scenario class)	Best index	Covered by
C1	Exact equality `=`	Hash or B-tree	Ex 1
C2	Range `<`, `>`, `BETWEEN`	B-tree only	Ex 2
C3	Sorting `ORDER BY`	B-tree only	Ex 3
C4	Prefix `LIKE 'app%'`	B-tree	Ex 4
C5	Inside-word `LIKE '%pp%'` (degenerate for B-tree)	Full-text	Ex 5
C6	Composite `(a,b)` + leftmost-prefix trap	B-tree	Ex 6
C7	Zero / empty result (degenerate input)	any	Ex 7
C8	Limiting behaviour: $N \to$ huge, hash collisions	analysis	Ex 8
C9	Real-world word problem (choose the index)	reasoning	Ex 9
C10	Exam twist: " $O (1)$ beats $O (lo g N)$ so hash wins"	steel-man	Ex 10

The columns "sign/quadrant" of a trig problem become here "query shape" (equality / range / order / substring) and "input degeneracy" (empty table, empty result, collisions, huge $N$ ). We cover them all.

Worked example Ex 1 — Cell C1: exact equality lookup

Statement. Table users has $N = 1 0^{9}$ rows. There is a B-tree index on id with branching factor $m = 100$ . Query: WHERE id = 42. How many page reads with (a) no index, (b) the B-tree, (c) a hash index?

Forecast: guess the three numbers before reading. (Most people massively overestimate the B-tree.)

No index → full scan. Why this step? Without a sorted structure the DB must compare every row, reading every page. If each page holds ~100 rows, that is $1 0^{9} /100 = 1 0^{7}$ page reads. Why this step matters: this is the baseline disaster we are escaping.
B-tree height. Why this step? Each level of the tree multiplies reachable keys by $m$ , and each level is one page read. Height $h = ⌈ lo g_{m} N ⌉ = ⌈ lo g_{100} 1 0^{9} ⌉$ . Compute: $lo g_{100} 1 0^{9} = \frac{l o g _{10} 1 0 ^{9}}{l o g _{10} 100} = \frac{9}{2} = 4.5 \Rightarrow h = 5$ . So 5 page reads (fewer in practice — top levels sit in RAM). If we then need columns not in the index, add 1 table fetch to reach the row.
Hash index. Why this step? A hash computes bucket = hash(42) mod B in the CPU (free) and jumps to exactly one bucket = 1 page read. This is $O (1)$ .

Verify: $1 0^{7}$ (scan) $≫ 5$ (B-tree) $> 1$ (hash). Sanity check on step 2: $10 0^{5} = 1 0^{10} \geq 1 0^{9}$ ✓ — five levels of branching-100 comfortably hold a billion keys. Both indexes are effectively instant; the scan is $2 \times 1 0^{6}$ times worse than the B-tree.

Worked example Ex 2 — Cell C2: range query

Statement. WHERE age BETWEEN 20 AND 30 on a B-tree index over age. Suppose $k = 5000$ matching rows spread across leaf pages holding 200 keys each. Estimate the page reads. Then: could a hash index do this?

Forecast: will it be closer to 5 or to 5000?

Find the start key age = 20. Why this step? A range still begins with a descent — we walk down the tree to the leaf where 20 lives: $h = lo g_{m} N \approx 5$ reads.
Walk the linked leaf list. Why this step? B+tree leaves are chained in sorted order (parent note §1). Once at 20 we simply follow the chain until we pass 30. This is the geometry of the figure below — a horizontal walk, not another descent. Number of leaf pages touched $= ⌈ k /200 ⌉ = ⌈ 5000/200 ⌉ = 25$ .
Total $= 5 + 25 = 30$ page reads. Cost model: $O (lo g_{m} N + k / page)$ . (If the query needs non-indexed columns, add up to $k$ table fetches — one per matching row; if it only needs age, this is a free index-only scan.)
Hash? Why this step? Hashing scatters 20…30 into unrelated buckets — there is no chain to walk. The only way to answer a range with a hash index is to inspect every bucket = full scan. Hash cannot do ranges.

Figure 1: descend once (orange, ~5 reads) to the leaf holding 20, then walk the sorted leaf chain (magenta, 25 leaf pages) until we pass 30; grey leaves outside 20–30 are never read.

Verify: $5 + 25 = 30$ ✓. Compare full scan $1 0^{7}$ : the B-tree range is $\approx 3.3 \times 1 0^{5}$ times cheaper. And $30 ≪ 5000$ , so the answer is much closer to 5 than 5000 — because the "walk" is measured in pages, not rows.

Worked example Ex 3 — Cell C3: ORDER BY for free

Statement. SELECT ... ORDER BY created_at LIMIT 100. There is a B-tree on created_at. How much sorting work? Compare to no index.

Forecast: does the DB run a sort algorithm here?

No index. Why this step? To order $N$ rows the DB must run a sort, costing $O (N lo g N)$ comparisons plus reading all $N$ rows off disk. For $N = 1 0^{9}$ that is billions of operations.
With the B-tree. Why this step? The leaves are already in sorted order (that is what "sorted structure" means). ORDER BY created_at = just read leaves left-to-right. For LIMIT 100 with ~200 keys/leaf, we touch $⌈ 100/200 ⌉ = 1$ leaf page after a 5-read descent = 6 page reads, zero sorting (plus up to 100 table fetches if columns beyond created_at are selected).

Verify: $5 + 1 = 6$ page reads, and the sort cost drops from $O (N lo g N)$ to $0$ — the index pre-sorted for us. See also Query Optimization, which detects exactly this "index provides ordering" opportunity.

Worked example Ex 4 — Cell C4: prefix match

LIKE 'app%' Statement. WHERE name LIKE 'app%' on a B-tree over name. Does the index help? How?

Forecast: yes or no — and why does the position of the wildcard matter?

Read the pattern as a range. Why this step? app% means "starts with app", i.e. every string $\geq$ "app" and $<$ "apq" (bump the last letter). We have a known prefix, so we know exactly where to start the descent.
Descend to "app", then walk leaves until we exceed "apq". Why this step? This is identical to Ex 2's range walk — a leading known prefix converts LIKE into a range. Cost $O (lo g_{m} N + k / page)$ .

Figure 2: the fixed left edge "app" (orange arrow) is where the descent lands; magenta entries app, apple, apply are inside the range and get walked, grey ones outside are skipped. A leading wildcard %pp% would have no such edge.

Verify (contrast with Ex 5): the index works only because there is a fixed left edge "app". Remove that edge and everything breaks — that is the next example.

Worked example Ex 5 — Cell C5 (degenerate for B-tree): inside-word

LIKE '%pp%' Statement. WHERE name LIKE '%pp%' (leading wildcard) and WHERE body CONTAINS 'database'. What does the B-tree do, and what should we use?

Forecast: with an index on name, is '%pp%' fast?

Leading wildcard = no known prefix. Why this step? The match can begin at any position (apple, zipper, hippo…). The tree's whole power is "start at a known left edge and walk." With no edge, it cannot pick a starting leaf → full scan $O (N)$ . This is the degenerate case for a B-tree.
Use a full-text / inverted index. Why this step? An inverted index maps word → documents. Build it via tokenization → stemming → stop-word removal (parent §3). Then CONTAINS 'database' is a single lookup of the postings list.
Worked inverted lookup. Docs after preprocessing: $cat \to {D_{1}}, sat \to {D_{1}, D_{2}}, dog \to {D_{2}}$ Query sat AND dog $= {D_{1}, D_{2}} \cap {D_{2}} = {D_{2}}$ . Why this step? Boolean text search = set intersection on pre-sorted postings, which is linear in the list sizes, not in $N$ .

Verify: ${D_{1}, D_{2}} \cap {D_{2}} = {D_{2}}$ ✓ (checked in VERIFY). B-tree on '%pp%' = $1 0^{7}$ scan reads; full-text = a handful. See Hashing and the inverted-index idea are cousins: both trade order for direct lookup.

Worked example Ex 6 — Cell C6: composite index & the leftmost-prefix trap

Statement. Composite B-tree on (last_name, first_name). Which of these use the index efficiently? (a) WHERE last_name = 'Khan' (b) WHERE last_name = 'Khan' AND first_name = 'Sana' (c) WHERE first_name = 'Sana'

Forecast: which one silently falls back to a full scan?

Picture the sort order. Why this step? A composite index is sorted by last_name first, then first_name — exactly like a phone book (last-then-first). See the figure.
(a) last_name = 'Khan' → we know the first sort key → descend to Khan, walk that block. Index used, $O (lo g N + k)$ .
(b) both keys → even more precise: descend to Khan, then within it to Sana. Best case, fully served — and since both columns are in the index, this can be an index-only scan.
(c) first_name alone → Why this step? The Sanas are scattered across every last-name block (like every "Sana" spread through the whole phone book). With no last_name to anchor the left edge, there is no start point → full scan. This is the leftmost-prefix rule.

Figure 3: entries sorted by last name first. Case (a): the Khan block is one contiguous violet run — easy. Case (c): first_name = 'Sana' (magenta arrows) is scattered across unrelated last-name blocks, so there is no single starting point → scan.

Verify: index helps (a) ✓ and (b) ✓; fails (c) ✗. See Clustered vs Non-clustered Index for how the physical layout amplifies this.

Worked example Ex 7 — Cell C7: empty table & empty result (degenerate inputs)

Statement. Two edge cases: (a) the table has $N = 0$ rows; (b) WHERE id = 999 where no such row exists but the index is present.

Forecast: does an empty result cost a scan?

(a) Empty table. Why this step? Height $h = ⌈ lo g_{m} N ⌉$ is undefined at $N = 0$ , so we do not use the formula here. Convention: an empty index is a single empty root page. Any lookup reads exactly that 1 page, finds it empty, and returns. So we count it as 1 read — not a scan.
(b) No matching row. Why this step? A crucial point: an index lookup that finds nothing still costs only the descent. We walk down to where 999 would be, see it's absent, and stop. Cost = $h = lo g_{m} N \approx 5$ reads — the same as a hit, and with no matching row there are zero table fetches. Contrast: a full scan to prove absence must read all $1 0^{7}$ pages, because "not found" is only certain after checking every row.

Verify: empty result via index $\approx 5$ reads; empty result via scan $= 1 0^{7}$ reads. The index's advantage is largest precisely when the answer is empty — an underappreciated case.

Worked example Ex 8 — Cell C8: limiting behaviour — huge

$N$ and hash collisions Statement. (a) As $N$ grows $1 0^{6} \to 1 0^{9} \to 1 0^{12}$ ( $m = 100$ ), how does B-tree height grow? (b) A hash index has $B = 1000$ buckets but $N = 1 0^{6}$ keys. What is the average bucket length, and what does a lookup now cost?

Forecast: does the B-tree height double when $N$ goes up 1000×?

(a) Height vs $N$ . Why this step? $h = lo g_{100} N$ , so: $lo g_{100} 1 0^{6} = 3, lo g_{100} 1 0^{9} = 4.5 \to 5, lo g_{100} 1 0^{12} = 6$ A million-fold jump ( $1 0^{6} \to 1 0^{12}$ ) only doubles the height (3 → 6). This is the "wide and shallow" magic — logarithms crush growth.
(b) Hash overload. Why this step? Average bucket length (the load factor) $= N / B = 1 0^{6} /1000 = 1000$ keys per bucket. Disk-read view: if a bucket still fits in ~one page, the lookup is still ~1 page read — but now the DB must scan 1000 keys inside that page with CPU comparisons ( $O (N / B)$ comparisons, not $O (N / B)$ reads). Only when a bucket overflows several pages do the disk reads themselves start to climb. So the $O (1)$ promise degrades in CPU work first, and in page reads only under severe overload.
Fix. Why this step? Grow $B$ with $N$ (rehash) so the load factor $N / B$ stays $\approx 1$ , restoring $O (1)$ on both axes. See Hashing.

Verify: $lo g_{100} 1 0^{12} = 6$ and $lo g_{100} 1 0^{6} = 3$ , so height only doubles for a $1 0^{6} \times$ data increase ✓. Load factor $1 0^{6} /1000 = 1000$ ✓ (that many comparisons per lookup, not that many disk reads).

Worked example Ex 9 — Cell C9: real-world word problem

Statement. You design a session store: table sessions(session_id, user_id, created_at, data). Queries are: 99% WHERE session_id = ? (exact), plus a nightly WHERE created_at < now() - 24h cleanup. Which index(es)?

Forecast: one index or two? Same type?

The hot path: exact session_id. Why this step? Only equality, no ranges, no sorting → hash index gives $O (1)$ , beating the B-tree's ~5 reads on the 99% workload.
The cleanup: created_at < X. Why this step? This is a range. A hash can't do ranges (Ex 2), so we add a B-tree on created_at so the nightly job walks the leaf chain instead of scanning. The cleanup only needs the row's key to delete it, so it can stay index-only until the delete itself.
Decision. Why this step? Two indexes, two types: hash on session_id, B-tree on created_at. Justify writes: sessions are write-heavy, so we keep indexes minimal (parent's "index only what you query") — no index on data or user_id, which are never filtered.

Verify: hot query $O (1)$ via hash; cleanup $O (lo g N + k)$ via B-tree; $2$ indexes total; columns data/user_id left unindexed since never filtered. Matches the mnemonic B for Between, H for Hit-exact.

Worked example Ex 10 — Cell C10: the exam twist (steel-manned)

Statement. Exam claim: "Big-O says $O (1) < O (lo g N)$ , therefore a hash index is strictly better than a B-tree. Always use hash." Refute with numbers and cases.

Forecast: where does this argument break?

The constant is tiny. Why this step? For $N = 1 0^{9}, m = 100$ , $lo g_{m} N = 5$ . Big-O hides that "logarithmic" here means the number 5. The hash saves at most $5 - 1 = 4$ reads on equality — often 0 after caching.
Coverage collapse. Why this step? A hash serves only equality. Ranges (Ex 2), ORDER BY (Ex 3), prefix LIKE (Ex 4) all fall back to a full scan of $1 0^{7}$ pages on a hash. So on a range query the hash costs $1 0^{7}$ reads while the B-tree costs $\approx 30$ (Ex 2) — the hash is worse by a factor of $1 0^{7} /30 \approx 3.3 \times 1 0^{5}$ .
Verdict. Why this step? Big-O compares one operation's growth, not which operations are supported. The hash's $4$ -read equality edge is dwarfed by its $3.3 \times 1 0^{5} \times$ penalty the moment a range appears. B-tree is the safe default; hash only for a pure-equality workload (Ex 9's hot path).

Verify: equality saving $5 - 1 = 4$ reads (small); range penalty $1 0^{7} /30 \approx 3.3 \times 1 0^{5}$ (huge). Since real workloads contain ranges/sorts, "always use hash" is false. ✓

Recall Scenario checklist — can you place each in a matrix cell?

Query is col = value and nothing else ::: Cell C1 — hash ( $O (1)$ ) or B-tree. Query is BETWEEN / < / > ::: Cell C2 — B-tree only (hash can't walk ranges). Query is ORDER BY col ::: Cell C3 — B-tree gives sorted leaves free. Query is LIKE 'pre%' ::: Cell C4 — B-tree via known-prefix range. Query is LIKE '%mid%' ::: Cell C5 — B-tree degenerates to scan; use full-text. Query filters b alone on index (a,b) ::: Cell C6 — leftmost-prefix fails; scan. Query returns nothing / table empty ::: Cell C7 — index still just $lo g_{m} N$ , no scan. $N$ explodes or buckets overflow ::: Cell C8 — B-tree height $\sim lo g N$ ; hash degrades to $N / B$ comparisons. Query needs only indexed columns ::: index-only scan, no table fetches; otherwise add one fetch per matching row.