File organization: pages, heaps, sorted files and hashing
Goals and the physical model
Logical relations do not promise a physical row order. File organization decides where records live; an access path decides how a query finds them. Learn to distinguish comparisons in memory from page transfers, calculate capacity, and choose a layout for an explicitly stated workload. Prerequisite: keys and relational selection. Index structures follow in lessons 11–12.
Our exercise model has fixed-size disk pages, fixed-size records unless stated, and initially empty buffers. One page read counts as one I/O, regardless of how many records on that page are inspected. CPU comparisons, seek time, prefetch, logging, directory traversal and output writes are excluded unless specified. This is a cost model, not a prediction that an SSD and a hard disk have equal latency. A cached page causes no additional disk read. Always declare whether a quoted cost includes data pages as well as index pages.
1. Capacity and record placement
Let B be page bytes, H fixed page-header bytes, R record bytes and N records. With unspanned records, a record cannot cross a page boundary, so capacity bfr=floor((B−H)/R), and a packed file needs b=ceil(N/bfr) pages. Rounding inside this formula matters. For B=4096, H=96, R=150 and N=1000, usable space is 4000 bytes, bfr=26 and b=39. The first 38 full pages hold 988 records; the last holds 12. A full page leaves 100 unused bytes; that waste cannot be borrowed by another page under this model.
If each record also needs a 4-byte slot, capacity instead solves 150n+4n≤4000, giving 25 records. A slotted page stores stable slot identifiers pointing to current record locations. Moving bytes within a page can preserve a record identifier (page number, slot number) if its slot entry is updated. Moving the record to another page needs further indirection or reference maintenance. Variable-sized records require actual sizes, slot overhead and free space; blindly using the largest or average record length is not an exact capacity calculation.
For explicitly spanned records, contiguous payload can cross page boundaries. With no per-record fragmentation overhead and 4000 payload bytes per page, the 150000-byte example requires ceil(150000/4000)=38 pages. A split record may require two reads. Account for all page headers and fragment overhead before using this payload formula; do not use it for unspanned placement.
2. Heap files: place where space exists
A heap has no search-key ordering. A free-space directory can identify a page with room, making insertion cheap when that directory is cached. This does not make arbitrary equality search cheap. Without another access path, finding a missing key requires reading all b pages. For one uniformly located existing unique key, a linear scan reads (b+1)/2 pages on average when every page is equally likely to contain the target. This assumption is approximate if the final page is much less full. If all matching rows must be returned for a nonunique predicate, continue scanning even after finding the first match.
Worked workload: a 500-page heap receives many new rows and occasional reports that read the entire relation. Appending or reusing free space fits the workload; a report reads 500 pages. An unindexed equality query cannot use binary search merely because its attribute is numeric. If a RID is already known and valid, fetching that record needs its page, typically one uncached page read, rather than searching the heap.
3. Sorted files: order helps ranges
A sorted file is maintained in search-key order. With directly addressable pages and usable boundary comparisons, binary search locates the first candidate page in logarithmic page reads. Say “about ceil(log2 b)” for an estimate; exact worst-case probe counts depend on the binary-search algorithm and whether the task seeks an exact record or a lower bound. Once the first qualifying page is located, an interval is scanned sequentially. If that first page was already read during search, the answer spans k contiguous data pages, and the other k−1 answer pages are still uncached, add k−1 further reads, not k.
In a worked instance, an explicitly supplied lower-bound search takes 9 reads including the first answer page, and the result occupies 12 consecutive pages. The other 11 answer pages are still uncached. Total is 9+11=20 reads. This is why sorted placement helps ranges. Insertion is more difficult: keeping a tightly packed physical sequence may shift many records or pages. Overflow areas reduce immediate movement but long overflow chains weaken the original locality and may require later reorganization. Deletion can mark space reusable; compacting and reordering are separate operations.
4. Hash-organized files: equality and collisions
A hash function maps a search key to a bucket. Different keys can share a bucket; equality must still be checked against stored keys. In a static hash file, growth can cause overflow chains. An exact-key lookup normally reads the target bucket and any required overflow pages. It is not guaranteed to cost one I/O, and absent-key search may traverse the entire chain. An ordinary hash function does not preserve order, so a numeric interval generally cannot be answered by reading adjacent hash buckets.
Original trace: h(k)=k mod 4; each bucket page holds two records. Insert 1,5,9,2,6. Bucket 1's primary page has 1,5 and its overflow page has 9; bucket 2 has 2,6. With directory information cached and neither data page cached, searching 9 takes two reads. Searching absent 13 also takes two reads to exhaust bucket 1. Searching 6 takes one read. Skew can be severe even when the file as a whole has free space.
Dynamic hashing changes the bucket structure as the file grows. In extendible hashing, a directory indexed by a chosen prefix or suffix of hash bits has global depth d and 2^d entries; each bucket has a local depth no greater than d. A bucket split increases its local depth; the directory doubles only when splitting a bucket whose local depth equals global depth. Several directory entries may reference the same bucket. These are supporting concepts, not a claim that every hash-file question assumes extendible hashing.
5. Choosing and checking an answer
Heap favors inexpensive placement and full scans; sorted placement favors ordered scans and ranges; hashing favors equality when distribution and overflow behavior are suitable. Workload, buffering, growth and maintenance determine the best choice. An index can be added to a heap: “heap” does not mean “indexes forbidden.” Physical ordering on one key does not automatically order another key.
Before computing, list page size and overhead, spanning rule, record count, cache state, predicate type, whether every match is needed, and whether reads and writes are both counted. Avoid mixing a count of records with a count of pages. A scan of 10000 records stored in 250 pages is 250 page reads, not 10000, under a cold sequential-read model.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. A page has 4096 bytes with a 96-byte header. Unspanned records are 150 bytes, with no slots. How many pages hold 1000 records?
A. 38 B. 39 C. 40 D. 26
Answer: B
A: 38 uses spanned payload arithmetic, forbidden here.
B: Capacity is floor(4000/150)=26; ceil(1000/26)=39.
C: 40 is not the minimum packed allocation.
D: 26 is records per page, not pages.
P02. A cold 120-page heap has no index. To establish that a key is absent, how many data-page reads are required in the worst case?
A. 1 B. 7 C. 60 D. 120
Answer: D
A: No key-to-page map is given.
B: Binary search requires an order not given here.
C: Half-file average does not prove absence.
D: Every page may need checking.
P03. A sorted-file search costs 8 reads including the first qualifying page. Results occupy 5 consecutive pages. The other four result pages are still uncached. Total reads?
A. 12 B. 13 C. 40 D. 8
Answer: A
A: The other four answer pages add four reads: 8+4.
B: This double-counts the first answer page.
C: Search is not repeated for each result page.
D: Four further answer pages remain.
P04. For h(k)=k mod 4 and two records per bucket page, keys 1,5,9 occupy bucket 1 and one overflow page. Cold search for absent 13 reads how many pages, with directory cached?
A. 0 B. 1 C. 2 D. 4
Answer: C
A: Computing a hash does not prove absence.
B: The primary page alone is insufficient.
C: Both primary and overflow pages must be inspected.
D: Only the target bucket chain is needed.
P05. Which organization directly preserves search-key order for interval scans?
A. Heap B. Ordinary hash file C. Sorted file D. Every organization
Answer: C
A: Heap has no promised search-key order.
B: Ordinary hashing does not preserve numeric order.
C: Sorted placement keeps nearby keys together in the stated model.
D: Logical relation semantics impose no such order.
P06. In extendible hashing, a full bucket has local depth 2 while global depth is 3. Its ordinary split requires which directory change?
A. Always double to 16 entries B. Keep 8 entries and update relevant pointers C. Shrink to 4 entries D. Set local depth to 4
Answer: B
A: Directory doubling is not required when local depth is smaller.
B: Existing directory bits distinguish the split; local depth becomes 3.
C: An insertion split does not require shrinking.
D: One split increases this local depth from 2 to 3.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Databases syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in