Cost Comparison of File Organizations

A file organization is the physical layout of a relation's records across disk blocks. Two baseline organizations anchor every comparison in this area. A heap file (or unordered file) places records wherever there is free space, in no particular order; new records are typically appended at the end. A sorted file maintains all records in physical order according to some search key, so that consecutive blocks contain consecutive key ranges. The right way to compare organizations is not "which is faster" in the abstract, but which is faster for which operation, measured in a currency that reflects real hardware: the number of block (page) transfers. This convention exists because a single disk I/O — reading or writing one block — typically costs on the order of milliseconds, while an in-memory comparison or arithmetic operation costs nanoseconds, a difference of roughly six orders of magnitude. Consequently, database cost models systematically ignore CPU cost and count only block transfers; this is the standard simplification used throughout query optimization and storage analysis. Fix the following notation, used throughout: let `r` denote the number of records (tuples) in the relation, `R` the size in bytes of one record, `b` the number of blocks the file occupies, and `B` the size in bytes of one block. Then `b = ⌈r · R / B⌉` (assuming records are not split across blocks — the usual convention). We assume records of fixed length for simplicity, and that a search key is the attribute (or attributes) on which equality or range queries are posed and on which the sorted file is ordered. All costs below are given in units of block transfers; a secondary, smaller cost of CPU comparisons is noted only where it matters qualitatively.

We now derive the cost of each of the five canonical operations for each organization. The derivations are not arbitrary — each follows from a precise mechanical description of what the storage engine must physically do.

1. Scan (retrieve all records). Both organizations must read every block at least once, since every record must be examined regardless of order.

• Heap file: `b` block transfers.
• Sorted file: `b` block transfers (order does not reduce scan cost — you still must touch every block).

2. Equality search on the search key (find the record(s) with key = v). Heap file. Records are unordered, so there is no way to know where a matching record lives without checking blocks. If the search key is not a candidate key (duplicates possible, or no uniqueness guarantee), the engine must scan all `b` blocks to be sure it has found every match — cost `b`. If the search key is a candidate key (at most one match exists), the engine can stop as soon as it finds the match. On average, assuming the match is equally likely to be in any block, this costs about `b/2` block transfers; in the worst case (no match, or match in the last block), it costs `b`. Sorted file. Because records are physically ordered by the search key, the engine can perform binary search directly on the block sequence: read the middle block, compare its key range against `v`, and recurse into the correct half. This costs `⌈log₂ b⌉` block transfers to locate the first qualifying block. If the key is not a candidate key, additional blocks holding further duplicates must also be read, but binary search still identifies the start of the matching run in `O(log₂ b)`.

3. Range search (find all records with `v₁ ≤ key ≤ v₂`). Heap file. There is no shortcut: matching records could be anywhere, so the entire file must be scanned — cost `b`. Sorted file. Binary search locates the first block containing a key `≥ v₁` in `⌈log₂ b⌉` transfers; then the engine reads sequentially forward until a key exceeds `v₂`. If the matching records span `r'` blocks, total cost is `⌈log₂ b⌉ + r' − 1` (the `−1` because the first matching block was already fetched during the binary search) — commonly written `O(log₂ b + r')`.

4. Insertion. Heap file. A new record can go anywhere there is space. The typical strategy — append at end of file, or use the last block if it has free space — costs: 1 block transfer to fetch the last block (if it might have space), plus 1 block transfer to write it back; if a new block must be allocated, it's simply 1 write. This is treated as `O(1)`, i.e., a constant small number of block transfers (commonly quoted as 2: read last block, write updated/new block), independent of `b`. Sorted file. Order must be preserved. The engine must (a) locate the correct position via binary search — `O(log₂ b)` — then (b) shift all subsequent records one slot forward to make room, which in the worst case touches every block after the insertion point. Worst-case cost is `O(b)`; on average, if the insertion point is uniformly random, about `b/2` blocks must be shifted, giving `O(log₂ b) + O(b) = O(b)` overall (the shifting term dominates).

