One Is Faster and Cannot Do Ranges, the Other Is for Writing
Last timeAnswering Without Touching the Table
Two structures exist alongside the tree. A hash is unbeatable on exact lookups and useless on ranges; a write-ordered log is for data arriving faster than a tree can take it.
Six lessons have been about one structure. There are two others worth knowing,
and knowing them is mostly about knowing what each one gives up, because each
gives up something the tree has.
The hash index
A hash index computes a number from the key and uses it to pick a bucket. The
key is in that bucket or nowhere. One read, no descent, no depth growing with
the table.
| reads for an exact looku | reads for the first row | reads for a range of ten | cost of an insert, tree | space used, tree equals | |
|---|---|---|---|---|---|
| tree | 2 | 1 | 11 | 100 | 100 |
| hash | 11 | 1 | 11 | 95 | 110 |
| write-ordered log | 5 | 3 | 5 | 25 | 170 |
The hash wins on exact lookups and the margin is smaller than people expect:
two or three reads against one, where the two or three are nearly always cached.
What it loses is total. Hashing scrambles the keys on purpose, so keys that were
next to each other are now in unrelated buckets. There is no range query, no
ordering, no sorted output, no prefix match, and no help with a composite key
unless the query supplies every column.
That is why hash indexes are rare as a general tool and common in specific
places: joining on an identifier inside a single query, caches keyed by exact
lookup, and partitioning rows across machines, where scattering is the goal
rather than a side effect.
The lesson stops here
5 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents