Indexing — B-tree index, hash index, full-text: Exercises

This is the practice-and-mastery companion to the Indexing topic note. Each problem is graded on Bloom's ladder: L1 Recognition → L2 Application → L3 Analysis → L4 Synthesis → L5 Mastery. Read the problem, try it, THEN open the collapsible solution. After each level there is a trap most students fall into and how to escape it.

Prerequisites you may want open in another tab: B+ Tree Data Structure, Hashing, Big-O Notation, Disk vs Memory I/O, Clustered vs Non-clustered Index, Query Optimization.

The one picture to hold in your head first

Before any exercise, fix the B+tree shape in your mind, because almost every solution below leans on it. Look at the figure: the tree is wide and shallow (each node = one disk page holding many keys), and — crucially — the bottom row of leaves is chained left-to-right in sorted order (the amber links). That chain is why ranges and ORDER BY are cheap: you descend once to the start key, then just walk along the chain. Keep the red "walk" arrow in mind whenever a solution says "walk the linked leaves."

Figure — Indexing — B-tree index, hash index, full-text

L1 — Recognition

These test whether you can name the right tool without any calculation.

Exercise 1.1

For each query, name the best index type (B-tree, hash, full-text, or n-gram/trigram):

#	Query
a	`WHERE session_id = 'abc123'` (only ever exact match)
b	`WHERE age BETWEEN 20 AND 30`
c	`WHERE body CONTAINS 'database'` (whole word)
d	`ORDER BY created_at`
e	`WHERE name LIKE '%son%'` (substring, mid-word)

Recall Solution 1.1

a → Hash. Only exact equality, no ranges, no sorting → the $O (1)$ bucket jump is ideal.
b → B-tree. A range needs order; B+tree leaves are sorted and linked, so you find 20 then walk to 30.
c → Full-text (inverted index). We are searching for a whole word inside a text column; the text is tokenized into words, so database as a token is found directly.
d → B-tree. Its leaves are already in sorted order, so ORDER BY is free — no extra sort step.
e → n-gram / trigram index (NOT full-text). %son% is an arbitrary substring buried mid-word. A full-text index tokenizes on whole words only, so it never indexes the fragment son inside Johnson — it won't help. A plain B-tree fails too (leading wildcard = no prefix). The right tool is an n-gram/trigram index (e.g. Postgres pg_trgm), which indexes every 3-letter fragment (son, ohn, …) so substring matches become index lookups.

Exercise 1.2

True or False, with a one-line reason each:

A B+tree is balanced (all leaves at the same depth).
A hash index can answer WHERE x > 5.
Every extra index makes writes faster.

Recall Solution 1.2

True. "Balanced" is the defining property: every leaf is the same distance from the root, so every lookup costs the same number of levels.
False. Hashing deliberately scatters keys to spread them evenly; adjacent values land in unrelated buckets, so there is no range to walk.
False. Every write (INSERT/UPDATE/DELETE) must also update each index, so more indexes make writes slower.

L2 — Application

Now you compute using the height formula $h = ⌈ lo g_{m} N ⌉$ from the topic note (each level = one disk read).

Exercise 2.1

A table has $N = 1 0^{6}$ rows. The B-tree branching factor is $m = 100$ . (a) How many levels (disk reads) does a point lookup cost? (b) If the top 2 levels are cached in RAM, how many actual disk reads remain?

Recall Solution 2.1

(a) WHAT/WHY: the height formula counts how many times we multiply by $m$ before covering all $N$ keys. $h = ⌈ lo g_{100} 1 0^{6} ⌉ = ⌈ \frac{l o g _{10} 1 0 ^{6}}{l o g _{10} 100} ⌉ = ⌈ \frac{6}{2} ⌉ = 3$ We used the change-of-base rule $lo g_{100} x = \frac{lo g _{10} x}{lo g _{10} 100}$ because we want base-100 but only "know" base-10 in our head. So 3 disk reads. (b) Cache removes the top 2 levels: $3 - 2 = 1$ actual disk read.

Exercise 2.2

Compare a full table scan vs a B-tree lookup for a point query WHERE id = 42 on $N = 1 0^{8}$ rows, $m = 100$ . (a) Scan cost in page reads (assume 200 rows per page). (b) B-tree cost in disk reads. (c) The speed-up factor (scan ÷ B-tree).

Recall Solution 2.2

(a) WHAT: a scan reads every page. Pages $= \frac{1 0 ^{8} rows}{200 rows/page} = 500, 000$ page reads. (b) $h = ⌈ lo g_{100} 1 0^{8} ⌉ = ⌈ 8/2 ⌉ = 4$ disk reads. (c) WHY compare: this shows why we tolerate the storage/write cost of an index. $\frac{500 , 000}{4} = 125, 000 \times faster$

Exercise 2.3

You have $N = 1 0^{9}$ rows. You upgrade nodes from $m = 10$ to $m = 1000$ (bigger disk pages). How do the tree heights compare? (This is exactly the trade shown in the figure at the top of the page — watch the tree get shorter as nodes fan out wider.)

