Hashing gets you there in one jump, if you only ever ask "equals"
CS205ES built a hash table for near-instant lookup by key. Applied to disk-based indexing, the same idea gives near-instant row lookup — with the exact same one sharp limitation carried over unchanged.
After this lesson
You should be able to
- Explain how hash-based indexing locates a row's block using a hash function.
- Explain why hash-based indexing cannot support range queries efficiently.
The same hash idea from CS205ES, now pointing at disk blocks
Hash-based indexing applies a hash function to the search key, producing a bucket number that identifies exactly which disk block should contain the matching row — this is precisely CS205ES's division-method hashing, with the value stored being a pointer to a disk block instead of a value sitting directly in an in-memory array slot.
Collisions are handled the same way too: two different keys hashing to the same bucket is resolved through chaining or open addressing, the identical two techniques CS205ES's own hash table visualizer demonstrated — the theory transfers directly, only the thing being pointed to has changed, from an array slot to a disk block.
One sharp limitation, carried over unchanged
A hash function scatters keys across buckets deliberately, with no relationship between a key's value and its bucket number — key 100 and key 101 could land in completely unrelated, physically distant buckets. This makes hashing excellent for exact-match lookup ("find roll_number = 4521") but useless for a range query ("find every roll_number between 4000 and 5000"), because there is no way to jump to "the start of the range" and scan forward — every single value in the range must be hashed and checked individually.
This is exactly why a database rarely relies on hash indexes alone: real applications need both kinds of query, so most systems pair a hash index for exact-match speed with a different structure — covered next — for anything involving order or ranges.
Try it yourself
A library system frequently runs "find the book with isbn = X" and occasionally runs "find all books with publication_year between 2015 and 2020." Would a hash index on isbn alone be a complete indexing solution? Explain.
Need a hint?
A hash index handles the isbn lookups excellently, but the publication_year query is a range query, which hashing cannot serve efficiently.
Check the worked solution
No, a hash index on isbn alone is not complete. It serves the isbn lookups excellently, since those are exact-match queries. But the publication_year range query needs a different, order-preserving index structure, because a hash index scatters years across unrelated buckets with no way to scan a contiguous range efficiently.
Quick check
Why can a hash index not efficiently answer a range query like "find all rows with value between 100 and 200"?
Why this lesson exists
Syllabus mapping
Index data Structures, Hash Based Indexing
Maps to course outcome CO4.