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

Source: https://skills101.in/learn/dbms-sql/dbms-file-organization-hashing — Skills101 free tutorial (DBMS & SQL). Updated 2026-11-21.

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:

```python
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)))
```

```text
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:

```python
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:]}')
```

```text
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](https://skills101.in/learn-img/dbms-sql/static-hashing.svg)

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):

```python
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)
```

```text
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](https://skills101.in/learn-img/dbms-sql/extendible-hashing.svg)

**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.


Practice quiz and free certificate: https://skills101.in/learn/dbms-sql/dbms-file-organization-hashing