A hash index answers a point lookup in one I/O and answers a range query only by reading the whole table, because hashing destroys the order a range needs. A tree pays its height on both. On a workload of nine hundred lookups and a hundred small ranges a second that is 500 900 I/O against 3 000, and “hash is faster” turns out to be a true claim about one operation wearing the clothes of a claim about an index.
Core ideas
Two structures, two operations, four numbers. The argument people have about this is entirely caused by quoting one of the four.
It computes a bucket from a key and reads it: one I/O, no descent, no comparisons. The expected probe length behind that 1 is Θ(1 + α) under simple uniform hashing, with a Θ(n) worst case no hash function removes; “Hashing with Chaining” on the Algorithms path establishes both, and this lesson uses them rather than re-deriving them. What the structure spends to get that 1 is the order of the keys.
There is no way to ask a hash index for the keys between two values except to look at every one of them, so a range costs a full scan: 10⁶ rows at 200 rows a page is 5 000 page reads. It is not that a hash is slower at ranges. It is that it has no access path for them, and what you are pricing is the table scan the planner falls back to.
A B-tree descends to the first matching key and then reads leaves in key order, so a range of k rows costs about (h − 1) + ⌈k/rows per page⌉. Over a million rows at B = 500 the height is 3, and a range of a hundred rows is 3 I/Os altogether: two internal levels, then one leaf that already holds all hundred.
The material
What a hash index gives up for its point lookup, and what that costs on the operation it gave up.
A point lookup retrieves the row for one exact key. A range query retrieves every row whose key lies between two bounds, and is priced by the number of rows k it returns.
An index is ordered if it stores keys in a comparison order, and unordered if it stores them by a hash of the key. Only an ordered index has an access path for a range.
The hash index's 1 is worth taking seriously rather than waving at. Under simple uniform hashing the expected number of probes is Θ(1 + α) in the load factor α, so a table kept at a sensible load factor really does answer in about one access — and the worst case, where every key collides, really is Θ(n). Those are Algorithms' results, proved in “Hashing with Chaining”; what this lesson adds is that on disk the unit is a page read and the constant is therefore expensive.
The hash index does one hundred and sixty-seven times the I/O of the tree on that mix, and it is genuinely three times cheaper on the operation it is good at. Both facts come out of the same four numbers. Which one you quote is a choice about what you want the answer to be.
Set the two totals equal and solve for the range rate r at a fixed point rate. With 900 point lookups a second: 900(1) + r(5 000) = 900(3) + r(3), so r(5 000 − 3) = 900(3 − 1) and r = 1800/4997 ≈ 0.360 range scans a second. One range query every three seconds is enough to make the tree the cheaper engine on this table.
Remove the ranges entirely. At 900 point lookups a second and nothing else, the hash index does 900 I/O a second and the tree does 2 700 — three times as many, exactly the ratio of 1 to h. The true claim behind “hash is faster” is alive; it is just very small, and it is a claim about one operation.
The same misconception exists in memory, where “a hash table is always the fastest map” is corrected by pointing out that it cannot answer predecessor, range or ordered iteration at all. “Choosing a Structure” on the Algorithms path is that statement. This lesson is the same fact with a disk attached, and the disk is what turns a structural limitation into a number: not “unsupported” but 5 000 I/O.
What the count assumes: that pages hold their nominal number of rows, that nothing is cached, and that the range is contiguous in the index's key order. Cache the tree's top two levels and its point lookup falls from 3 to 1, at which point the hash index's advantage on the operation it is good at disappears entirely — which is worth knowing before anyone builds an argument on the 1 against 3.
Interactive
One I/O for a point lookup, the whole table for a range
Method
Four costs, then two products, then a comparison. The order stops you from quoting the wrong one of the four.
Point and range, hash and tree. Any claim about an index made from fewer than four numbers is a claim about one operation, and it will be defended as though it were about the index.
A range returning k rows at p rows a page is ⌈k/p⌉ leaf pages, and a full scan of n rows is ⌈n/p⌉ pages. Rows are what the query asks for; pages are what the device delivers.
point rate × I/O a point + range rate × I/O a range, for each engine, in I/O a second. Now the two engines are comparable, which they were not when the units were operations.
Set the two totals equal and solve for whichever rate is in doubt. The crossover is more useful than the winner: it tells you how much of the workload would have to change to change the answer, and here that is one range query every three seconds.
Four costs, two totals, and then the rate at which the two totals meet.
The 5 000 contains no hash parameter. It is 10⁶/200: rows divided by rows a page, which is what a scan costs when there is no access path. Doubling the buckets, improving the hash function or removing every collision leaves it exactly where it is.
The crossover is the honest summary. At these page geometries the tree wins any workload with more than about one range scan every three seconds, and the hash index wins below that. Neither engine is faster; one of them is cheaper at your mix, and the mix is measurable.
For a faded rehearsal, widen the range to 1 000 rows and keep everything else. The supplied first move is that the tree's range cost becomes 2 + ⌈1 000/200⌉. Compute it, recompute both totals, and then say what happened to the crossover rate and why it moved in the direction it did. Run the lab at your numbers before opening the quiz.
You should be able to write down all four costs for a stated page geometry, total a workload in I/O a second on both engines, and solve for the rate at which the answer changes.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.