The idea: a directory of pointers in front of the buckets
Extendible hashing is a hash index for data on disk. The keys live in buckets, and each bucket is one disk page. In front of the buckets sits a small directory: an array of 2g pointers. The number g is the global depth. To find a key, hash it, write the hash in binary, and take its last g bits. They are the index of a directory entry, and that entry points to the bucket.
The page uses h(k) = k mod 16, shown as 4 bits, and buckets of 2 keys. A real bucket is a page of 4 KB to 16 KB and holds hundreds of keys; 2 makes the splits happen quickly. The table starts with g = 1 and two empty buckets. Pick a key and press Insert or Find, or run a demo.
Global depth and local depth
Each bucket also has a local depth d, shown as d=… in front of it. All keys in a bucket agree on their last d bits; the grey name after the bucket, such as …01, shows those bits. A bucket with d < g only looks at d bits, so 2g−d directory entries point to it. In the figure above, bucket …1 has d = 1 while g = 2, so the two entries 01 and 11 share it. Always d ≤ g.
Find: one bucket read
find(k) reads one directory entry and then one bucket. The directory is small (a pointer per entry), so a database keeps it in memory, and a lookup costs one disk read however large the file grows (Demo 1: find(32) reads entry 0 and bucket …0).
Insert: split one bucket
insert(k) follows the same path. If the bucket has room, k goes in and nothing else changes. If the bucket is full and its local depth is less than g, only that bucket splits. A new bucket is made, both get local depth d + 1, and the keys whose bit d is 1 (counting from 0 at the right) move to the new bucket. Of the entries that pointed to the old bucket, the ones whose bit d is 1 now point to the new one. The directory keeps its size. Then the insert is tried again.
This is why extendible hashing grows smoothly: a static hash file would have to rehash every key into a bigger file, but here one insert touches the full bucket, one new bucket and a few directory entries.
Doubling the directory
If the full bucket's local depth equals g, only one entry points to it, so there is no entry to give the new bucket. The directory first doubles: g goes up by 1, and each new entry 1x copies the pointer of its twin 0x, which has the same last g bits. Doubling copies pointers only; no key moves and no bucket is read. Now the full bucket has d < g and splits as above (Demo 2).
A split does not always help at once. If all keys in the bucket agree on bit d, they all stay, the new bucket is empty, and the insert overflows again. In Demo 4, 20 (0100), 32 (0000) and 44 (1100) all end in 00, so one insert doubles the directory twice, to g = 3, and leaves an empty bucket. Many keys with the same hash bits (skew) make the directory large while most entries point to the same few buckets. Two keys with the same hash can never be split apart; real systems put them in an overflow page.
Compared with other disk indexes
| Static hashing | Extendible hashing | Linear hashing | B+ tree | |
|---|---|---|---|---|
| Point lookup | 1 read (more with overflow chains) | 1 bucket read + directory | 1 read, sometimes an overflow page | height of the tree, about 3–4 reads |
| Growth | rehash the whole file | split one bucket, sometimes double the directory | split buckets in a fixed round-robin order | split one page |
| Extra structure | none | directory of 2g pointers | none | inner nodes |
| Range queries | no | no | no | yes |
Like any hash index, it only answers equality lookups: neighbouring keys land in unrelated buckets, so WHERE k BETWEEN 10 AND 20 needs a B+ tree. Extendible hashing was published by Fagin, Nievergelt, Pippenger and Strong in 1979 and is the disk hash index in most database textbooks. PostgreSQL's hash index uses a related scheme with bucket splits and overflow pages, and the same directory idea appears in file systems and in-memory tables that must grow without long pauses.
See also Open Hash Tables and Closed Hash Tables, using buckets for fixed-size tables, Cuckoo Hashing for another table with a worst-case lookup bound, B+ Tree for the disk index that also answers range queries, and PostgreSQL index types for a hash index in a real database.
Linear hashing grows the same kind of file without a directory, splitting buckets in a fixed order.
What the page leaves out
Delete, and merging two buddy buckets whose keys fit in one, then halving the directory when every bucket has d < g (many systems never shrink); overflow pages for keys with equal hashes; using the high-order bits instead of the low-order bits (some textbooks, such as Elmasri and Navathe, do that; the idea is the same); a real hash function on strings; bucket pages with hundreds of keys; the directory itself spilling to several disk pages; locking and concurrency; and linear hashing, which grows without a directory.
See where this page fits on the Indexing mind map.