Recall Solution 2.3

$h_{10} = ⌈ lo g_{10} 1 0^{9} ⌉ = 9$ . $h_{1000} = ⌈ lo g_{1000} 1 0^{9} ⌉ = ⌈ 9/3 ⌉ = 3$ . Bigger branching factor makes the tree wider and shallower: 9 reads down to 3. WHY it matters: fewer levels = fewer disk seeks, and disk seeks are the whole bottleneck.

L3 — Analysis

Now you diagnose why a plan is slow and which structure the optimizer must pick.

Exercise 3.1

A query SELECT * FROM users WHERE age > 25 ORDER BY age runs slowly. The DBA has a hash index on age. Explain in structural terms why the hash index cannot help, and what the query planner falls back to.

Recall Solution 3.1

A hash index computes bucket = hash(age) mod num_buckets. WHAT this does: it maps each age value to a scattered bucket so keys spread evenly. WHY that breaks this query:

age > 25 is a range — it needs to visit all values above 25. But hash(26), hash(27), hash(28) land in unrelated buckets, so there is no ordered chain to walk.
ORDER BY age needs values in order, which hashing has deliberately destroyed. So the planner ignores the hash index and does a full table scan ( $O (N)$ ), then a separate sort for ORDER BY. The correct fix is a B-tree index on age: find 25, then walk the sorted linked leaf chain (the amber links in the top figure) upward. Because that walk visits leaves already in ascending order, ORDER BY becomes free — no separate sort step needed.

Exercise 3.2

An index exists on the composite key (country, city). For each query, will it be used efficiently? Explain via the leftmost-prefix rule.

WHERE country = 'IN'
WHERE country = 'IN' AND city = 'Pune'
WHERE city = 'Pune'
WHERE city = 'Pune' AND country = 'IN'

Recall Solution 3.2

A composite B-tree is sorted by country first, then city within each country — exactly like a phone book sorted by last name, then first name.

Yes. country is the leftmost column → the tree can descend to all IN rows.
Yes. Full prefix (country, city) → most precise, jumps straight to IN+Pune.
No. city alone is not the leading column. Within the whole tree, Pune values are scattered across every country block, so there is no single start point → full scan.
Yes. Order of clauses in the WHERE text does not matter; the optimizer reorders them. What matters is that both leftmost columns (country, and then city) are present.

L4 — Synthesis

Now you design. Combine multiple ideas to build the right indexing scheme.

Exercise 4.1

Design indexes for a messaging app with these query patterns:

Log in by exact session_token (millions/sec, exact only).
Load a user's messages: WHERE user_id = ? ORDER BY sent_at DESC.
Search message bodies: WHERE body CONTAINS 'refund'.

For each, state the index type and justify. Note any write-cost concern.

Recall Solution 4.1

1. Hash index on session_token. Pure exact-match, no ranges, no ordering → $O (1)$ bucket jump beats a B-tree's ~5 levels. WHY not B-tree: we never sort or range on tokens, so B-tree's ordering is wasted overhead. 2. Composite B-tree on (user_id, sent_at). WHY: filtering on user_id uses the leftmost column, and because the tree is then sorted by sent_at within each user, ORDER BY sent_at is free. Recall the leaf chain from the top figure: we descend to this user's block, then walk the sorted linked leaves — for DESC we simply walk that chain backwards, so no separate sort is ever run. 3. Full-text / inverted index on body. WHY: searching for a whole word inside text needs word → document postings. A B-tree can't (it would need LIKE '%refund%' = full scan). Note: this works because refund is a whole word/token; an arbitrary substring would instead need an n-gram index. Write-cost concern: messages are write-heavy (every message = 1 insert). Each of the 3 indexes must be maintained per insert, and full-text indexing (tokenize + stem + update postings) is the most expensive. So index only these three columns — do not add indexes on rarely-filtered columns.

Exercise 4.2

You inherit a table with 8 indexes. Ingestion (bulk INSERT) is painfully slow, but reads are fast. Propose a concrete strategy and explain the trade-off in terms of the read/write cost model.

Recall Solution 4.2

Root cause: every INSERT must update all 8 indexes → write amplification. Reads are fast precisely because of these indexes; the two goals conflict. Strategy:

Audit usage. Drop indexes that no live query uses (check the planner / pg_stat_user_indexes). Unused indexes are pure write-cost with zero read benefit.
Merge overlapping composites. An index on (a) is redundant if (a, b) exists (leftmost-prefix rule already covers a alone) → drop (a).
For bulk loads: drop the indexes, load the data, rebuild indexes once at the end. Rebuilding once is far cheaper than maintaining them per-row across millions of inserts. Trade-off stated cleanly: indexes convert $O (N)$ read scans into $O (lo g N)$ but add a per-write maintenance cost. On a write-heavy path you deliberately trade some read speed back for write throughput.

L5 — Mastery

Full reasoning, edge cases, and defending a design under pressure.

Exercise 5.1

