Skills101

AdvancedDBMS & SQL · Lesson 24 of 25 · Updated ·

File Organization and Hashing — Heap, Sequential and Hash Files, Static and Extendible Hashing

Tables look like neat grids in SQL, but on disk they are just records packed into fixed-size blocks (also called pages). The disk reads and writes whole blocks, never single records, and a block read is thousands of times slower than work in memory. So the main question of file organization is: how many blocks must be read to find a record? This lesson covers the classic answers and the hashing techniques that university exams ask you to trace.

1. Records, blocks and the blocking factor

The blocking factor (bfr) is the number of records that fit in one block:

bfr = ⌊ block size / record size ⌋

For a students file with 10,000 records of 100 bytes each and 4,096-byte blocks:

import math

block, record, n = 4096, 100, 10_000
bfr = block // record
blocks = math.ceil(n / bfr)
print('records per block:', bfr)
print('blocks needed    :', blocks)
print('linear search, average blocks read:', blocks // 2)
print('binary search, worst blocks read  :', math.ceil(math.log2(blocks)))
records per block: 40
blocks needed    : 250
linear search, average blocks read: 125
binary search, worst blocks read  : 8

The floor is used because a record usually may not be split across two blocks (an unspanned organization); the 96 leftover bytes in each block are wasted.

2. Three ways to organise a file

OrganizationHow records are placedFind one record by keyInsertGood for
Heap (unordered)wherever there is space, usually at the endlinear scan: about b/2 blocks on average, b if absentvery cheapbulk loading, tables read fully
Sequential (sorted)in order of a keybinary search: log₂ b blockscostly — must keep order (an overflow area helps)range queries and ordered reports
Hashblock chosen by a hash function on the keyabout 1 blockcheapexact-match lookups (roll = 1042)

With b = 250 blocks: heap ≈ 125 reads, sorted = 8 reads, hash ≈ 1 read. But a hash file cannot answer cgpa BETWEEN 8 AND 9 efficiently, because the hash scatters neighbouring values across the file. That is why most database indexes are B+ trees, and hash indexes are used where only equality lookups are needed.

3. Static hashing

A hash file has M buckets (each bucket is one or more blocks). A hash function h maps a key to a bucket number, for example h(k) = k mod M. To find a record, compute h(k) and read that one bucket.

When a bucket is full, extra records go to an overflow block chained to it. Searching that bucket now needs extra reads. Here is M = 4, two records per bucket, with nine keys:

M, CAP = 4, 2
buckets = [[] for _ in range(M)]
for key in [12, 7, 20, 15, 33, 8, 28, 3, 44]:
    buckets[key % M].append(key)

for i, b in enumerate(buckets):
    print(f'bucket {i}: {b[:CAP]}  overflow: {b[CAP:]}')
bucket 0: [12, 20]  overflow: [8, 28, 44]
bucket 1: [33]  overflow: []
bucket 2: []  overflow: []
bucket 3: [7, 15]  overflow: [3]

Static hashing with h(k) = k mod 4: bucket 0 holds 12 and 20 and has an overflow chain with 8, 28 and 44, bucket 1 holds 33, bucket 2 is empty, bucket 3 holds 7 and 15 with 3 in overflow

Two problems are visible:

  • Skew: many keys here are multiples of 4, so they all land in bucket 0 while bucket 2 stays empty. A good hash function spreads keys evenly; choosing M as a prime number helps with patterns like this.
  • Fixed size: M is chosen when the file is created. If the file grows ten times, chains get long and lookups slow down. Rebuilding with a bigger M means rehashing every record — slow, and the table is unavailable meanwhile. If M is chosen too large, space is wasted.

Collision is the general word for two keys hashing to the same bucket; in a database, a bucket holds several records, so collisions are normal and only bucket overflow is a problem.

4. Extendible hashing (dynamic hashing)

Extendible hashing lets the file grow one bucket at a time. It adds a directory of 2^d pointers:

  • Global depth (d): the directory uses the last d bits of h(k) to choose an entry.
  • Local depth (d′) of each bucket: how many bits its keys really share. Several directory entries can point to the same bucket when d′ < d.

Inserting into a full bucket:

  1. If its local depth < global depth: split only that bucket into two, increase its local depth, and redistribute its keys on one more bit. Fix the directory pointers. The directory does not grow.
  2. If its local depth = global depth: first double the directory (global depth + 1; each new entry copies its partner's pointer), then split as in step 1.

Trace, with h(k) = k, two keys per bucket, starting from global depth 1 (one bucket for even keys, one for odd):

CAP = 2                                   # keys per bucket

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

def insert(directory, gd, key):
    while True:
        b = directory[key % (2 ** gd)]          # last gd bits of the key
        if len(b.keys) < CAP:
            b.keys.append(key)
            return directory, gd
        if b.depth == gd:                       # no spare bit: double the directory
            directory = directory + directory
            gd += 1
        bit = b.depth                           # split the full bucket on one more bit
        b0, b1 = Bucket(bit + 1), Bucket(bit + 1)
        for k in b.keys:
            (b1 if (k >> bit) & 1 else b0).keys.append(k)
        for i in range(len(directory)):
            if directory[i] is b:
                directory[i] = b1 if (i >> bit) & 1 else b0

def show(directory, gd):
    print('global depth', gd)
    for i, b in enumerate(directory):
        print(f'  {i:0{gd}b} -> local depth {b.depth}: {sorted(b.keys)}')

directory, gd = [Bucket(1), Bucket(1)], 1
for key in [4, 7, 10, 8, 3]:
    directory, gd = insert(directory, gd, key)
show(directory, gd)
directory, gd = insert(directory, gd, 12)
show(directory, gd)
global depth 2
  00 -> local depth 2: [4, 8]
  01 -> local depth 1: [3, 7]
  10 -> local depth 2: [10]
  11 -> local depth 1: [3, 7]
global depth 3
  000 -> local depth 3: [8]
  001 -> local depth 1: [3, 7]
  010 -> local depth 2: [10]
  011 -> local depth 1: [3, 7]
  100 -> local depth 3: [4, 12]
  101 -> local depth 1: [3, 7]
  110 -> local depth 2: [10]
  111 -> local depth 1: [3, 7]

What happened:

  • 4 and 10 fill the even bucket. Key 8 finds it full with local depth 1 = global depth 1, so the directory doubles to 4 entries and the even bucket splits on bit 1: 4 (100) and 8 (1000) end in 00; 10 (1010) ends in 10.
  • 7 and 3 share the odd bucket. It keeps local depth 1, so entries 01 and 11 both point to it.
  • Key 12 (1100) goes to 00, which is full with local depth 2 = global depth 2: the directory doubles again to 8 entries, and only that bucket splits, on bit 2.

Extendible hashing after inserting 12: a directory of 8 entries with global depth 3 points to four buckets; the odd bucket with 3 and 7 has local depth 1 and is shared by four entries, the bucket with 10 has local depth 2 and is shared by two entries, and the buckets with 8 and with 4 and 12 have local depth 3

Number of directory entries pointing to a bucket = 2^(d − d′). For the odd bucket: 2^(3 − 1) = 4 entries.

Advantages: no long overflow chains, growth without rehashing the whole file, one directory lookup plus one bucket read. Disadvantages: the directory doubles even when only one bucket is crowded, and keys with many identical low bits (like 4, 12, 20, 28) can force repeated doubling.

Linear hashing is another dynamic scheme: it has no directory and splits buckets in a fixed round-robin order, using overflow chains for a while until each bucket's turn comes.

5. Hashing vs B+ tree index

Hash indexB+ tree index
WHERE roll = 1042about 1 block readabout 3–4 block reads (tree height)
WHERE cgpa BETWEEN 8 AND 9useless — must scanfollow the leaf chain in order
ORDER BY rollno helprows already in order
Growthneeds dynamic hashinggrows naturally by splitting nodes

PostgreSQL offers CREATE INDEX ... USING HASH; MySQL's InnoDB uses B+ trees for normal indexes; hash joins (in the query optimization lesson) build temporary hash tables in memory.

Common mistakes

  • Using ceiling for the blocking factor. Records per block is the floor; number of blocks is the ceiling.
  • Saying a hash file supports range queries efficiently. It supports equality search only.
  • In extendible hashing, doubling the directory on every split. Double only when the bucket's local depth equals the global depth.
  • Reading the first bits of the binary key when the method (as here) uses the last bits. Check which convention your textbook uses; some use the leading bits.
  • Forgetting that after the directory doubles, the new half points to the same buckets as the old half until a split changes them.

Quick recap

  • bfr = ⌊block size / record size⌋; blocks = ⌈n / bfr⌉.
  • Heap: cheap insert, b/2 average search. Sorted: log₂ b binary search, good for ranges. Hash: about 1 read for equality.
  • Static hashing: h(k) mod M buckets; growth causes overflow chains; skewed keys overload buckets.
  • Extendible hashing: directory of 2^d entries, buckets with local depth d′; split one bucket, double the directory only when d′ = d.
  • Hash indexes for equality, B+ trees for ranges and ordering.

Practice what you learned

📝 Quiz: File Organization and Hashing5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →