Part 5 of 5 · 3 min read
Exercises
Easy
Easy 1: Name how a hash index locates a value (15 minutes)
State what a hash index computes to locate a key, and what it does not need to do, compared to a B+-tree.
Done when: computing a hash to reach a bucket directly, without tree traversal, is correctly named.
Hint
It computes a hash of the key to reach a bucket directly; it does not need to traverse levels of a search tree.
Easy 2: Name what a collision is (15 minutes)
Define a collision in a hash index.
Done when: two different keys hashing to the same bucket is correctly described.
Hint
Two different keys hashing to the same bucket.
Easy 3: Name the query type hash indexes cannot support (15 minutes)
State the type of query a hash index cannot support at all.
Done when: range queries are correctly named.
Hint
Range queries.
Medium
Medium 1: Explain why exact-match lookups stay fast at scale (25 minutes)
Explain why a hash index lookup takes roughly the same amount of work whether the table has a thousand rows or a hundred million rows.
Done when: the explanation correctly ties this to computing one hash and landing on a bucket directly, with no traversal that grows with table size.
Hint
A hash computation and bucket lookup take the same small amount of work regardless of how many rows exist.
Medium 2: Explain why nearby keys do not land near each other (25 minutes)
Explain why two consecutive dates, such as 2026-01-15 and 2026-01-16, are unlikely to land in neighboring buckets of a hash index.
Done when: the explanation correctly notes a hash function is designed to scatter values evenly, destroying any closeness between nearby keys.
Hint
A hash function scatters values evenly across buckets by design, so similarity in value gives no similarity in bucket location.
Medium 3: Choose the right index type for a query pattern (25 minutes)
A column is only ever queried with WHERE column = value, never with a range. Decide whether a hash index or a B+-tree is the better default choice, and explain why.
Done when: a hash index is chosen, with the explanation correctly citing its faster exact-match performance when no range support is ever needed.
Hint
A hash index, since it is faster for pure exact-match lookups and no range support is needed here.
Hard
Hard 1: Explain why a collision does not break correctness (30 minutes)
Explain why a hash index still returns correct results even when collisions occur.
Done when: the explanation correctly describes checking each entry within the collided bucket individually to confirm an exact match, rather than assuming the first entry found is correct.
Hint
Each entry in the collided bucket is checked individually against the search key, so only the truly matching entry is returned.
Hard 2: Explain the risk of choosing a hash index for the wrong column (35 minutes)
A column is indexed with a hash index, but a later report needs WHERE placed_on BETWEEN ... on that same column. Explain what happens to that report's performance, and what should have been chosen instead.
Done when: the explanation correctly states the hash index gives no benefit for the range query, forcing a full scan, and that a B+-tree should have been chosen if range queries were ever expected.
Hint
The hash index provides no help for the range query, so a full scan runs instead; a B+-tree would have supported the range efficiently.
Hard 3: Compare the two structures' cost growth (40 minutes)
Explain, in general terms, how a hash index's lookup cost and a B+-tree's lookup cost each grow as a table grows from a thousand rows to a billion rows.
Done when: the explanation correctly states a hash index's exact-match cost stays roughly constant, while a B+-tree's cost grows very slowly (logarithmically) due to its increasing depth, with both still vastly cheaper than a full scan.
Hint
A hash index's cost stays roughly flat as the table grows; a B+-tree's cost grows slowly with depth, but both remain far cheaper than scanning every row.