Hash Indexes

A hash index organizes records into buckets, where a hash function `h` maps every possible search-key value to a bucket number. To find the record with key `K`, the system computes `h(K)`, reads that one bucket (typically one disk page, possibly with a short overflow chain), and scans the handful of entries inside it for an exact match. This is fundamentally different from a B+-Tree Index, which encodes an ordering over keys and must compare `K` against separator keys at every level of a tree. The central design tension is bucket count versus load factor. If a hash file has `B` buckets holding `n` records, and the hash function distributes keys uniformly, each bucket holds about `n / B` records on average. Too few buckets and every bucket overflows into long linked chains, degrading lookups toward O(n). Too many buckets and most sit nearly empty, wasting space. Because real tables grow and shrink, a hash index's B must be able to change over time — this is the "dynamic hashing" problem, solved by extendible and linear hashing.

Static hashing fixes `B` when the file is created and never changes it. It is simple and gives excellent performance as long as the estimated `n` was accurate, but it fails ungracefully: once the file grows past its planned capacity, every bucket accumulates an overflow chain of additional pages, and lookups degrade toward a linear scan of that chain. The only fix for static hashing is to rebuild the entire file with a new `B` and rehash every record — an O(n) operation that must lock out normal operation. Dynamic hashing schemes exist precisely to avoid this all-or-nothing rehash, growing the bucket count incrementally, one bucket at a time, while old buckets keep serving lookups undisturbed.

Static hashing, and why it breaks

Static hashing picks `B` buckets numbered `0` to `B-1` and a hash function `h(K) mod B`. Insertion computes the bucket, writes the record there, and chains an overflow page if the bucket is full. Lookup computes the bucket and scans the primary page then any overflow pages. ``` STATIC-HASH-LOOKUP(K): i ← h(K) mod B page ← bucket[i].primary_page while page ≠ NULL: for each entry e in page: if e.key == K: return e.record page ← page.overflow_pointer return NOT-FOUND ``` This is O(1) expected time only if the average chain length stays short — which requires `B` to be chosen close to `n / (records per page)` and to stay that way as `n` changes. Real tables do not stay the same size, so static hashing needs periodic full reorganizations, each costing O(n) I/O and blocking access. Dynamic schemes were invented to make growth incremental.

Extendible hashing

