Static and Extendible Hashing

Hash indexes

An index helps the database find rows without scanning the whole table. A B+ tree keeps keys sorted and supports range queries. A hash index instead sends each key straight to a bucket (a disk page) computed from its hash, like a hash table on disk. Equality lookups (WHERE id = 42) take about one disk read. Range queries get no help.

The hard part is growth. What happens when buckets fill up?

Static hashing

Fix the number of buckets N, and put key k in bucket h(k) mod N. When a bucket is full, chain an overflow page behind it. As the data grows, chains get longer and every lookup in that bucket reads more pages. Rebuilding with a bigger N means rehashing every record, which is far too expensive for a busy database.

Extendible hashing

Add one level of indirection: a directory of 2^g pointers to buckets.

• Global depth g: the directory uses the last g bits of the hash to pick an entry. Some books use the first bits instead, and the idea is the same.
• Local depth d (one per bucket): the bucket’s keys agree on their last d bits. Several directory entries, 2^(g − d) of them, may share one bucket.

Inserting key k:

1. Follow entry (last g bits of h(k)) to its bucket. If there’s room, store k. Done.
2. If the bucket is full and d < g: split the bucket. Make a new bucket, give both local depth d + 1, and move the keys whose bit d + 1 is 1. Repoint half of the entries that pointed to the old bucket.
3. If the bucket is full and d = g: first double the directory (g + 1, each entry copied, no keys moved), then split as in step 2.
4. Try k again. A very uneven split may need another round.

Worked example

Each bucket holds 2 keys. We start with g = 1 and two buckets, then insert 4, 9, 6, 13, 2, 11, 10, 20.

Final: 8 directory entries, 5 buckets, and every lookup takes one directory step plus one bucket read.

Strengths and weaknesses

• Graceful growth. Only the full bucket splits, and the directory doubles rarely. Doubling copies only pointers, never records.
• Fast lookups. The directory usually fits in memory, so a lookup costs one disk read.
• Skewed keys hurt. Keys that share many low-order bits, such as 0, 8, 16 and 24, force repeated doublings, and the directory can grow huge.
• Linear hashing, a related scheme, avoids the directory altogether by splitting buckets in a fixed round-robin order.

Code

CAP = 2                                    # keys per bucket

class Bucket:
    def __init__(self, depth):
        self.depth, self.keys = depth, []

def insert(directory, g, k):
    """Insert key k; return the (possibly doubled) directory and global depth."""
    while True:
        b = directory[k & ((1 << g) - 1)]      # use the last g bits
        if len(b.keys) < CAP:
            b.keys.append(k)
            return directory, g
        if b.depth == g:                       # no spare bit: double the directory
            directory, g = directory + directory, g + 1
        b.depth += 1                           # split on one more bit
        new, bit = Bucket(b.depth), 1 << (b.depth - 1)
        for j, x in enumerate(directory):
            if x is b and j & bit:
                directory[j] = new
        b.keys, new.keys = [x for x in b.keys if not x & bit], [x for x in b.keys if x & bit]

directory, g = [Bucket(1), Bucket(1)], 1
for k in [4, 9, 6, 13, 2, 11, 10, 20]:
    directory, g = insert(directory, g, k)
for i, b in enumerate(directory):
    print(f'{i:0{g}b} -> depth {b.depth}: {b.keys}')
# 000 -> depth 2: [4, 20]
# 001 -> depth 2: [9, 13]
# 010 -> depth 3: [2, 10]
# 011 -> depth 2: [11]
# 100 -> depth 2: [4, 20]
# 101 -> depth 2: [9, 13]
# 110 -> depth 3: [6]
# 111 -> depth 2: [11]

Common mistakes

• Doubling the directory on every split. Only when the full bucket’s local depth equals g.
• Mixing up global and local depth. g belongs to the directory, d to each bucket, and d ≤ g always.
• Forgetting shared buckets. After a doubling, pairs of entries point to the same bucket until it splits.
• Switching between first and last bits. Pick one convention and use it everywhere.
• Expecting range queries. A hash index scatters neighbouring keys. Use a B+ tree for ranges.