5. Deletion (find then delete a record satisfying some condition). Heap file. Locate the record — costs the same as equality search (`b` or `b/2` depending on key uniqueness) — then delete it. Physical deletion in a heap file is cheap once located: mark the slot free, or move the last record into the freed slot to keep the file "packed" (both are `O(1)` additional transfers beyond the search). Sorted file. Locate the record via binary search — `O(log₂ b)` — but then, to preserve sortedness without leaving a gap, all following records must be shifted back by one slot, exactly mirroring insertion: worst case `O(b)`, average `O(b)` dominated by the shift. A common practical mitigation is lazy deletion: mark the record as deleted (a tombstone bit) without physically shifting anything, deferring the compaction cost to a periodic batch reorganization. This reduces deletion cost to `O(log₂ b)` (search cost only) at the price of wasted space and slightly increased future scan/search cost until reorganization. ``` // Cost model conventions: // b = number of blocks occupied by the file // B = block transfer cost unit (we count block transfers, not bytes) // search key may or may not be a candidate key (unique) function SCAN(file): cost = 0 for each block in file: // must visit every block read(block) cost += 1 return cost // = b for both heap and sorted files function EQUALITY_SEARCH_HEAP(file, v, key_is_unique): cost = 0 for each block in file (in storage order): read(block); cost += 1 if block contains a record with key == v: if key_is_unique: return cost // stop early: at most b, avg b/2 // else continue scanning: duplicates may be elsewhere return cost // = b if not found, or if key not unique function EQUALITY_SEARCH_SORTED(file, v): lo = 0; hi = b - 1; cost = 0 while lo <= hi: mid = (lo + hi) / 2 read(block[mid]); cost += 1 if v within key range of block[mid]: // scan forward within/after this block for all matches return cost // = ceil(log2 b) else if v < min_key(block[mid]): hi = mid - 1 else: lo = mid + 1 return cost // not found: still O(log2 b) function RANGE_SEARCH_SORTED(file, v1, v2): start_cost = EQUALITY_SEARCH_SORTED(file, v1) // ~ log2 b cost = start_cost block = the block located above while block has records with key <= v2: cost += 1 // sequential read forward block = next_block(block) return cost // = ceil(log2 b) + r' - 1 function INSERT_HEAP(file, record): read(last_block); cost = 1 if last_block has free space: write record into last_block write(last_block); cost += 1 else: allocate new_block write record into new_block write(new_block); cost += 1 return cost // O(1), typically ~2 function INSERT_SORTED(file, record): pos_cost = EQUALITY_SEARCH_SORTED(file, record.key) // find insertion point shift_cost = number of blocks after insertion point // rewrite each for each block from insertion point to end: read(block); write(block) // shift records forward by one slot return pos_cost + 2 * shift_cost // O(b) worst case, O(b) average ``` The single unifying mechanism worth internalizing: binary search only works because the file is physically sorted; any operation that would destroy that order (insert, delete without tombstoning) must pay to restore it.

The complexity results are summarized below, `r` = matching-range block span for range queries, `b` = total blocks.

Why binary search costs `⌈log₂ b⌉`. Each probe reads one block and, by comparing its key range to the target, discards half of the remaining candidate blocks — exactly as in ordinary binary search over an array, except the "array elements" are blocks rather than individual keys. Starting from `b` candidate blocks, after `k` probes at most `b / 2^k` candidates remain; the search terminates when this quantity is `< 1`, i.e., when `k ≥ log₂ b`. Hence at most `⌈log₂ b⌉` block reads are needed. This is a direct instance of the classical binary search invariant: at every iteration, the answer (if it exists) lies within the current `[lo, hi]` window, and the window's size strictly halves (up to rounding) each iteration.

Why heap equality search averages `b/2`. If the key is unique and the matching record's block position is uniformly distributed over the `b` blocks (a reasonable assumption absent other information), the expected number of blocks read before encountering the match is the expectation of a discrete uniform variable over `{1, …, b}`, which is `(b+1)/2 ≈ b/2`. The worst case remains `b` (record is in the last block, or absent).

