Sorted Files
Imagine a database of ten million customer records. A manager constantly asks for "everyone with a balance between 1000." If the records sit in arbitrary order, answering that query means scanning every single block. A sorted file fixes this. It physically arranges records on disk according to a chosen search key. Records with nearby key values then sit in nearby blocks. This single organizational choice turns an expensive linear scan into a fast binary search. It also turns range queries from "read everything" into "read only the relevant contiguous run." Sorted files matter because so much of real query workload is about order and ranges. Examples include date ranges, alphabetical lookups, price brackets, and timestamps. Long before modern indexes existed, database systems used physical sort order as the primary access mechanism. Even today sorted files underpin index leaf levels, merge-based query processing, and log-structured storage engines. Understanding sorted files is a prerequisite for understanding why indexes are built the way they are. A sorted file is, in a sense, the simplest possible index: the data organizes itself. The central tension this article explores is between read efficiency and write cost. A sorted file gives excellent performance for point lookups and range scans via binary search. But inserting or deleting a record threatens to violate the sort order. This can potentially force large blocks of data to shift. This trade-off — fast reads, expensive maintenance — is the defining feature of sorted files. It motivates almost every later refinement in indexing, from overflow areas to B-trees. This article builds the mechanism from first principles. It covers how binary search works at the block level, and how range scans exploit contiguity. It also covers the exact cost of insertion and deletion in the worst and average cases. Finally, it examines the practical compromises real systems use to survive updates. These include overflow blocks, periodic reorganization, and gap-leaving. Such compromises avoid paying the full reorganization price every time.
- A sorted file stores records in physical order by a search key, enabling binary search over blocks.
- Binary search on `b` blocks costs `O(log₂ b)` I/Os — dramatically cheaper than the `O(b)` cost of a linear scan.
- Range queries cost one binary search plus a sequential scan of the qualifying blocks: `O(log₂ b + r)`.
- Insertions and deletions can require shifting `O(n)` records to preserve order — the classic cost of sortedness.
- Real systems soften this with overflow blocks, gaps, and batched reorganization instead of shifting on every write.
- Sorted files are the conceptual ancestor of index leaf levels and set the baseline for comparing file organizations.
Sorting a file trades cheap, fast reads (binary search, contiguous range scans) for expensive, disruptive writes (record shifting to keep order).
The idea
A sorted file (also called an ordered file or sequential file) stores all records of a relation physically arranged, block by block, in increasing (or decreasing) order of some attribute or attribute combination called the search key. This is distinct from the notion of a sort key used only for query output — here the sort order is a permanent property of the file's storage layout, maintained across insertions, deletions, and updates. Two properties make sorted files powerful. First, global order: if you know the search-key value you want, you know which "direction" to look — smaller values are to the left, larger to the right — so you can prune half the remaining search space at each step, exactly as in binary search over an array. Second, local contiguity: records with adjacent key values are stored in adjacent or nearby blocks, so a range query (`WHERE key BETWEEN v1 AND v2`) can be answered by locating the start of the range once and then reading blocks sequentially until the range ends, without random-access jumps. These two properties come at a structural cost. Because the file's blocks are (conceptually) a single sorted array spread across disk, inserting a new record in the middle requires shifting every subsequent record over by one slot to keep the array sorted and gapless — analogous to `array insertion cost` in an in-memory sorted array, but multiplied by the cost of a disk I/O per block touched. This is the central design tension that motivates every mechanism discussed below, and it is exactly the tension that later leads system designers toward richer structures such as B+-Tree Index and other index organizations that decouple logical order from physical placement.
How it works
Physical layout. Assume records of fixed size `R` bytes are packed into blocks of size `B` bytes, with the file spanning `b = ⌈n·R / B⌉` blocks for `n` records (ignoring header/free-space bookkeeping and any per-record overhead). The blocks themselves are typically also arranged so that block `i` holds records with strictly smaller keys than block `i+1` — i.e., the file is sorted within each block and blocks are sorted among themselves. This lets us treat the entire file, for algorithmic purposes, as one giant sorted array indexed by block number and slot number.
Binary search for point lookup. To find a record with search-key value `v`, we do not need to read every block. We can binary search over block numbers directly, since we know each block's key range (either by reading its first/last record or by an auxiliary in-memory block directory). ``` function BINARY_SEARCH_FILE(file, v): lo ← 0 hi ← file.numBlocks - 1 while lo <= hi: mid ← (lo + hi) / 2 // integer division block ← READ_BLOCK(file, mid) // one disk I/O if v < block.firstKey: hi ← mid - 1 else if v > block.lastKey: lo ← mid + 1 else: // v falls in this block's key range; scan the block in memory for record in block.records: if record.key == v: return record return NOT_FOUND // v not present, but in range return NOT_FOUND ``` Each loop iteration reads exactly one block (one I/O) and halves the remaining search interval, exactly mirroring in-memory binary search but with disk blocks as the unit instead of individual elements — this is the key structural insight that turns `O(b)` linear cost into `O(log₂ b)`.
Range scan. For a range query `[v1, v2]`, run the binary search above to locate the first block whose range could contain `v1` (a small variant that returns the leftmost qualifying block rather than failing on a miss), then scan forward sequentially, collecting records until a key exceeds `v2`. ``` function RANGE_SCAN(file, v1, v2): startBlock ← FIND_FIRST_BLOCK_GEQ(file, v1) // binary search, O(log b) I/Os results ← [] b ← startBlock while b < file.numBlocks: block ← READ_BLOCK(file, b) // 1 I/O, sequential access for record in block.records (in key order): if record.key > v2: return results if record.key >= v1: results.append(record) b ← b + 1 return results ``` The crucial efficiency gain is that the scan phase reads blocks sequentially — disk (and even SSD, for prefetching reasons) access patterns strongly favor sequential reads over random reads, so this phase is both I/O-count-optimal (touches only the `r` blocks that actually contain qualifying records) and access-pattern-optimal.
Insertion. To insert a new record `x` while preserving sort order: ``` function INSERT_SORTED(file, x): target ← FIND_BLOCK_FOR_KEY(file, x.key) // O(log b) I/Os via binary search if BLOCK_HAS_SPACE(target): SHIFT_WITHIN_BLOCK(target, x) // insert in-block, small cost WRITE_BLOCK(target) else: // target block is full: must cascade overflow ← x for b ← target to file.numBlocks - 1: block ← READ_BLOCK(file, b) evicted ← REMOVE_LAST_RECORD(block) INSERT_IN_ORDER(block, overflow) WRITE_BLOCK(file, b) overflow ← evicted APPEND_NEW_BLOCK(file, overflow) // last evicted record starts new block ``` This cascading-shift version is the "textbook worst case": one new record can force every subsequent block to be rewritten. Deletion is symmetric — remove the record, then optionally pull records forward from later blocks to eliminate the resulting gap, or simply leave a gap (a tombstone) to be reclaimed later.
Practical mitigation. Because full cascading shifts are too expensive for interactive workloads, real systems typically use one or more of:
- Overflow blocks: each primary block reserves a pointer to an overflow chain; new records that do not fit go into overflow blocks rather than triggering a cascade. The file stays logically sorted (via chasing overflow pointers) but is no longer perfectly physically sorted, and periodic reorganization merges everything back into clean sorted blocks.
- Reserved free space (fill factor): blocks are loaded only, say, 80% full at creation/reorganization time, leaving room for a bounded number of insertions before a shift becomes necessary.
- Batch reorganization: instead of shifting on every insert, buffer new records separately (e.g., in an unsorted "delta" file) and periodically merge-sort them into the main file in one efficient sequential pass.
Complexity & correctness
Point lookup — `O(log₂ b)` I/Os. Binary search over `b` blocks halves the candidate range each iteration, exactly as binary search over an array of `b` elements. The number of iterations until the interval collapses to zero or one block is `⌈log₂(b+1)⌉ = O(log₂ b)`. Each iteration costs exactly one disk I/O (one block read), and the in-memory scan of that block's records costs `O(R/r)` where `r` is record size and `R` block size — a constant, CPU-only cost that does not touch disk again. Compare this to an unsorted (heap) file, where a point lookup for a key not known to be unique in placement requires an `O(b)` linear scan in the worst case (and expected `O(b)` even if the record is guaranteed to exist, since it could be anywhere). Correctness invariant. The binary search is correct because the file maintains the invariant: for all blocks `i < j`, every key in block `i` is `≤` every key in block `j`. This total order across blocks means that comparing `v` to `block.firstKey` and `block.lastKey` correctly determines which half of the file can be discarded — exactly the loop invariant of classical binary search, lifted from array indices to block numbers. Formally, if `v < block[mid].firstKey`, no record with key `v` can exist in blocks `mid, mid+1, …` (all have keys `≥ block[mid].firstKey > v`), so discarding the right half preserves the "answer must be in `[lo, hi]`" invariant; the symmetric argument handles `v > block[mid].lastKey`.
Range scan — `O(log₂ b + r)` I/Os, where `r` is the number of blocks that actually contain qualifying records. The `log₂ b` term is the one-time binary search to find the start of the range; the `+ r` term is a purely sequential scan. This is asymptotically optimal: any correct algorithm must read at least the `r` blocks containing answers, so `r` is an unavoidable lower bound, and `log₂ b` is the cost of locating those blocks without scanning everything before them.
Insertion / deletion — `O(b)` worst case, but the real bound is subtler. Locating the insertion point costs `O(log₂ b)` I/Os via binary search. If the target block has a free slot, insertion finishes there: `O(log₂ b)` total. But if the target block is full, correctness of the sort order forces a cascade: every subsequent block must shift one record to the block before it, an `O(b)` I/O operation in the worst case (imagine inserting a record with the smallest key into an already-full file — every block must shift). This is unavoidable if we insist on gapless, fully-packed sorted blocks with no reserved space or overflow mechanism: any correct algorithm maintaining that exact invariant must, in the worst case, touch `Θ(b)` blocks, because a single insertion can force a permutation affecting every record after the insertion point.
Why overflow/free-space mitigations change the bound. If each block reserves a fraction `f` of free slots (fill factor `1 − f`), a single insertion typically only needs to touch the target block, giving expected `O(log₂ b)` amortized cost for a sequence of insertions, until free space in a local region is exhausted and a local reorganization (or overflow chaining) is triggered. Overflow chains avoid the cascade entirely by paying a small, bounded cost per insertion (`O(1)` to append to an overflow block) at the price of degrading range-scan sequentiality — you must eventually reorganize to restore true sortedness, an `O(b)` operation done rarely (e.g., during off-peak maintenance windows) rather than per insert.
Space complexity. A sorted file with no reserved space uses `O(n)` blocks, essentially `⌈n·r / B⌉`, identical to a heap file — sortedness costs no extra space in the ideal case, only reorganization time under updates. With a fill factor `f`, space overhead grows by a factor `1/f`, a direct, tunable trade of space for insertion headroom.
Honest tradeoff summary.
| Operation | Sorted file | Unsorted (heap) file |
|---|---|---|
| Point lookup (key known to exist) | `O(log₂ b)` | `O(b)` worst case |
| Range scan (`r` result blocks) | `O(log₂ b + r)` | `O(b)` |
| Insertion (no free space) | `O(b)` worst case | `O(1)` (append) |
| Deletion (compact gaps) | `O(b)` worst case | `O(1)` (mark deleted) |
The pattern is unmistakable: sortedness is a read-side optimization purchased with write-side cost. Systems choose sorted files precisely when reads (especially range reads) vastly outnumber writes, or when writes can be batched.
Worked example
Consider a file of customer records with search key `CustomerID`, block capacity 4 records, currently holding 24 records packed into 6 full blocks (no free space reserved), so `b = 6`.
| Block | Records (CustomerID) |
|---|---|
| 0 | 101, 105, 110, 115 |
| 1 | 118, 122, 130, 135 |
| 2 | 140, 148, 155, 160 |
| 3 | 165, 170, 178, 185 |
| 4 | 190, 195, 200, 210 |
| 5 | 215, 220, 230, 240 |
Query 1: point lookup for CustomerID = 170.
| Step | lo | hi | mid | Block range read | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | [140,160] | 170 > 160 → go right, `lo=3` |
| 2 | 3 | 5 | 4 | [190,210] | 170 < 190 → go left, `hi=3` |
| 3 | 3 | 3 | 3 | [165,185] | 170 in range → scan block, found |
3 disk I/Os total, versus up to 6 for a linear scan of an unsorted file — here `⌈log₂ 6⌉ = 3` matches exactly, confirming the `O(log₂ b)` bound.
Query 2: range scan for CustomerID in [150, 200]. Binary search locates block 2 as the first block whose range could contain 150 (in 2–3 I/Os, similar to above). Then the algorithm scans sequentially:
- Block 2: 140 (skip, <150), 148 (skip), 155 ✓, 160 ✓
- Block 3: 165 ✓, 170 ✓, 178 ✓, 185 ✓
- Block 4: 190 ✓, 195 ✓, 200 ✓, 210 (stop, >200)
Total I/O: `O(log₂ b)` to locate block 2, plus 3 sequential block reads (blocks 2, 3, 4) — matching `O(log₂ b + r)` with `r = 3`.
Update: insert CustomerID = 172. Binary search locates block 3 (range 165–185) as the insertion target. Block 3 is full (4/4 records), so the cascading-insert algorithm fires: 1. Read block 3: `[165, 170, 178, 185]`. Insert 172 in order → `[165, 170, 172, 178, 185]`, which has 5 records but capacity is 4. Evict the last record, `185`, to carry forward. Write block 3 as `[165, 170, 172, 178]`. 2. Read block 4: `[190, 195, 200, 210]`. Insert carried `185` → `[185, 190, 195, 200, 210]`, evict last (`210`), write block 4 as `[185, 190, 195, 200]`. 3. Read block 5: `[215, 220, 230, 240]`. Insert carried `210` → `[210, 215, 220, 230, 240]`, evict last (`240`), write block 5 as `[210, 215, 220, 230]`. 4. No block 6 exists yet: append a new block 6 containing the final evicted record `240`. This single insertion touched blocks 3, 4, 5, and appended block 6 — four block writes plus the original binary-search reads, illustrating exactly the `O(b)` cascade cost predicted above when no free space is reserved. Had each block instead reserved one free slot (fill factor 75%), inserting 172 into block 3 (now holding only 3 of 4 records) would have cost a single block rewrite — a concrete demonstration of how fill factor converts worst-case cascades into cheap local updates, at the price of `4/3×` space overhead.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Assuming binary search works without a block-range directory | Binary search needs to know each block's `firstKey`/`lastKey` cheaply; scanning a block just to check its range wastes I/O | Maintain a small in-memory (or cached) array of block boundary keys, itself effectively a primitive index |
| Off-by-one in the binary search bounds | Using `<` vs `<=`, or forgetting to update `lo`/`hi` correctly, causes infinite loops or missed blocks | Use the standard invariant "`answer ∈ [lo, hi]`" and verify termination when `lo > hi` |
| Treating insertion as always `O(log b)` | Confusing the cost of locating the insertion point with the cost of performing the insertion | Separate "search cost" from "maintenance cost"; the cascade dominates when blocks are full |
| Forgetting deletion gaps degrade range scans | Leaving tombstones without periodic compaction makes range scans read wasted, empty slots | Schedule reorganization, or compact eagerly if delete rate is low |
| Ignoring reorganization cost when comparing to heap files | A sorted file "wins" on reads but its total cost of ownership must include periodic full re-sorts | Amortize reorganization cost over the insertions it enables before comparing to heap-file append cost |
| Binary searching on a non-unique key without handling duplicates | If many records share a key, one binary search probe lands "inside" a run of duplicates, and naive logic may stop early, missing others | After finding one match, scan left/right within and across blocks to collect all duplicates |
Pioneers & history
Sorted, sequential file organization predates relational databases entirely — it descends directly from sequential tape and card-sorting practice in early data processing, where "sorted" was often the only efficient way to process large batches of records at all, since random access to tape was effectively impossible. The technique of merging sorted runs, binary searching over blocked data, and reorganizing periodically were formalized as database systems matured in the 1970s, closely tied to foundational work on file organizations and external sorting.
Origins · 1 minOle-Johan Dahl and Kristen Nygaard and how this was discovered
While best known as originators of object-oriented programming through Simula, Dahl and Nygaard's work on structuring large simulation datasets fed directly into thinking about how to organize records efficiently on external storage — a precursor concern to the file organization problems formalized in relational systems.
Where this matters
Sorted files are rarely used today as the sole organization for a heavily updated OLTP table, precisely because of the insertion cost this article derives — but the concept is everywhere underneath the surface. The leaf level of a <span class="wiki-link-missing">B+-Tree Index</span> is, in essence, a sorted file with a tree of guide-posts on top, replacing linear block-boundary lookup with a shallow tree traversal. Log-structured merge (LSM) trees, used in systems like Cassandra, RocksDB, and LevelDB, explicitly embrace the "batch reorganization" mitigation described above: writes accumulate in an unsorted in-memory buffer, then are flushed as sorted, immutable files, which are periodically merged (compacted) — turning the sorted-file insertion problem into a controlled, asynchronous background cost rather than a per-write penalty. Data warehouses and columnar analytics engines (e.g., sorting fact tables by date for range-heavy analytical queries) rely directly on the range-scan efficiency of sorted physical layout, often calling the technique "clustering" or "sort keys" (as in Amazon Redshift or Snowflake's clustering keys). Read-heavy, append-mostly workloads — time-series databases, immutable event logs, data lake table formats — are natural fits for sorted files because their write pattern (append at the end, rarely insert in the middle) sidesteps the cascade problem entirely. Understanding sorted files is the essential stepping stone to the Cost Comparison of File Organizations that database designers perform when choosing a storage layout, and to the broader topic of Introduction to Indexing, where the same binary-search intuition reappears in tree form to make maintenance cheap without sacrificing read speed.
Ask the tutor: How do B+-trees avoid the O(b) cascading-shift cost that plain sorted files suffer during insertion?
Is a sorted file the same thing as an index?
Not quite. A sorted file is a physical storage organization: the actual data records themselves are arranged in key order on disk. An index is typically a separate, auxiliary structure (like a B+-Tree Index) that points to records, which may or may not be physically sorted. However, a sorted file's block-boundary key directory is conceptually a primitive index, and many indexes (like a clustered index) are built by physically sorting the underlying data — so a clustered index is essentially a sorted file with a search structure layered on top for faster navigation than raw binary search.
Why not just always keep files sorted, since reads are so much faster?
Because maintaining sort order under insertions and deletions can cost `O(b)` I/Os in the worst case — potentially rewriting most of the file for a single new record. For workloads dominated by writes, or by unpredictable insert patterns, this cost can dwarf the read-side savings. Systems instead choose sorted files when reads (especially range queries) vastly outnumber writes, or use mitigations like overflow blocks, reserved free space, and batched reorganization to approximate sortedness cheaply, deferring the expensive full re-sort to background maintenance windows.
How does binary search on a file differ from binary search on an in-memory array?
The algorithmic logic is identical — repeatedly halve the search interval by comparing the target to a midpoint. The difference is the cost model: each "compare" in a file-based binary search costs one disk I/O (reading a block), which is orders of magnitude slower than an in-memory comparison. This is why the `O(log₂ b)` I/O bound is significant news for databases — a file of a million blocks needs only about 20 I/Os to find any record, versus up to a million for a linear scan — while the same asymptotic improvement in memory is comparatively less dramatic in wall-clock terms.
What happens to range scan performance if the file accumulates lots of overflow blocks?
Overflow chains preserve logical order (you can still find all matching records by following overflow pointers) but destroy physical contiguity. A range scan that used to read `r` sequential blocks might now need to also chase scattered overflow blocks, turning some of what should be sequential I/O into random I/O, which is much slower on spinning disks and still meaningfully slower on SSDs due to prefetching and command queuing effects. This degradation is precisely why systems schedule periodic reorganization: it merges overflow chains back into clean sorted blocks, restoring the sequential-scan advantage.
Does a sorted file help with equality search on a non-key attribute that isn't the sort key?
No. The binary search and range scan efficiency only apply to the attribute the file is physically sorted on. Searching for a value on a different attribute in a sorted file offers no better guarantee than an unsorted (heap) file — you generally still need a full `O(b)` scan, unless a separate index exists on that attribute. This is exactly why real systems build multiple secondary indexes: the file can only be physically sorted by one key at a time, so other attributes need auxiliary structures for efficient lookup.
Is deletion cheaper than insertion in a sorted file?
It can be, if you allow gaps: deleting a record just means marking its slot empty (or shrinking the block's record count), an `O(log₂ b)` operation (locate, then mark) with no cascade required. The cost only reappears if you insist on immediately compacting the file to remove gaps, which then requires shifting subsequent records leftward, symmetric to the insertion cascade. Most practical systems tolerate gaps temporarily and reclaim the space during periodic reorganization rather than paying compaction cost on every delete.
How does this relate to Disk Blocks and File Organization more broadly?
Sorted files are one specific answer to the general file organization question: given that data must be grouped into fixed-size disk blocks, how should records be arranged among and within those blocks? Disk Blocks and File Organization introduces the basic unit of I/O and unsorted (heap) organization as the baseline; sorted files show what happens when we additionally enforce a global order constraint, trading write-time flexibility for read-time speed. This sets up the natural next question, addressed in Cost Comparison of File Organizations: which organization is best for a given workload's read/write mix.