Extendible hashing (Fagin, Nievergelt, Pippenger, Strong, 1979) adds one layer of indirection: a directory of `2^G` pointers, where `G` is the global depth. Each directory slot points to a bucket, but multiple directory slots may point to the same bucket if that bucket has not yet been split as many times as the directory has grown. Each bucket stores its own local depth `L ≤ G`, recording how many bits of the hash it actually distinguishes on. To locate a key `K`, take the low-order `G` bits of `h(K)` (call this the key's hash suffix) and use it as an index into the directory; follow that directory pointer to the bucket. ``` EXTENDIBLE-LOOKUP(K): hash ← h(K) slot ← low-order G bits of hash # G = global depth bucket ← directory[slot] scan bucket's page for K return record or NOT-FOUND ``` Insertion is where the structure earns its name: ``` EXTENDIBLE-INSERT(K, record): hash ← h(K) slot ← low-order G bits of hash bucket ← directory[slot] if bucket has free space: insert (K, record) into bucket return

# bucket is full: must split it if bucket.local_depth == G:

# directory too small to distinguish the split halves — double it G ← G + 1 directory ← duplicate every entry

# each old slot i now has two slots, i and i + 2^(G-1), pointing to the same bucket

# create a sibling bucket, incrementing local depth of both L ← bucket.local_depth + 1 bucket.local_depth ← L new_bucket.local_depth ← L

# repartition entries of the full bucket by their L-th bit for each entry e previously in bucket: target ← (low-order L bits of h(e.key) selects old or new bucket) move e into the correct one of {bucket, new_bucket}

# redirect exactly the directory slots that should now point to new_bucket for each directory slot s whose low-order L bits match new_bucket's suffix: directory[s] ← new_bucket EXTENDIBLE-INSERT(K, record) # retry; guaranteed to fit unless split cascades ``` The crucial cost-saving idea: doubling the directory is cheap (it is just an array of pointers, e.g. 2^20 pointers is only a few megabytes), while splitting a bucket only moves the records that were in that one bucket — no other bucket's data is touched. This is the entire reason extendible hashing avoids the O(n) global rehash of static hashing. Deletion is the mirror image: remove the entry, and if a bucket becomes empty (or underfull, in more aggressive implementations), merge it with its buddy bucket (the one differing only in the last local-depth bit) and, if every bucket pair has now merged down to a shared local depth less than `G`, the directory can be halved. Most practical systems implement bucket merging but skip directory shrink-back, since the directory is small anyway and avoiding a rare, tricky operation is often worth the modest wasted memory.

Linear hashing

Extendible hashing needs an in-memory directory that must itself be split, doubled, and kept consistent — a real engineering burden, particularly under concurrent access. Linear hashing (Witold Litwin, 1980) achieves similar amortized behavior without any directory at all, by fixing the order in which buckets will split ahead of time: bucket 0 splits first, then bucket 1, then bucket 2, and so on, regardless of which bucket actually overflowed. Linear hashing maintains:

• `N` — current number of "original-round" buckets (buckets 0 through N-1 exist at the start of the current round).
• `p` — a pointer, `0 ≤ p < N`, indicating the next bucket scheduled to split.
• Two hash functions `h_i` for round `i` and round `i+1`, typically `h_0(K) = h(K) mod N` and `h_1(K) = h(K) mod 2N`, so that `h_1` simply looks at one more bit than `h_0`.

A key rule: at any moment, buckets numbered `0 .. p-1` have already split this round and must be probed with `h_1`; buckets numbered `p .. N-1` have not yet split and must still be probed with `h_0`. ``` LINEAR-LOOKUP(K): i ← h(K) mod N # h_0, current round's base modulus if i < p: i ← h(K) mod (2 * N) # this bucket already split; use h_1 instead scan bucket[i] (and its overflow chain) for K return record or NOT-FOUND LINEAR-INSERT(K, record): i ← LOCATE-BUCKET(K) # same rule as LINEAR-LOOKUP if bucket[i] has free space: insert (K, record) into bucket[i] else: append record to bucket[i]'s overflow chain

# independent of where the insert landed, check the SPLIT TRIGGER if load_factor() > threshold: SPLIT() SPLIT():

# split bucket p into bucket p and new bucket (N + p) old ← bucket[p] new ← create bucket[N + p] for each entry e in old (including its overflow chain): if h(e.key) mod (2N) == p: keep e in old else: # must equal N + p move e to new p ← p + 1 if p == N: p ← 0 N ← N 2 # round complete; start next round ``` Notice that `SPLIT` is triggered by an overall load-factor threshold, not by the specific bucket that just overflowed — bucket `7` might be the one that's currently overflowing with a long chain, but bucket `p` (say bucket `2`) is the one that actually gets split. That overflow chain on bucket 7 is tolerated temporarily; it will shrink once bucket 7's own turn to split arrives. This design deliberately trades a short-lived overflow chain for the huge simplification of never needing a directory.

Static hashing. With `n` records uniformly hashed into `B` buckets of capacity `c`, the expected chain length per bucket is `n / (B·c)`. Lookup and insertion cost `O(1 + n/(Bc))` expected page I/Os. As long as `B` is provisioned so that `n/(Bc) = O(1)`, lookups are effectively O(1). But when `n` grows beyond the design capacity, chains grow linearly with `n`, degrading toward O(n) worst case — the entire motivation for dynamic schemes. Rebuilding a static hash file to restore O(1) performance costs O(n) I/O and requires rehashing every record, which is why production systems avoid pure static hashing for tables with unpredictable growth.

Extendible hashing. Lookup is always exactly two dereferences plus one page read: compute `h(K)`, index into the in-memory directory (O(1), often no I/O since directories are small enough to fit in memory), then read one bucket page. This is O(1) worst case for lookup, assuming the directory is memory-resident, which is standard practice because `2^G` pointers stays modest even for large `G` (each pointer is a handful of bytes; `G = 20` is a million pointers, a few MB). Insertion is O(1) amortized. A single overflow triggers a bucket split that touches only the records in that one bucket — call this bucket's occupancy `c` records — costing O(c) work, independent of `n`. Directory doubling costs O(2^G), but doubling only happens when the global depth increases, and each doubling at least doubles the directory's capacity to absorb future splits before the next doubling is needed. This telescoping structure — same amortized argument used for dynamic array growth — means the total cost of all directory doublings across `n` insertions is O(n) overall, i.e., O(1) amortized per insertion. Space overhead is the directory itself, O(2^G) pointers, plus O(n/c) buckets, each at least half full in typical implementations (some implementations allow lower fill factors after merges). Invariant that guarantees correctness: for every directory slot `s` and the bucket `B = directory[s]` it points to, the low-order `B.local_depth` bits of `s` equal the low-order `B.local_depth` bits of every key stored in `B`. This invariant is established at bucket creation and preserved by every split (which only ever increases local depth and redirects exactly the slots whose suffix now disagrees) and by directory doubling (which duplicates pointers, changing no bucket assignment). Because the invariant holds, `LOOKUP` using `G` bits of the hash always lands on the unique bucket that could contain `K` — never a wrong bucket, never a linear scan of the whole file.

Linear hashing. Lookup cost is O(1) expected: at most one modulus computation to decide between `h_0` and `h_1`, then one bucket read plus its (hopefully short) overflow chain. Because splits happen on a fixed schedule tied to overall load factor rather than to which bucket is hottest, some buckets can carry a temporary overflow chain for up to one full round (`N` insert-triggered splits) before their turn comes — this is the price paid for having no directory. In the worst case a single unlucky bucket could see O(n/N) chain length right before its scheduled split, but this is bounded and self-correcting: it necessarily resolves once `p` reaches that bucket. Insertion is O(1) amortized by the same telescoping argument as extendible hashing: a full round of `N` splits (each O(records per bucket)) exactly doubles capacity, so total split work across `n` insertions is O(n). Space overhead for linear hashing is strictly better than extendible hashing in one respect: no directory at all, just an array of bucket pointers of size O(n/c) (or even a computable bucket-address function in some implementations), which is the minimum possible.

Why hashing cannot serve range queries — a real argument, not an assertion. A hash function `h` is explicitly designed to satisfy, for keys `K1 ≠ K2`, that `h(K1)` and `h(K2)` are (with high probability, over the choice of hash function or the distribution of keys) unrelated — this is precisely the uniformity property that makes buckets balanced. Formally, a good hash function approximates the property that for any two distinct buckets `i ≠ j`, `P[h(K) = i]` and the ordering of `K` relative to other keys are independent. Consequently, keys `K1 < K2 < K3` that are numerically adjacent can be routed to buckets `h(K1) = 5, h(K2) = 91, h(K3) = 2` — arbitrarily far apart in bucket-address space. A range query `WHERE key BETWEEN K1 AND K3` would therefore need to inspect every bucket, because the index provides no way to know which buckets might contain keys in that range without checking each one — an O(B) or effectively O(n) operation, no better than a full scan (and worse, since a scan at least reads pages sequentially while probing scattered buckets means random I/O). A B+-Tree Index, by contrast, maintains keys in sorted order specifically so a range's lower bound can be located once and the answer read off contiguously; this is a structural, not incidental, difference — hashing optimizes for the opposite property that a tree needs.

Trace extendible hashing with bucket capacity `c = 2`, starting from an empty directory with `G = 1` (2 slots), inserting keys with these 4-bit hash values (we always look at the low-order bits):

Step 1 — Insert A (hash …11), B (hash …01). G=1, directory slots `0` and `1`, one bucket each, local depth 1.

• A's low 1 bit = `1` → bucket₁. Insert. Bucket₁ = {A}.
• B's low 1 bit = `1` → bucket₁. Insert. Bucket₁ = {A, B}. (Full: capacity 2, holds 2.)

Step 2 — Insert C (hash …01). Low 1 bit of C = `1` → bucket₁, which is full (A, B already there).

• Bucket₁'s local depth (1) equals G (1), so we must double the directory: G becomes 2, slots become `00, 01, 10, 11`.
• Split bucket₁ using 2 bits now: A=1011 → low 2 bits `11`; B=0101 → low 2 bits `01`. These differ, so A and B land in different new buckets. New bucket "11" holds A, new bucket "01" holds B, both local depth 2.
• Directory slot `00` and `10` still point at the untouched bucket₀ (which never had any data — local depth 1, still fits under either new slot since bucket₀'s data, if any, doesn't depend on the 2nd bit).
• Retry inserting C: low 2 bits of C = `01` → bucket "01" (currently {B}). Insert. Bucket "01" = {B, C}.

Step 3 — Insert D (hash …10). Low 2 bits = `10` → bucket₀ (local depth 1, currently empty or holding whatever was there before — assume empty). Insert. Bucket₀ = {D}.

Step 4 — Insert E (hash …01). Low 2 bits = `01` → bucket "01" = {B, C}, which is full.

• Bucket "01"'s local depth (2) equals G (2) again, so double the directory again: G becomes 3, 8 slots.
• Split bucket "01" using 3 bits: B=0101 → low 3 bits `101`; C=1101 → low 3 bits `101`. Both B and C have the same 3-bit suffix! They land in the same new bucket — the split did not separate them.
• This is a real, well-known edge case: the split doesn't help immediately. The algorithm's retry-insert loop handles this correctly: bucket "101" is now local depth 3, holds {B, C}, still full, and E also hashes to low 3 bits `101` (E = 1001 → low 3 bits `001`... let's recompute: E=1001, low 3 bits are `001`, not `101`). So E actually goes to a different bucket after the split, `001`, which is empty. Insert succeeds: bucket "001" = {E}.

This trace illustrates the one genuine subtlety in extendible hashing: a single split does not guarantee the two colliding keys separate (B and C shared their new 3-bit suffix), so implementations must be prepared to split a bucket again (and double the directory again if local depth has caught up to global depth) if a retry still finds the target bucket full. In the worst pathological case (many keys sharing a long common hash suffix), this cascades — bounded in practice by hash function quality, but a real implementation must handle it as a loop, not a single conditional.

Linear hashing worked in parallel, same keys, `N = 2` initial buckets, `p = 0`, capacity 2, split threshold "any bucket overflow triggers a split of bucket p":

This highlights linear hashing's core tradeoff versus extendible hashing directly: bucket 1 is allowed to overflow into a chain for a while, because its scheduled split (when `p` reaches 1) hasn't arrived yet — no directory doubling is needed, but a temporary chain is tolerated as the price.

Ronald Fagin, working with Jürg Nievergelt, Nicholas Pippenger, and H. Raymond Strong, published "Extendible Hashing — A Fast Access Method for Dynamic Files" in 1979, introducing the directory-plus-local-depth idea described above. The insight that a small in-memory directory could be doubled cheaply while bucket splits stayed strictly local was a major departure from the static hash files common in databases at the time, and it directly influenced the design of dynamic hash tables in file systems and database storage engines that followed. Witold Litwin's linear hashing, published in 1980, offered a complementary solution to the identical problem — eliminating the directory altogether by fixing the split order in advance — trading a small amount of temporary chain length for the elimination of directory maintenance, which matters when concurrent access to a shared directory is itself a bottleneck.

Relational engines such as PostgreSQL offer an explicit `HASH` index type, recommended specifically for equality-only workloads on wide values, since PostgreSQL's hash indexes store only the hash, not the value, making them more compact than a B-tree for that narrow use case. In-memory key-value stores (Redis's hash tables, memcached) are essentially pure static or resizing hash tables optimized for equality lookup at the cost of no ordering. The Hash Join operator inside query optimizers builds a temporary in-memory hash table over the smaller relation and probes it with the larger relation's rows — the exact same bucket-and-probe mechanism as a hash index, just built transiently for a single query rather than persisted. Distributed systems generalize hashing further into consistent hashing, used by Cassandra, DynamoDB, and content-delivery networks, where the "buckets" are physical machines and the hash function's job is to distribute keys across a cluster while minimizing data movement when machines are added or removed — directly analogous to extendible hashing's goal of growing without a full rehash, but applied at the scale of a data center rather than a single file. Understanding when hash structures win over tree structures is exactly the reasoning that Index Selection formalizes into a systematic decision procedure.

Ask the tutor: How would you decide, for a given table and query workload, whether to build a hash index, a B+-tree index, or both?