File organization: heap, sorted, hashed; cost of search/insert/delete

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. r = 30,000, R = 100, B = 1024 (unspanned): bfr and b? from Lesson 5.1.1
2. What is the average rotational latency at 6,000 rpm? from Lesson 5.1.1
3. What is a candidate key? from Lesson 2.2.1

1 · The Hook

"Find the student with roll 21,407" in a 3,000-block file. Read every block? Jump straight to the right block? It depends on how the records were arranged when stored. The three basic file organisations trade fast search against fast inserts.

2 · Predict First

In a file sorted by roll, you can open the middle block, see whether 21,407 is before or after it, and throw away half the file each time. About how many block reads to find one roll among 3,000 blocks?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

About 12. Each read halves the remaining blocks: 3000 → 1500 → 750 → … → 1 takes about 12 halvings, because 2¹¹ = 2048 < 3000 ≤ 4096 = 2¹².

Halving and log₂ (mini primer)

log₂ x is the power of 2 that gives x: log₂ 1024 = 10 because 2¹⁰ = 1024. Repeatedly halving b blocks down to one takes about log₂ b steps; for whole steps use the ceiling ⌈log₂ b⌉: the smallest k with 2ᵏ ≥ b.

Heap (unordered) file

Records are placed wherever there is room, usually at the end.

• Search on a key: linear scan; b/2 block accesses on average if the record exists, b if it does not (or if the field is not a key, since all matches must be found).
• Insert: very cheap: read the last block, add, write back (constant).
• Delete: search, then mark the record deleted (space reclaimed later by reorganisation).

Sorted (ordered, sequential) file

Records are kept in order of an ordering field (often the key).

• Search on the ordering field: binary search on blocks: ⌈log₂ b⌉ accesses.
• Search on any other field: no help: linear, like a heap.
• Range search (roll between 1000 and 1200): binary search to the start, then read consecutive blocks.
• Insert / delete: expensive: records after the position must shift: about b/2 blocks read and written on average. Real systems use overflow areas and periodic reorganisation.

Hashed file

A hash function h(key) computes the bucket (block or group of blocks) where the record lives.

• Search on the hash key with equality (roll = 21407): about 1 block access (more if the bucket has overflow blocks chained to it).
• Range search or search on other fields: no help: hashing scatters neighbours.
• Insert / delete: about 1–2 accesses.

Summary

With b = 3,000: heap ≈ 1,500 accesses, sorted 12, hashed ≈ 1.

4 · Visual

Binary search over 3000 sorted blocks, looking for roll 21407

read block 1500 -> too low  -> keep 1501..3000
read block 2250 -> too high -> keep 1501..2249
read block 1875 -> ...
...                                  about 12 reads (2^12 = 4096 >= 3000)

5 · Worked Examples

Example 1 Easy

A heap file has 5,000 blocks. Average block accesses to find a record by its key, if it exists? If it does not exist?

Solution

2,500 on average; 5,000 if it does not exist.

Example 2 Medium

The same file sorted on the key. Block accesses for a binary search?

Solution

2¹² = 4096 < 5000 ≤ 8192 = 2¹³ → 13.

Example 3 GATE

A sorted file has 10,000 blocks; the sort field is roll. A query asks for all students whose name is 'Esha'. How many block accesses in the worst case?

Solution

The file is not sorted on name, so binary search is useless: 10,000 (every block must be read; a name is not a key).

8 · Connect the Dots

Lesson 5.1.1 counted blocks; this lesson counted block accesses for three file layouts. Next: an index, a small sorted file of pointers that gives sorted-file speed on any field, without sorting the data.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Heap

A heap file has 8,000 blocks. Average block accesses to find an existing record by key?

Numerical answer: ________

Q2 · NAT · 1 mark(s) — Binary search

A file sorted on the key has 1,000 blocks. Block accesses for binary search?

Numerical answer: ________

Q3 · MCQ · 1 mark(s) — Hashing

Which query does a hashed file on roll help with?

1. (A) roll BETWEEN 4000 AND 5000
2. (B) roll = 4501
3. (C) name = 'Asha'
4. (D) ORDER BY roll

Q4 · MCQ · 2 mark(s) — Insert cost

Which organisation makes inserts the most expensive?

1. (A) Hashed file
2. (B) Heap
3. (C) Sorted file
4. (D) All equal

Q5 · NAT · 2 mark(s) — Binary search

A file of 50,000 records, 25 records per block, sorted on the key. Block accesses for binary search?

Numerical answer: ________

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

log₂ (mini primer)heap filesorted (ordered) fileordering fieldbinary search on blocksrange searchhashed filehash functionbucketoverflow block