Part 3 of 5 · 1 min read
Why exact-match lookups are so fast
A single hash computation replaces several levels of tree traversal.
Think of the coat-check rule again: computing the hook number from a ticket takes one quick calculation, compared to searching through a long rack of coats one at a time.
In plain words: a B+-tree lookup must walk down several levels of internal nodes before reaching the right leaf, with cost that grows slowly as the table grows. A hash index skips that traversal entirely: computing a hash and landing on a bucket takes roughly the same, very small amount of work no matter how large the table has grown. This makes a well-sized hash index faster than a B+-tree for a pure exact-match lookup, with no range involved.
A worked example. Looking up one exact customer_id value in a hash index on a hundred-million-row table takes about the same small amount of work as the same lookup on a thousand-row table.
The key lines. No new SQL; the speed difference is internal to how the two index types execute the same kind of query.
Collision
A collision occurs when two different keys hash to the same bucket, requiring the bucket's short list of entries to be checked individually to find the correct match.
Example: two different coat tickets landing on the same numbered hook, requiring a quick check of which coat is actually which, is a collision.