Heap Files

A heap file (also called an unordered file) is a file organization in which records are placed on disk blocks in no particular order relative to any attribute value. The only structural rule is: a record lives entirely within one block (assuming no record spans blocks, the common case for fixed or moderately sized variable-length records), and the file grows by allocating new blocks when existing ones fill up. There is no sort key, no key-based clustering, and no index built into the file itself — a heap file is what you get when a table is created with nothing else specified. The design goal is to make insertion as cheap as possible: find any block with free space, write the record there, done. This is contrasted with a sorted file, which must maintain an order and therefore may need to shift records on insertion, and with indexed/hashed files, which impose extra structure to accelerate search at some cost in maintenance. The heap file sacrifices search speed for this insertion speed and for structural simplicity: because records can be anywhere, answering "find all records with `age = 30`" requires inspecting every block — there is no shortcut. Three operations define the interface of a heap file, and each has a distinct cost profile that this article derives precisely:

• Insert(record) — place the record in some block with available space, updating free-space bookkeeping.
• Delete(record-id) — remove or mark unavailable the slot holding the record, and register the freed space for reuse.
• Scan() — iterate over every block and every valid record within it, typically for a linear search or to support a full query evaluation.

Records are addressed by a record identifier (rid), typically a pair `(block number, slot number)`, which lets other structures — most importantly Index Structures built later — point directly at a record's physical location without needing to know how heap-internal free space is organized.

Physical layout. Each block holds a slotted page: a small header (record count, pointers/offsets to free space) followed by a directory of slots, each slot holding either a record or a tombstone marking a deleted record. This slotted structure is what allows variable-length records and lets deletion be "logical" — mark a slot empty — without physically compacting the whole block on every delete.

Free-space tracking. A heap file needs a way to answer "which block has room for n more bytes?" without scanning the entire file on every insert. Two classical mechanisms: 1. Free-space linked list. The file header points to the first block with free space; each such block points to the next block with free space, forming a linked list threaded through the blocks themselves. Blocks that fill up are unlinked (a full pointer is not on the list, or is put on a separate "full" list so it can be revisited after a deletion frees space in it). 2. Free-space map (FSM) / bitmap of free-space classes. A small separate structure (often cached in memory) records, per block, roughly how much free space it has (e.g., a few bits encoding "empty," "one-third full," "two-thirds full," "full"). Insertion consults the map directly instead of following pointers, at the cost of maintaining an auxiliary structure. Both approaches answer the same question in O(1) amortized time for a typical insert: they avoid scanning the file to find space.

Insertion algorithm. The database receives a new record, consults the free-space structure for a candidate block, and writes the record there. If no block has room, a new block is allocated at the end of the file. ``` function INSERT(file, record): size = byte_length(record)

# Step 1: consult free-space structure for a block with enough room block_id = FREE_SPACE_STRUCTURE.find_block_with_room(size) if block_id is null:

# No existing block has room: allocate a new block block_id = ALLOCATE_NEW_BLOCK(file) page = EMPTY_PAGE() else: page = READ_BLOCK(file, block_id)

# Step 2: place record into a free slot (or extend the slot directory) slot = page.first_free_slot_or_new() page.write(slot, record)

# Step 3: update bookkeeping WRITE_BLOCK(file, block_id, page) FREE_SPACE_STRUCTURE.update(block_id, page.remaining_free_space()) rid = (block_id, slot) return rid ```

Deletion algorithm. Deletion is deliberately lazy: the slot is marked free rather than the remainder of the block being shifted, because shifting is expensive and unnecessary — the slotted-page directory lets a slot be reused later without moving its neighbors. ``` function DELETE(file, rid): (block_id, slot) = rid page = READ_BLOCK(file, block_id) if page.slot_is_empty(slot): return FAILURE # already deleted / invalid rid page.mark_slot_free(slot) # tombstone; do NOT shift other records WRITE_BLOCK(file, block_id, page) FREE_SPACE_STRUCTURE.update(block_id, page.remaining_free_space()) return SUCCESS ```

Scan algorithm. A scan simply walks every block in file order and yields every occupied slot — this is the operation that touches the entire file and is the reference cost against which indexes are measured. ``` function SCAN(file): for block_id in 1 .. file.num_blocks: page = READ_BLOCK(file, block_id) for slot in page.slots: if not page.slot_is_empty(slot): yield page.read(slot) ```

Point search (no index). Searching for a record matching a predicate on a heap file with no index degenerates to a linear scan with early exit only if a unique match is guaranteed and found: ``` function FIND(file, predicate): for block_id in 1 .. file.num_blocks: page = READ_BLOCK(file, block_id) for slot in page.slots: if not page.slot_is_empty(slot) and predicate(page.read(slot)): yield page.read(slot)

# no early termination in general: predicate may match multiple records,

# or none, and heap file order gives no hint about where matches lie ```

Notation. Let b be the number of blocks currently occupied by the heap file, and let r be the number of records. Assume the free-space structure (map or linked list) is small enough to be cached in memory, or costs O(1) amortized block I/O to consult — this is standard, since it typically occupies a tiny fraction of the space the data itself occupies.

