Skip to content
Tutorials Center
My learning

Topics

Lesson 55 of 79 ยท Storage and Indexing

Hashing: Static, Extendible and Linear

Learn hash-based indexing: static hashing with overflow chains, extendible hashing with a directory, linear hashing, and how hashing compares to B+ trees.

A B+ tree finds a key by comparing it with separators on its way down. Hashing takes another route: a function turns the key into a bucket number, and the record lives in that bucket, or at least that is where you look. If the function spreads keys evenly and each bucket is a single disk page, an equality lookup costs about one page read, regardless of the table size.

The difficulty is that a file changes size. A hash function that maps to a fixed number of buckets works until the file grows, and then buckets overflow. This lesson shows the three classic answers: static hashing with overflow chains, extendible hashing with a directory that doubles, and linear hashing that grows one bucket at a time. Live Python simulations print the buckets so you can follow every step.

One idea, three growth plans

Static Fixed bucket count. Overflow chains when full.
Extendible A directory that doubles. Splits one bucket.
Linear No directory. Splits buckets in a fixed order.

All three aim for about one page read per lookup.

1 / 2

Hash function and buckets

A bucket is one page (or a few) that holds index entries or records. The hash function h(key) maps any key to an integer, and the bucket is chosen from that number, for example h(key) mod N for N buckets. A good function distributes keys evenly and is cheap to compute. Real systems use strong mixing functions, not the raw key. The examples below use small integers and key mod N or the low bits of the key, since that makes the results easy to check by hand.

To find a key, compute its bucket number, read that bucket and scan it. To insert, put the entry in its bucket. The only questions are what to do when the bucket is full and how to grow.

Static hashing

In static hashing the number of primary buckets N is fixed when the file is created. When a bucket is full, the file gets an overflow page chained to it. A lookup reads the primary page and then follows the chain.

Python Static hashing and overflow chains

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The numbers 3, 11, 19, 27, 35 and 43 all have the same remainder mod 4, so bucket 3 needs three pages and a lookup there needs up to three reads, while bucket 2 is empty. Two problems follow. A skewed hash function creates long chains. And if the file grows ten times, chains grow ten times too: static hashing has no way to adapt, so the administrator has to rehash the whole file into a larger bucket count, which takes the table offline for a while.

Extendible hashing

Extendible hashing removes the full rehash. It keeps a directory, an array of pointers to buckets, indexed by the first (or last) d bits of the hash value. d is the global depth, so the directory has 2^d slots. Each bucket has its own local depth d': the number of bits that all its keys share. Several directory slots can point to the same bucket (exactly 2^(d - d') of them).

When a bucket overflows:

  1. If its local depth is less than the global depth, the bucket splits into two. Its local depth increases by one, the keys are redistributed using the next bit, and half of the directory slots that pointed to it are redirected to the new bucket. The directory does not change in size.
  2. If its local depth equals the global depth, the directory doubles first (each slot is copied), the global depth increases by one, and then the bucket splits as in case 1.

Only the overflowing bucket is touched, plus the directory (small enough to sit in memory). A lookup costs the directory access plus one bucket read: two page reads at most, often one.

The simulation uses the lowest bits of the key (a hardware-friendly choice, the idea is the same with leading bits) and a bucket capacity of 2. It prints a message each time the directory doubles or a bucket splits.

Python Extendible hashing simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Follow the first interesting event. After 4 and 6, the "even" bucket (slot 0) is full. Inserting 10 needs that bucket, its local depth (1) equals the global depth (1), so the directory doubles to depth 2 and the bucket splits on the second-lowest bit: 4 stays (...00), 6 and 10 move together (...10). When 16 arrives, the bucket [4, 12] is full and has depth 2, so the directory doubles again to depth 3, but only that one bucket splits. In the final directory, slots 001 and 101 both point to bucket B1, and 010 and 110 both point to B2: those buckets have local depth 2, so they ignore the third bit. Doubling the directory is cheap; no data moves except for the one bucket that split.