A junior engineer argues: "Hash is $O (1)$ and B-tree is $O (lo g N)$ , so we should replace ALL our B-tree indexes with hash indexes for speed." Refute this rigorously. Cover: (a) the actual size of $lo g_{m} N$ , (b) which query classes break, (c) hash collisions/degenerate case.

Recall Solution 5.1

(a) $lo g_{m} N$ is tiny. For $N = 1 0^{10}$ , $m = 100$ : $lo g_{100} 1 0^{10} = \frac{10}{2} = 5$ . So even at ten billion rows " $O (lo g N)$ " is about 5 disk reads, and the top levels cache in RAM → often 1–2 real hits. The asymptotic win of $O (1)$ over $O (5)$ is negligible in practice. (b) Query classes that BREAK on hash: ranges (<, >, BETWEEN), ORDER BY, prefix LIKE 'a%', and any join that relies on sorted order (merge join). These are most real queries. A hash index turns each of them into a full table scan. (c) Degenerate hash case: $O (1)$ is the average. With poor hash distribution or an adversarial key set, many keys collide into one bucket → that bucket degrades toward $O (N)$ (a long chain to scan). A balanced B-tree guarantees $O (lo g_{m} N)$ worst case — all leaves same depth, no degenerate path. Verdict: B-tree is the safe default; use hash only for pure-equality-only workloads (e.g. session lookup). "Constant beats log" ignores constants, breaks the majority of queries, and has no worst-case guarantee.

Exercise 5.2

Docs after preprocessing (stop-word removal + stemming):

D1: run fast cat
D2: run slow dog
D3: cat run fast

(a) Build the inverted index (word → sorted document list). (b) Evaluate run AND fast AND NOT dog by set operations, showing each intersection/difference.

Recall Solution 5.2

(a) Inverted index (postings kept as sorted document IDs so intersections are fast):

run  -> {D1, D2, D3}
fast -> {D1, D3}
cat  -> {D1, D3}
slow -> {D2}
dog  -> {D2}

(b) WHY set ops: Boolean text search = operations on sorted postings lists. Evaluate step by step (the figure below shows the two circles and their overlap):

run AND fast $= {D 1, D 2, D 3} \cap {D 1, D 3} = {D 1, D 3}$ .
AND NOT dog $= {D 1, D 3} ∖ {D 2} = {D 1, D 3}$ (nothing removed; $D 2$ wasn't in the set).
Result: ${D 1, D 3}$ .

In the figure, the cyan circle is run and the amber circle is fast; the two documents sitting in the overlap ( $D 1$ , $D 3$ ) are exactly the answer, and $D 2$ lives outside fast so it never qualifies.

Exercise 5.3

A read-heavy analytics table has $N = 4 \times 1 0^{9}$ rows. Compare disk reads for a point lookup on: (a) full scan (500 rows/page), (b) B-tree with $m = 100$ , (c) B-tree with $m = 1000$ . Then state which one you'd deploy and why, mentioning the memory cache effect.

Recall Solution 5.3

(a) Full scan pages $= \frac{4 \times 1 0 ^{9}}{500} = 8, 000, 000$ page reads. (b) $h = ⌈ lo g_{100} (4 \times 1 0^{9})⌉$ . Since $10 0^{4} = 1 0^{8} < 4 \times 1 0^{9}$ and $10 0^{5} = 1 0^{10} > 4 \times 1 0^{9}$ , we need $h = 5$ . (c) $h = ⌈ lo g_{1000} (4 \times 1 0^{9})⌉$ . Since $100 0^{3} = 1 0^{9} < 4 \times 1 0^{9}$ and $100 0^{4} = 1 0^{12} > 4 \times 1 0^{9}$ , we need $h = 4$ . Which to deploy: the $m = 1000$ B-tree. WHY: it needs only 4 levels vs 5, so one fewer disk seek per lookup, and the full scan (8 million reads) is never competitive for a point query. Memory cache effect: the root and upper internal levels are read on every query, so the database keeps them permanently in RAM. With the top ~3 levels cached, a lookup in the $m = 1000$ tree touches only ~1 actual disk read — the practical winner. (The wider $m = 1000$ nodes cost more RAM per cached page, but 4 levels is still cheap to cache.)

Recall Self-check: could you re-derive these from scratch?

One-tool, one-question summary of everything above.

What single formula converts row count into disk reads for a B-tree? ::: $h = ⌈ lo g_{m} N ⌉$ — each level multiplies reachable keys by $m$ , and each level is one disk read. Why is ORDER BY free on a B-tree but impossible on a hash? ::: B+tree leaves are stored sorted and linked, so you walk the chain in order; hashing scatters keys to destroy order. Which index wins for pure exact-match session lookups, and its one risk? ::: Hash ( $O (1)$ ), risk = collision skew degrading a bucket toward $O (N)$ with no worst-case guarantee. Full-text search reduces to which computation on postings lists? ::: Set operations (intersection for AND, difference for NOT) on sorted document-ID lists. Which index handles a mid-word substring LIKE '%son%', and why not full-text? ::: An n-gram/trigram index; full-text only tokenizes whole words, so it never stores the fragment son inside Johnson.