Why insert/delete on sorted files cost `O(b)`. To keep the file sorted after inserting a record at logical position `i` (out of `b` blocks' worth of records), every record originally at position `≥ i` must move one slot forward. In the worst case (`i` near the front), nearly all `b` blocks are rewritten. Averaging over a uniformly random insertion position gives an expected `b/2` blocks shifted — still `Θ(b)`, i.e., linear in file size, because the number of records requiring displacement scales with `b` regardless of how quickly the insertion point itself is located.

Correctness of the sorted-file invariant. The entire benefit of the sorted file rests on one invariant that must be preserved by every operation: for any two blocks `Bᵢ`, `Bⱼ` with `i < j` in storage order, every key in `Bᵢ` is ≤ every key in `Bⱼ`. Binary search is only correct as long as this invariant holds — if a single insertion is done "for free" without shifting, the invariant breaks and future binary searches can silently return wrong (incomplete) results. This is precisely why insertion and deletion cannot be made cheap without either (a) paying the shift cost, or (b) weakening the promise (e.g., tombstoning, which preserves order among live records exactly, or overflow/auxiliary areas, which trade order for later reorganization cost) — themes that anticipate why B+-trees exist: they preserve logical order while allowing local (not global) rebalancing, at the cost of extra pointer structure.

Tradeoff honesty. No organization dominates the other across all five operations — this is the entire point of the comparison. A heap file is optimal for write-heavy workloads with rare or bulk-only reads (e.g., staging/append-only logs). A sorted file is excellent for read-heavy workloads dominated by equality/range queries on the sort key, but pays a steep price under interleaved single-record inserts/deletes — a cost profile that in practice is usually addressed by never physically re-sorting on every write, but instead using an index (B+-tree) that gives `O(log_F N)` search and update, at the cost of extra structure — the natural segue to Index Selection and to structures such as the B+-Tree Index and Hash Index.

Consider a relation `Employee` with `r = 100{,}000` records, each of size `R = 100` bytes, stored in blocks of size `B = 4{,}096` bytes. Then: ``` b = ceil(r R / B) = ceil(100,000 100 / 4,096) = ceil(2441.4) = 2442 blocks ``` Assume the search key `emp_id` is a candidate key (unique). We compute costs for each operation under both organizations.

Trace of the equality search on the sorted file, locating `emp_id = 47281` among 2442 blocks (indices `0..2441`):

Twelve probes, matching `⌈log₂ 2442⌉ = 12` exactly, versus an average of 1,221 block reads for the heap file — roughly a 100× speedup for this single search. This gap widens as `b` grows: for `b = 10^6` blocks, sorted search costs `⌈log₂ 10^6⌉ = 20` versus a heap average of `500{,}000` — a five-order-of-magnitude difference, illustrating why `O(log b)` versus `O(b)` is not a minor constant-factor distinction but a qualitative one at scale. Conversely, for 1,000 individual inserts into the sorted file (not batched), the expected shift cost per insert is about `b/2 ≈ 1221` blocks, giving roughly `1{,}221{,}000` block transfers total — versus roughly `2{,}000` transfers for the same 1,000 inserts into a heap file. This is the mirror-image demonstration: the sorted file's search advantage is purchased at an update cost that can be several orders of magnitude worse.

The systematic cost-based comparison of file organizations emerged from the broader development of relational database theory and query optimization in the 1970s, when researchers first insisted on quantifying I/O cost explicitly rather than reasoning about correctness alone.

Every production relational database — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server — begins its storage layer with exactly this choice: tables are stored as heaps by default (heap tables in PostgreSQL, unless a clustered index is used), while explicit range and equality lookups are accelerated by separately maintained sorted structures (B+-tree indexes) rather than by keeping the base table itself sorted, precisely because raw sorted-file maintenance costs are prohibitive under high-throughput inserts. Data warehouses and OLAP systems, where bulk loads dominate and interactive point-updates are rare, often use sorted or clustered storage (e.g., column-store systems with sort keys, or clustered indexes in row stores) because query performance benefits from `O(log b + r')` range scans and the insert/delete cost is amortized over large batch loads rather than paid per-record. Conversely, high-throughput transactional systems (OLTP) favor heap storage for the base table, layering B+-tree or hash indexes on top to regain fast search without paying sorted-file update costs on every write. Log-structured merge trees (LSM trees), used in systems like Cassandra, RocksDB, and LevelDB, are a direct engineering response to this exact tradeoff: they batch writes into sorted runs (gaining sorted-file search benefits) while amortizing the shifting/rewriting cost across many records at once via periodic compaction, rather than paying it per insert. Understanding this heap-versus-sorted cost tradeoff is the essential prerequisite for reasoning about Index Selection, B+-Tree Index design, and the query optimizer's access-path decisions in any real database engine.

Ask the tutor: How does adding a B+-tree index change these cost formulas, and why does it avoid the O(b) shifting cost that sorted files suffer from during insertion?