A weak spot: if many keys share a long prefix of bits (a bad hash), the directory can double again and again before a bucket finally splits. Good hash functions avoid it.

Linear hashing

Linear hashing avoids the directory altogether. The file grows by splitting buckets in a fixed round-robin order, no matter which bucket overflowed. A pointer next marks the next bucket to split. Overflow pages are allowed temporarily, and the split of a bucket relieves the pressure later, because eventually every bucket gets its turn.

  • At level L there are 2^L buckets at the start of a round, addressed with h mod 2^L.
  • To find a key: compute a = h mod 2^L. If a < next, that bucket has already been split in this round, so use h mod 2^(L+1) instead.
  • A split is triggered by a rule such as "average load above a threshold". It adds one new bucket at the end, redistributes the entries of bucket next between itself and the new bucket using h mod 2^(L+1), and advances next. When next reaches 2^L, the round ends: the level increases and next returns to 0.

The simulation below splits whenever there are more than 1.5 entries per bucket on average.

Python Linear hashing simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the first split happens after inserting 13 and splits bucket 0, even though the entries pushing the load over the limit might have belonged elsewhere. That is the price of the fixed order; the benefit is that the file grows smoothly by one bucket at a time with no directory and no pause. Here no bucket held more than two keys at the end, so the "needs an overflow page" note stays silent; with unlucky keys a bucket can carry an overflow page for a while until its turn comes.

Hashing or B+ tree?

Hash index B+ tree index
Equality (=) About 1 page read Tree height (3 to 4)
Range (BETWEEN, <) Not possible Excellent
ORDER BY Not possible Free from the leaf order
Prefix search (LIKE 'ab%') Not possible Possible
Growth Needs extendible/linear schemes Splits locally, always balanced
Skewed or duplicate keys Long chains or big directory Handled well
Where used In-memory tables, join hash tables, some engines' hash indexes The default index type almost everywhere

Hashing wins only on pure equality lookups, and the margin over a cached B+ tree is small (the tree's upper levels are in memory anyway). That is why B+ trees are the default. The place where hashing is everywhere in query processing is not the index but the hash join and hash aggregation, which build temporary hash tables in memory (see Join Algorithms).

SQLite has no hash index type; everything you create with CREATE INDEX is a B-tree. PostgreSQL offers USING HASH, MySQL's MEMORY engine can use hash indexes, and several in-memory and key-value stores are built on hashing. Those commands are not available in the browser sandbox, so this lesson uses simulations.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does static hashing perform badly when the file grows a lot?

    Static hashing has no directory and no automatic growth. More records per bucket means overflow pages and more reads per lookup, until the file is rehashed.
  2. 2. In extendible hashing a bucket with local depth 2 overflows while the global depth is 2. What happens?

    When local depth equals global depth, the directory has no spare slot to point to a new bucket, so it doubles first (global depth 3). Then only the full bucket splits.
  3. 3. What does the pointer next mean in linear hashing?

    Linear hashing splits buckets in a fixed order, whether or not that bucket is the one that is full. The pointer marks whose turn it is.
  4. 4. Which query can a hash index NOT help with?

    A hash function scatters neighbouring keys, so a range cannot be turned into a small set of buckets. Ranges and ordering need an ordered structure such as a B+ tree.

Summary

  • Hashing maps a key to a bucket (usually a page), so an equality lookup costs about one page read.
  • Static hashing has a fixed bucket count and uses overflow chains; it degrades as the file grows.
  • Extendible hashing uses a directory indexed by hash bits with global and local depths; it doubles the directory and splits one bucket when needed.
  • Linear hashing grows one bucket at a time in round-robin order using a level and a next pointer, with no directory.
  • Hash indexes cannot serve ranges or ordering, which is why B+ trees are the default index; hashing is more important inside joins and aggregations.

Next: Bitmap, Composite, Partial and LSM Indexes.