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
| Organization | How records are placed | Find one record by key | Insert | Good for |
|---|---|---|---|---|
| Heap (unordered) | wherever there is space, usually at the end | linear scan: about b/2 blocks on average, b if absent | very cheap | bulk loading, tables read fully |
| Sequential (sorted) | in order of a key | binary search: log₂ b blocks | costly — must keep order (an overflow area helps) | range queries and ordered reports |
| Hash | block chosen by a hash function on the key | about 1 block | cheap | exact-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]
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:
- 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.
- 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 in00; 10 (1010) ends in10. - 7 and 3 share the odd bucket. It keeps local depth 1, so entries
01and11both point to it. - Key 12 (
1100) goes to00, 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.
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 index | B+ tree index | |
|---|---|---|
WHERE roll = 1042 | about 1 block read | about 3–4 block reads (tree height) |
WHERE cgpa BETWEEN 8 AND 9 | useless — must scan | follow the leaf chain in order |
ORDER BY roll | no help | rows already in order |
| Growth | needs dynamic hashing | grows 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.