Lesson 24: Data Storage and File Organisation¶
The memory hierarchy, records, blocks and file organisations
About this lesson
Course: Database Management Systems
Unit 6: Data Storage and Indexes · 4 Lecture Hours
Lesson duration: 1 lecture
Reading: Elmasri & Navathe, Ch. 16
Learning Outcomes
- Describe the memory hierarchy and explain why disk access dominates database cost.
- Define block, blocking factor and record, and compute them.
- Distinguish fixed-length from variable-length records and spanned from unspanned blocking.
- Compare heap, sorted and hashed file organisations on each operation.
- Choose an organisation for a stated workload.
24.1 The Memory Hierarchy¶
capacity access time cost/byte
+--------------------+
| CPU registers | ~KB < 1 ns highest
+--------------------+
| Cache (L1/L2/L3) | MB 1-10 ns
+--------------------+
| Main memory (RAM) | GB ~100 ns PRIMARY
+====================+ ============================== volatile
| Flash / SSD | TB ~100 us SECONDARY
+--------------------+ non-volatile
| Magnetic disk | TB ~10 ms
+--------------------+
| Optical / tape | PB seconds TERTIARY
+--------------------+ lowest cost
MAIN MEMORY to DISK is roughly a 100,000-fold jump in access time.
That single gap dictates almost every design decision in this unit.
Figure 1.1 — The memory hierarchy.
Primary, secondary, tertiary
Primary storage — directly accessible by the CPU: registers, cache, main memory. Fast but volatile (contents lost on power failure) and expensive per byte.
Secondary storage — disks and SSDs. Non-volatile, far larger, far cheaper, and roughly five orders of magnitude slower. The database lives here.
Tertiary storage — tape and optical libraries, used for archives and backups.
Why databases are designed around disk
A main-memory access takes about 100 nanoseconds; a magnetic disk access about 10 milliseconds. The ratio is roughly 100,000 : 1.
If a memory access were one second, a disk access would take over a day.
Consequently the cost of a database operation is measured in block accesses, not in CPU instructions. An algorithm doing twice the computation but half the I/O wins easily. Every structure in this unit — indexes, B+-trees, hashing, the buffer pool — exists to reduce the number of block accesses.
Disk geometry and access time¶
A magnetic disk consists of platters with concentric tracks, divided into sectors; the set of tracks at the same radius across all platters is a cylinder.
Access time = seek time + rotational latency + transfer time
| Component | What it is | Typical |
|---|---|---|
| Seek time | Moving the arm to the right track | 3–10 ms — dominant |
| Rotational latency | Waiting for the sector to arrive under the head | ~4 ms (half a rotation at 7200 rpm) |
| Transfer time | Reading the bytes | < 1 ms per block |
Since seek time dominates, reading blocks that are physically adjacent is far cheaper than reading scattered blocks. This is why clustering related records together matters, and why a sequential scan of a whole file can be faster than an index lookup that touches many scattered blocks.
SSDs have no moving parts, so seek time nearly vanishes and random access is far cheaper. They do not eliminate the memory–storage gap, but they change the balance: index-based random access becomes relatively more attractive.
24.2 Records and Blocks¶
Definitions
Record — a collection of related field values, corresponding to one tuple.
Block (page) — the unit of transfer between disk and main memory, typically 4 KB or 8 KB. You cannot read a single byte or a single record from disk — you read a whole block.
Blocking factor bfr — the number of records that fit in one block.
bfr = floor( B / R ) where B = block size, R = record size.
Blocks needed for r records: b = ceil( r / bfr ).
Worked calculation¶
A STUDENT file has r = 30,000 records, record size R = 100 bytes, block size B = 1024 bytes.
bfr = floor(1024 / 100) = 10 records per block.
b = ceil(30000 / 10) = 3000 blocks.
Unused space per block = 1024 − 10 × 100 = 24 bytes, so about 2.3 per cent is wasted.
Spanned vs unspanned
Unspanned — a record never crosses a block boundary. Simple, and a record is retrieved in one block access, but space is wasted at the end of each block. Required when R > B is impossible.
Spanned — a record may be split across two blocks, with a pointer to the continuation. No wasted space, and necessary when R > B, but a record may need two block accesses.
Fixed-length records are usually unspanned; large variable-length records are usually spanned.
Fixed-length and variable-length records¶
Fixed-length — every record occupies the same number of bytes, so the address of record i is computable arithmetically: start + i × R. Direct access is trivial and deletion can use a simple free list.
Variable-length records arise when a table has VARCHAR fields, optional fields, repeating fields, or several record types in one file. Three techniques identify the field boundaries:
- Separator characters between fields;
- Length prefixes before each field;
- A field-offset table (a directory) at the start of the record — the usual modern choice, since it also gives direct access to any field.
Deletion and fragmentation
Deleting a record leaves a hole. Two strategies:
Deletion marker (tombstone) — a flag byte marks the record as deleted; the space is reused later. Cheap, but the file grows with dead space until reorganised.
Compaction — records are shifted to close the gap. No wasted space, but expensive, and it invalidates any stored record addresses.
Most systems use tombstones plus periodic reorganisation, which is why a table that has had many deletions may need OPTIMIZE TABLE or VACUUM.
24.3 File Organisations¶
File organisation vs access method
The file organisation is how records are physically arranged on disk. The access method is the set of operations that can be applied to it. One organisation may support several access methods, and the same access method may work over several organisations.
Heap (unordered / pile) file¶
Records are appended at the end of the last block, in no particular order.
| Operation | Cost | Explanation |
|---|---|---|
| Insert | 1–2 block accesses | Read the last block, add the record, write it back. Very efficient. |
| Search (any field) | b/2 average, b worst |
A linear search of every block. |
| Delete | search + 1 | Find the block, mark or remove, rewrite. Leaves dead space. |
| Ordered retrieval | must sort the whole file | Very expensive. |
Use when: the file is small; the workload is insert-heavy; whole-file scans are the normal access pattern (as in bulk loading, or a staging table).
Do the arithmetic
With b = 3000 blocks and 10 ms per block access, a linear search averages 1500 × 10 ms = 15 seconds for one record. This is why indexes exist (Lesson 2).
Sorted (sequential) file¶
Records are kept physically ordered on the value of an ordering field. If that field is also a key, it is the ordering key.
| Operation | Cost | Explanation |
|---|---|---|
| Search on the ordering field | log₂ b | Binary search over the blocks. |
| Search on any other field | b/2 average |
No better than a heap — the order does not help. |
| Range query on the ordering field | log₂ b + the matching blocks | Excellent — matching records are contiguous. |
| Ordered retrieval | b, no sort needed |
The file is already in order. |
| Insert | very expensive | On average half the file must be shifted to keep the order. |
| Delete | search + rewrite | Usually a deletion marker. |
With b = 3000, a binary search costs log₂ 3000 ≈ 12 block accesses instead of 1500 — a 125-fold improvement, but only for the ordering field.
The insertion problem, and how it is solved
Keeping a file physically sorted on every insert is unaffordable. Real systems use an overflow (transaction) file: new records go into a small unordered overflow area, which is periodically merged with the main file during reorganisation.
Searches must then check both the sorted main file and the overflow area, so performance degrades between reorganisations. This awkwardness is exactly why B+-trees (Lesson 2) displaced sorted files in practice: they keep the logical order while tolerating insertions gracefully.
Hashed file¶
A hash function h maps a field value (the hash field) to a bucket number — a block or small group of blocks.
h(Rollno) = Rollno mod 5
'X2019' -> numeric 2019 -> 2019 mod 5 = 4 -> bucket 4
'X2020' -> 2020 mod 5 = 0 -> bucket 0
+----------+ +----------+ +----------+ +----------+ +----------+
| bucket 0 | | bucket 1 | | bucket 2 | | bucket 3 | | bucket 4 |
+----------+ +----------+ +----------+ +----------+ +----------+
| X2020 | | | | X2017 | | X2018 | | X2019 |
| X2025 | | | | | | | | X2024 |
+----+-----+ +----------+ +----------+ +----------+ +----+-----+
| |
v overflow chain when a bucket fills v
+----------+ +----------+
| X2030 | | X2029 |
+----------+ +----------+
| Operation | Cost | Explanation |
|---|---|---|
| Equality search on the hash field | 1 block access (plus overflow) | Compute h, go straight to the bucket. The fastest possible. |
| Range search | b — useless |
A good hash function scatters nearby values, so ranges are meaningless. |
| Search on any other field | b/2 |
Linear scan. |
| Insert | 1–2 | Compute, write. |
| Ordered retrieval | must sort | Very expensive. |
Collisions and overflow
Two values may hash to the same bucket — a collision. Resolution methods:
- Open addressing — place the record in the next free bucket.
- Chaining — keep an overflow chain of extra blocks per bucket. Most common.
- Multiple hashing — apply a second hash function.
Performance degrades as chains lengthen, so a load factor of about 70–80 per cent is targeted.
Static vs dynamic hashing
Static hashing fixes the number of buckets in advance. If the file grows, chains lengthen and performance collapses; if it shrinks, space is wasted. A full rehash is then needed.
Dynamic hashing — extendible and linear hashing — grows and shrinks the bucket space incrementally, avoiding a total rehash. This is what real systems use.
Comparison — the table to memorise¶
| Operation | Heap | Sorted | Hashed |
|---|---|---|---|
| Insert | best (1–2) | worst (shift) | good (1–2) |
| Equality search on the key field | poor (b/2) |
good (log₂ b) |
best (1) |
| Search on a non-key field | poor (b/2) |
poor (b/2) |
poor (b/2) |
| Range query | poor (b) |
best | worst (useless) |
| Ordered retrieval | poor (sort) | best (free) | poor (sort) |
| Delete | fair | fair | good |
Choosing — match the organisation to the workload
- Mostly inserts, rarely searched (a log or audit table) → heap.
- Frequent exact lookups by a key (
WHERE Rollno = 'X2019') → hashed. - Frequent range and ordered queries (
WHERE Dateofadmission BETWEEN ...,ORDER BY) → sorted, or in practice a B+-tree index (Lesson 2), which gives sorted-file behaviour without the insertion penalty. - Mixed workload → a heap file with B+-tree indexes on the queried columns. This is what almost every real DBMS does by default.
24.4 Solved Questions¶
Solved Question 1
Q. Describe the memory hierarchy. Why is database performance measured in block accesses rather than instructions?
A. (Diagram: Figure 1.1.) From fastest and smallest to slowest and largest: registers, cache, main memory (all primary, volatile, CPU-addressable); flash/SSD and magnetic disk (secondary, non-volatile, where the database resides); optical and tape (tertiary, for archives).
Why block accesses are the unit of cost. The step from main memory to disk is a jump of roughly five orders of magnitude — about 100 nanoseconds against about 10 milliseconds, a ratio near 100,000:1. Any operation that touches disk is dominated by that cost; the CPU work done in between is negligible by comparison.
Two consequences follow, and they shape the whole unit:
- Algorithms are compared by the number of block accesses they require. An algorithm doing more computation but fewer I/Os wins. A linear search of 3000 blocks costs about 15 seconds; a B+-tree lookup of 3 blocks costs 30 milliseconds — a 500-fold difference that no amount of CPU tuning could produce.
- Data is transferred a whole block at a time, never a byte or a record. So the design goal is to arrange records so that the ones needed together arrive in the same block — which is what clustering, indexing and the buffer pool all address.
Solved Question 2
Q. A file has 50,000 records of 200 bytes each; the block size is 2048 bytes. Compute the blocking factor and the number of blocks, unspanned. How much space is wasted? Recompute if spanned.
A.
Unspanned.
bfr = floor(B / R) = floor(2048 / 200) = floor(10.24) = **10** records per block.
b = ceil(r / bfr) = ceil(50000 / 10) = **5000** blocks.
Wasted space per block = 2048 − (10 × 200) = 48 bytes.
Total waste = 5000 × 48 = 240,000 bytes ≈ 234 KB, which is 48/2048 = **2.34 per cent**.
Spanned. No space is wasted, so the space needed is exactly the data:
total = 50000 × 200 = 10,000,000 bytes; b = ceil(10,000,000 / 2048) = **4883** blocks.
Saving: 117 blocks, about 2.3 per cent.
The trade-off. Spanning saves 2.3 per cent of the space, but a record split across a boundary needs two block accesses instead of one. Given that block accesses are the dominant cost (question 1), sacrificing up to 2× on some retrievals to save 2 per cent of cheap disk is a poor bargain.
Conclusion: for fixed-length records of this size, unspanned is correct. Spanning is justified when records are large relative to the block (so the waste would be substantial) or when R > B, which makes spanning unavoidable.
Solved Question 3
Q. Compare heap, sorted and hashed file organisations on insertion, equality search, range search and ordered retrieval. Recommend one for each of three workloads.
A. (Comparison table of Section 1.3.) Summarising the reasoning behind each entry:
Heap. Insertion is a simple append — read the last block, write it back — so 1–2 accesses. But there is no structure to exploit, so any search is a linear scan averaging b/2 blocks, and ordered retrieval requires sorting the whole file.
Sorted. Because records are physically ordered on the ordering field, a binary search finds a record in log₂ b accesses, ranges are contiguous, and ordered retrieval is free. But maintaining the order on insertion requires shifting on average half the file — prohibitive, which is why real systems use an overflow area and periodic reorganisation.
Hashed. The hash function computes the bucket directly, giving a single block access for an equality search on the hash field — the best possible. But a good hash function deliberately scatters nearby values, so range queries and ordered retrieval are useless.
Recommendations.
| Workload | Choice | Reason |
|---|---|---|
| An audit log: constant appends, read only in bulk | Heap | Insertion is optimal and full scans are the access pattern anyway. |
A lookup table queried only as WHERE Rollno = ? |
Hashed | One block access per lookup; ranges are never needed. |
| A transactions table queried by date ranges and reported in date order | Sorted — in practice a B+-tree index | Ranges are contiguous and ordering is free; the B+-tree provides this without the insertion penalty. |
In practice most tables are heap files with B+-tree indexes on the queried columns, which combines cheap insertion with fast search.
Solved Question 4
Q. Explain hashing, collisions and overflow handling. Why is hashing unsuitable for range queries?
A. In a hashed file, a hash function h maps the value of a chosen hash field to a bucket address. To store or find a record, the system computes h(value) and goes directly to that bucket — one block access, with no search.
A collision occurs when two different field values hash to the same bucket. Collisions are unavoidable: the space of possible key values is far larger than the number of buckets. Three resolution methods:
- Open addressing — scan forward to the next free bucket. Simple, but causes clustering that degrades later searches.
- Chaining — each bucket has a pointer to an overflow chain of additional blocks. The most common method; searching a bucket means following its chain.
- Multiple hashing — apply a second hash function to place the colliding record elsewhere.
Because chain length determines search cost, a load factor of roughly 70–80 per cent is targeted, and dynamic hashing (extendible or linear) is used so the bucket space can grow without a total rehash.
Why range queries fail. A good hash function is designed to distribute values uniformly and unpredictably — that is precisely what avoids collisions. As a direct consequence, values that are close together are scattered to unrelated buckets. Rollno X2019 and X2020 may land in buckets 4 and 0.
So WHERE Rollno BETWEEN 'X2019' AND 'X2050' cannot be answered by visiting a few buckets: the qualifying records could be anywhere, and every bucket must be scanned — cost b, worse than a heap file, since the overflow chains must be followed too.
The same argument rules out ORDER BY and MIN/MAX on the hash field. Hashing is for equality, never for order. Where both are needed, a B+-tree index is the right structure.
Solved Question 5
Q. A file of 3000 blocks is searched for one record. Compute the cost under heap, sorted (on the search field) and hashed organisations, at 10 ms per block access. Comment.
A.
| Organisation | Block accesses | Time | Reasoning |
|---|---|---|---|
| Heap | 1500 average, 3000 worst | 15 s average | Linear scan; on average half the file is read before the record is found. |
| Sorted on the search field | log₂ 3000 ≈ 12 |
0.12 s | Binary search halves the search space each step. |
| Hashed on the search field | 1 (plus overflow) | 0.01 s | The bucket address is computed directly. |
| Sorted or hashed, but searching a different field | 1500 average | 15 s | Neither structure helps for a field it is not organised on. |
Comments.
-
The improvement from heap to sorted is 125-fold; from heap to hashed, 1500-fold. No amount of faster CPU or better code approaches this — the structure of the file is what matters.
-
The organisation helps only for the field it is built on. A file sorted on
Rollnogives no benefit whatever toWHERE Name = 'Ankit Sharma'. Since a file can be physically organised on only one field, all other access paths need indexes (Lesson 2) — which is exactly why indexes exist. -
The figures assume magnetic disk. On an SSD each access might cost 0.1 ms, so the heap search falls to 0.15 s — still 15 times worse than the sorted file and 150 times worse than hashing. Faster hardware narrows the absolute gap but not the ratio.
Solved Question 6
Q. Distinguish fixed-length from variable-length records. Give three techniques for identifying field boundaries in variable-length records, and explain how deletion is handled.
A.
Fixed-length records occupy the same number of bytes each. The address of record i is start + i × R, so direct access is a simple calculation, and the blocking factor is a constant. Space is wasted whenever a field is shorter than its allocated width.
Variable-length records arise from VARCHAR fields, optional fields that may be absent, repeating fields, or a file holding several record types. They save space but make the position of the ith record uncomputable, so a directory or index of record positions within each block is normally kept.
Three techniques for field boundaries:
- Separator characters — a reserved delimiter (say
|) between fields. Simple, but the delimiter must never occur in the data, and finding field k requires scanning from the start. - Length prefixes — each field is preceded by a byte or two giving its length. No reserved character is needed, but again access is sequential within the record.
- Field-offset table — a small directory at the head of the record giving the starting offset of each field. Costs a few bytes, but gives direct access to any field without scanning. This is the usual modern choice, and it also represents NULLs cleanly (by an offset equal to the next one).
Deletion. Two strategies:
- Deletion marker (tombstone) — a flag bit or byte marks the record as deleted, and the space is reused by a later insertion of a record that fits. Cheap and does not invalidate stored addresses, but the file accumulates dead space.
- Compaction — surviving records are shifted to close the gap. No waste, but expensive and it invalidates any stored record pointers, so indexes would have to be rebuilt.
Real systems use tombstones plus a free-space list, with periodic reorganisation to compact. This is why a heavily-updated table benefits from OPTIMIZE TABLE (MySQL) or VACUUM (PostgreSQL); without it, a table from which most rows have been deleted may still occupy its original space and still be slow to scan.
24.5 Exercises¶
A. Short answer
- Name the three levels of the storage hierarchy with an example of each.
- What is a block, and why is it the unit of transfer?
- Define blocking factor and give its formula.
- Distinguish spanned from unspanned blocking.
- Give the three components of disk access time and say which dominates.
- Why is a heap file good for insertion but poor for searching?
- Why can a hashed file not answer range queries?
B. Computation
- A file has 20,000 records of 150 bytes; the block size is 4096 bytes. Compute
bfr,b, and the wasted space per block and in total (unspanned). - Repeat for 1,000,000 records of 512 bytes and a block size of 8192 bytes.
- For the file in question 8, compute the average number of block accesses for a search under (a) heap, (b) sorted on the search field, (c) hashed on the search field.
- A record is 1500 bytes and the block size is 1024 bytes. What must be done, and why?
- A sorted file of 4096 blocks is binary-searched. How many block accesses? How many if the file doubles in size? Comment on the growth rate.
C. Analysis
- For each workload, choose a file organisation and justify:
a. A web-server access log, appended constantly and analysed monthly in bulk.
b. A table of country codes, looked up by exact code, never ranged.
c. A table of stock prices queried mostly as
WHERE date BETWEEN ... ORDER BY date. d. TheADMISSIONtable of our college database. - Explain why a sorted file is rarely used in practice despite its good search performance. What replaced it, and why?
- A hashed file has a load factor of 95 per cent and searches have become slow. Diagnose the problem and give two remedies.
- Explain why an organisation built on one field gives no benefit to queries on another. What is the consequence for database design?
- A table has had 90 per cent of its rows deleted, yet full scans are as slow as before. Explain why, and give the remedy.
- Compare magnetic disk and SSD on the three components of access time. Which file organisation becomes relatively more attractive on an SSD, and why?
D. Objective — True or False with reason
- A single record can be read from disk without reading its whole block.
- Rotational latency usually dominates disk access time.
- A heap file supports binary search.
- A hashed file gives the fastest possible equality search on the hash field.
- Spanned records always improve performance.
- Ordered retrieval from a sorted file requires a sort.
Answers to Section D
- False. The block is the unit of transfer; reading one byte costs a whole block access.
- False. Seek time (3–10 ms) usually dominates; rotational latency averages about 4 ms.
- False. Binary search requires the records to be ordered; a heap file must be searched linearly.
- True. One block access, computed directly — no search at all. Only overflow chains add to it.
- False. They save space but may require two block accesses for a record crossing a boundary. Since block accesses dominate cost, unspanned is usually better for small records.
- False. The file is already in order, so ordered retrieval is free — one of the sorted file's main advantages.
Lesson Summary
- The memory–disk gap of about 100,000:1 makes block accesses the unit of database cost.
bfr = floor(B/R);b = ceil(r/bfr). Unspanned wastes space but keeps one record in one block; spanned saves space at the cost of a second access.- Seek time dominates disk access, so physically adjacent blocks are far cheaper to read.
- Heap: best insertion, linear search. Sorted: binary search and free ordering, but crippling insertion cost. Hashed: one-access equality search, useless for ranges.
- Any organisation helps only for the field it is built on — which is why indexes are needed for every other access path.