Hash Indexes

## What a hash index is An index is a side structure mapping a key value to the location of rows holding it. A **hash index** does that mapping with a hash function rather than a sorted tree. Conceptually the index is an array of *buckets* (slots, usually one disk page each). A hash function `h` takes the indexed value and produces a large integer; the engine reduces that to a bucket number, classically `h(key) mod N` for `N` buckets. ## The write path Inserting a row computes `h(key)`, finds the bucket, and appends an entry. The entry holds a row identifier (a physical address in heap-organised engines, or the primary key in clustered-index engines) and either the full key or just the stored hash value. Storing only the hash keeps entries tiny and fixed-width regardless of how long the key is — an attractive property for indexing long URLs or hashes — but then a final key comparison must happen against the actual row. ## The read path A lookup for `key = X` runs three steps: 1. Compute `h(X)` and derive the bucket number. Pure CPU work, no I/O. 2. Read that one bucket page (plus its overflow chain, if any). 3. Compare each candidate entry's key against `X` and discard non-matches, then follow surviving row pointers to fetch rows. Step 3 exists because hashing is many-to-one: distinct keys can produce the same bucket, and even the same hash value. A hash index therefore *narrows*, it does not *decide*; the equality test on the real key is still required for correctness. ## Why the cost is constant A B+tree lookup descends from root to leaf, touching one page per level — typically three or four page reads for a large table, growing logarithmically as the table grows. A hash lookup touches one bucket regardless of whether the table has a thousand rows or a billion. That is the entire structural argument for hash indexes: O(1) equality probes instead of O(log n). In practice the advantage is narrower than it looks, because a B+tree's upper levels are almost always resident in the buffer cache, so its "three or four reads" are often one physical read plus a few cached ones. Hash indexes win on CPU comparisons and on very large keys more than on I/O. ## What the layout costs you Bucket numbers are deliberately unordered — a good hash scatters neighbouring keys to distant buckets. Consequences: - **No range scans.** Keys just above `X` are not stored anywhere near `X`. - **No sorted output.** Reading buckets in order yields effectively random key order, so the index cannot satisfy an ordering requirement or feed a merge join. - **No prefix or partial-key matching.** Hashing the whole value means a prefix hashes to something unrelated. - **No min/max shortcut.** There is no leftmost or rightmost entry. It also means the index is only usable for the exact expression that was indexed, on the full key, with an equality comparison. ## Sizing and rebuilds Because `N` appears in the bucket calculation, growing the index is not free. Static hashing fixes `N` at build time and degrades as data grows (long overflow chains); dynamic schemes such as linear or extendible hashing split buckets incrementally so the structure grows without a full rebuild. Real engines use dynamic schemes, but a badly loaded hash index still degrades toward linear scanning of an overflow chain, at which point the O(1) promise evaporates. ## Where you actually meet them Hash indexes are common inside in-memory engines and caches, as internal join structures (a hash join builds a transient hash table on the fly), and as an optional on-disk index type in several relational engines. On disk they are a niche choice; the default index type in essentially every mainstream relational engine is the B+tree, because it serves equality *and* everything else.