Insertion — O(1) block I/Os (amortized). Consulting the free-space structure is a memory operation (or one extra I/O in the worst case if the structure itself must be paged in). Reading the candidate block, writing the record into it, and writing the block back is exactly one block read + one block write, i.e., 2 I/Os, regardless of b. In the rare case no block has room, the cost is one block allocation and one write — still O(1), independent of file size. This is the entire point of a heap file: insertion cost does not grow with the size of the table. Why is this correct, not just fast? The free-space structure is an invariant-preserving cache: after every insert or delete, `FREE_SPACE_STRUCTURE.update` is called, so the structure always reflects the true occupancy of the block just touched. The one subtlety is staleness for blocks not just touched — a bitmap with coarse buckets (e.g., "under 33% free") can under- or over-estimate slightly, but never claims a full block has room, so `INSERT` never corrupts data; at worst it wastes a check by trying a block that turns out too full and falling through to allocate a new one. This bounded imprecision is the standard tradeoff for keeping the free-space structure cheap to maintain.

Deletion — O(1) block I/Os. Deletion touches exactly the one block containing the target rid: one read, mark the tombstone, one write. No other block is touched, because deletion never triggers compaction of other pages. This is why deletion is called "lazy": the r value drops but b does not shrink automatically, and interior fragmentation (free tombstoned slots inside used blocks) accumulates until the free-space structure directs future inserts to reclaim it.

Scan — Θ(b) block I/Os. A scan must read every block exactly once: `b` reads. This is both an upper and lower bound — you cannot know a block is empty of matching records without reading it (there is no ordering or index to skip blocks), so Θ(b) is tight, not merely an upper bound. This is the number every later article on Cost Comparison of File Organizations will use as the reference point: any index or sorted structure is judged by how far below Θ(b) it can push a point or range query.

Point search (linear scan) — O(b) worst case, Θ(b) if no shortcut exists. Because the heap file gives no information about where a record with a given value lives, a search for `attribute = value` must, in the worst case (value absent, or all matches concentrated in the last block), inspect all b blocks. Average case is still Θ(b) if the query issuer cannot stop early (e.g., counting all matches) and Θ(b/2) in expectation only for the specific sub-case of finding a single guaranteed-unique match with uniformly random placement — a fragile assumption that databases do not rely on for cost estimation. The standard, defensible statement is: point search on a heap file costs O(b) block transfers, full stop.

Space overhead. The free-space structure costs O(b) bits to O(b) bytes depending on granularity (a bitmap of a few bits per block, or a linked pointer per block), which is asymptotically negligible next to the O(b · block-size) data itself, and is the price paid for O(1) insertion.

Tradeoff summary. Heap files achieve the best possible asymptotic insertion cost among file organizations — no reordering, no rebalancing, no split logic — at the cost of the worst possible search cost, since nothing about record placement encodes any information useful for skipping blocks. Every more sophisticated organization (sorted files, hash files, tree indexes) spends some insertion cost to buy back search cost; heap files sit at the "pure insertion speed" end of that spectrum.

Consider a heap file `Employees` with block size holding 4 records per block, currently spanning 3 blocks (12 slots, some occupied, some free after earlier deletes). The free-space map is coarse-grained: it tracks only "has ≥1 free slot" per block.

Two things this trace makes concrete. First, step 5 shows reclamation working as designed: the slot vacated by deleting Farah in step 4 is reused by Grace in step 5 rather than the file growing a fifth block — this is exactly why heap files bound their wasted space to at most one block's worth of fragmentation per free-space-map granularity level, not unboundedly. Second, step 7 shows the fundamental limitation: even though Deepak's record physically sits in block 4, `FIND` has no way to know that without checking B1, B2, and B3 first (in the worst ordering of blocks scanned), incurring the full O(b) cost that a later index would eliminate. Total I/O for this six-operation sequence: 2+2+2+2+4+4 = 16 block transfers for 3 inserts, 1 delete, 1 full scan, and 1 point search over a 4-block file — illustrating that the insert/delete operations (O(1) each) are cheap individually, while the scan and search dominate the total cost, scaling with file size rather than with the number of records touched.

The heap file is not the invention of a single person; it is the natural first file organization anyone builds when persisting records to block-structured disks, and its formalization emerged alongside the earliest systematic treatments of database file structures in the 1970s, as researchers began classifying file organizations (heap, sorted, hashed) and analyzing their access costs in the way this article does.

Every major relational database uses a heap-like organization as its default table storage unless the user explicitly requests otherwise. PostgreSQL literally calls its default table storage a "heap" and maintains an explicit free-space map (FSM) file per table plus a visibility map, exactly mirroring the mechanisms described here, with a background `VACUUM` process reclaiming tombstoned tuple slots. MySQL/InnoDB by contrast clusters tables by primary key (an index-organized table) by default, but heap-style unordered secondary storage patterns appear in its temporary tables and in MyISAM's legacy heap-organized `.MYD` files. Big-data and log-structured systems — write-optimized stores, append-only logs, LSM-tree base layers — inherit the same core tradeoff: cheap appends now, and a cost paid later (compaction, indexing, merging) for cheap reads. Heap files are also the conceptual anchor for teaching query cost estimation: every database course computes "cost of a full table scan" as b I/Os before introducing any index, precisely because that number is the heap file's scan cost derived above. Once a table has a B+-tree or hash index, the same query's cost analysis becomes "index lookup cost + heap file access cost per matching row," making the heap-file cost model the baseline term in every subsequent formula. Understanding heap files is therefore not just historical background — it is the arithmetic every later chapter on indexing, query optimization, and access-path selection builds directly on top of.

Ask the tutor: How does the I/O cost of a heap file scan compare once a B+-tree index is added on top of it, for both point queries and range queries?