Speaker note: Every structure so far lived in RAM. This week moves to disk, where the unit that matters is not a comparison but a block read.
Speaker note: Nine short animations carry the whole lecture; each idea gets one normal run and one edge/hard run, right where it is introduced.
Speaker note: Every term gets a full definition the first time it appears; this table just says where to find it again.
Speaker note: Open a terminal now if you want to run these live; every program creates a scratch folder in the OS temp directory, never inside the repo.
Speaker note: This week keeps returning to one theme — trading a search for a computation whenever the data's layout allows it.
Speaker note: If you understood Week 6's hash table, sections 8-10 are the same table, just one level removed from RAM.
Speaker note: This single shift in what you count is the organizing idea of the entire week — everything else follows from it.
Speaker note: Every box here gets its own full section below, each with an animation, a real program, and a complexity/mistakes discussion.
Speaker note: Section 1 has no animation of its own — it sets up the drawing convention and cost model every later section reuses.
Speaker note: The answer is a hardware and file-system fact, not a design choice any program can opt out of.
Speaker note: Every technique this week is really a strategy for minimizing the number of block reads and writes.
Speaker note: Every single animation this week uses exactly this layout — once you can read one, you can read all nine.
Speaker note: Real systems very often use both at once — a sequential file for batch jobs, a hashed file for interactive lookups.
Speaker note: Think about what actually costs time here — the comparisons, or the disk accesses.
Speaker note: This is precisely why every section from here on counts block reads, not comparisons, as its complexity.
Speaker note: Section 2 is about packing several fields of a record into bytes — and unpacking them again on read.
Speaker note: The three answers below trade wasted space against parsing cost, and none of them is free.
Speaker note: Fixed-length pays with wasted or lost bytes; delimited pays with a scan; length-prefixed pays with a hard size cap.
Speaker note: This is the seed of the whole "compute instead of search" theme that runs through the rest of the week.
Speaker note: None of these three is "the right one" in general — the right choice depends entirely on whether records need a fixed, computable size.
Speaker note: Normal example: 11 records, `NAME_FIXED=8` — watch which names get padded and which get silently truncated.
Speaker note: Every single record loses data in the fixed layout here — the worst case for this technique, made maximal on purpose.
Speaker note: An empty name is fully padded in the fixed layout, costs zero bytes in the delimited layout — two very different ways to handle the same extreme.
Speaker note: Truncation is silent unless the program itself decides to report it — the code above prints a warning specifically for that reason.
Speaker note: No delimiter character is needed at all, and no character has to be forbidden inside the name — the trade is a 255-byte length cap.
Speaker note: This is a rare case this semester where the interesting trade-off is not in the big-O at all.
Speaker note: A delimiter like a comma inside a name breaks the moment a real name contains a comma — length-prefixing sidesteps this class of bug entirely.
Speaker note: Think about what information the reader has *before* it starts reading the field's content.
Speaker note: The length-prefixed scheme's one byte of overhead buys it certainty a scan can never have in advance.
Speaker note: Section 3 answers a question section 1 left open — how many records actually share one disk access?
Speaker note: The answer is the blocking factor — and it does not eliminate waste, it only relocates where the waste happens.
Speaker note: This is the entire payoff of blocking — bf records for the price of one disk access, not bf separate accesses.
Speaker note: A partial last block still occupies a whole block on disk — block_flush writes it anyway, waste included.
Speaker note: The truck analogy makes both kinds of waste tangible: cargo space unused per trip, and a trip taken for very little cargo.
Speaker note: Watch the RAM buffer fill to bf, flush as one block write, then start over empty for the next block.
Speaker note: bf computes to 0 here — a real system must detect and reject this as a design error, never silently misbehave.
Speaker note: No last-block waste here — but internal fragmentation still happens inside every full block, since the two kinds of waste are independent.
Speaker note: block_flush is only ever called once, after the main loop — it is what pays the last-block waste.
Speaker note: Sections 4 and 5's O(numBlocks) and O(log numBlocks) both shrink directly as bf grows, because numBlocks = n / bf.
Speaker note: These two kinds of waste have different causes and different fixes — conflating them leads to the wrong optimization.
Speaker note: bf = floor(100/24) = 4; the wasted bytes are what is left over after bf*recSize.
Speaker note: 4 bytes looks trivial for one block — the "hard" scenario in the animation shows it compounding across many blocks.
Speaker note: Section 4 is Week 1's linear search, adapted to the fact that records arrive bf at a time, not one at a time.
Speaker note: With no sort order to exploit, the answer this section gives is: no — every block must be checked.
Speaker note: Comparing a few extra records already sitting in RAM costs almost nothing next to the disk access that loaded them.
Speaker note: This is Week 1's linear search, retold with disk-sized units — the box, not the paper inside it, is what costs time to open.
Speaker note: Normal example: bf=4 — watch the block-read counter, not the comparison counter, as the true cost.
Speaker note: An absent target costs exactly the same as finding the very last record — every block must be read either way.
Speaker note: One block read, one comparison — the best case, exactly as far from the worst case as this technique's variance ever gets.
Speaker note: block_reads increments once per block; comparisons increments once per record — only the first is this week's real cost.
Speaker note: A larger blocking factor from section 3 directly speeds up sequential search, since numBlocks shrinks as bf grows.
Speaker note: Unlike section 5's sorted file, an unsorted sequential file offers no shortcut at all for the not-found case.
Speaker note: Think about what the algorithm can conclude before it has read the final block.
Speaker note: This is the same shape of answer section 5 will contrast against a moment from now, once the file is sorted.
Speaker note: Section 5 asks what section 4 never used — the fact that the file could be sorted at all.
Speaker note: The answer is yes, with one twist: an entire block is ruled out per comparison, not one element.
Speaker note: Once binary search narrows down to one block, a short linear scan inside it (section 4's idea, bounded to bf) finds it or confirms a gap.
Speaker note: This is the edge case worth its own animation run — binary search narrows down WHICH block, not whether the key exists.
Speaker note: The label is exactly a block's first/last key — reading it costs one glance, ruling out everything on the wrong side.
Speaker note: Normal example: watch each comparison rule out an entire block's worth of records at once.
Speaker note: The target falls between two real keys in the same block — the short scan inside it correctly reports "not found".
Speaker note: The very first comparison against block 0's first key already rules out the whole file — no further reads needed.
Speaker note: Every iteration reads exactly one block, exactly like array binary search examines exactly one element.
Speaker note: Exactly like Week 1's binary vs. linear search on an array — same shape of speedup, one level up.
Speaker note: This algorithm must compare against a whole block's range, because a block of several records, not one record, is ruled in or out at each step.
Speaker note: Recall numBlocks = n / bf — think about whether this is a fundamentally different algorithm or the same one, one level up.
Speaker note: File binary search is binary search performed over groups of bf records, because block-oriented I/O forces that grouping.
Speaker note: Section 6 is the classical algorithm this whole topic is named for — updating a huge file without touching it record by record.
Speaker note: The alternative predates modern databases by decades — it comes straight from early batch-processing systems.
Speaker note: This pattern is one of the oldest ideas in file processing — it long predates the databases most students think of first.
Speaker note: This is literally the merge step of merge sort from Week 10, applied to two files instead of two arrays.
Speaker note: Whichever pointer is "behind" advances — this is exactly the same comparison logic as merging two sorted arrays.
Speaker note: A rejected transaction must never delete data nobody asked to delete — this is the single most important rule in this algorithm.
Speaker note: This two-reader picture is exactly Week 10's merge step, and it is the cleanest way to visualize why the algorithm never backtracks.
Speaker note: Normal example: 10 master records, 6 transactions mixing add/change/delete — watch both pointers advance together.
Speaker note: Two error types in one run: adding a key that exists, and changing/deleting a key that does not.
Speaker note: This is exactly the "leftover transactions" loop — some trailing adds succeed, some trailing changes/deletes are rejected.
Speaker note: This is exactly the merge-sort comparison structure from Week 10 — the only new part is the equal-key branch.
Speaker note: Forgetting the leftover loops after the main merge ends is the single most common bug in this algorithm.
Speaker note: This complexity gap is precisely why batch systems merge sorted files instead of searching for each transaction individually.
Speaker note: A single out-of-order record anywhere silently produces a wrong merge — not a crash, not an error message.
Speaker note: Think about what the new master file actually contains when the merge finishes.
Speaker note: Contrast this with section 10's tombstones, which need an explicit marker precisely because a probed file cannot be rewritten from scratch.
Speaker note: Section 7 is Week 1's array-indexing idea, moved to disk — no searching at all, just arithmetic.
Speaker note: The answer is no — and this is the fastest technique in the entire week, by a wide margin.
Speaker note: This costs exactly the same one block read whether the file holds a hundred records or a hundred million.
Speaker note: Computing a location instead of searching for it does not mean skipping validation — quite the opposite.
Speaker note: A numbered space is the cleanest possible picture of a computed address — nobody would search a garage floor by floor for a known number.
Speaker note: Normal example: bf=5, 13 records — watch every request cost exactly one block read, valid or invalid.
Speaker note: A negative rrn is rejected cleanly here — an unchecked one would compute a negative block and a corrupt fseek.
Speaker note: One valid rrn lands correctly in a block that is otherwise mostly empty; the very next rrn must still be rejected as out of range.
Speaker note: No loop, no comparison against stored data at all — this is genuinely the simplest algorithm of the entire week.
Speaker note: This is the theoretical ceiling every other technique this week is trying to approximate with a computed or hashed location.
Speaker note: An unvalidated rrn computed into an out-of-bounds fseek is exactly the kind of bug that corrupts a file, not just fails cleanly.
Speaker note: Think about how many blocks each technique must visit to find an answer, versus how many it must compute.
Speaker note: numBlocks = n / bf appears explicitly in both search techniques' complexity — never in direct access's.
Speaker note: Section 8 takes Week 6's hash table and moves it to disk, where "one slot" becomes "one block", not one cell.
Speaker note: Yes — and the key change is that one hash "slot" here is an entire block, which can already hold bf keys.
Speaker note: This is exactly Week 6's separate chaining, except the "linked list nodes" are now whole disk blocks, not individual records.
Speaker note: A mailbox that can already hold bf letters is the key difference from Week 6's RAM table, where every "mailbox" held exactly one letter.
Speaker note: Watch how many keys accumulate in one bucket before an overflow block is finally allocated.
Speaker note: With only one bucket, every key beyond the first bf collides — a long overflow chain, the worst case made maximal.
Speaker note: With m greater than 1 but every key still colliding, this isolates a bad hash outcome from a badly chosen m.
Speaker note: A new overflow block must chain onto the LAST block in the chain, never back onto the home bucket directly.
Speaker note: This is exactly Week 6's chaining degradation, now measured in block accesses instead of comparisons.
Speaker note: A collision here means "the bf-th key competing for one already-full block" — materially rarer than Week 6's one-key-per-slot.
Speaker note: Think about whether a colliding key stays inside the same table structure, or grows something separate.
Speaker note: Section 9's progressive overflow is the other family — claiming a different slot inside the same table, like Week 6's open addressing.
Speaker note: Section 9 is Week 6's open addressing, moved to disk — no separate structure at all, just keep probing.
Speaker note: Week 6's open addressing solved exactly this waste in RAM by keeping every key inside the original table.
Speaker note: Every slot probed, empty or not, costs one real disk access — this is why the technique's cost is measured in probes.
Speaker note: Unlike section 8's mailbox trays, there is no separate structure here at all — every key genuinely lives inside the one table.
Speaker note: Watch the probe sequence wrap around from the last slot back to slot 0 when a home slot is near the end.
Speaker note: Probe counts grow 1, 2, 3, ... in lock-step with insertion order — the textbook signature of primary clustering.
Speaker note: The last insert tries every one of the m slots and finds none free — a clean "file full" report, never an infinite loop.
Speaker note: Without the `tries < m` guard, a full table with no matching key would loop forever — this bound is not optional.
Speaker note: This is exactly Week 6's open-addressing degradation, now paid for in real disk accesses instead of RAM comparisons.
Speaker note: A well-designed program must detect and report a full file gracefully, exactly as the sample program above does.
Speaker note: Recall the Week 6 term — think about why an occupied run of slots keeps growing once it starts.
Speaker note: Any new key whose probe sequence reaches an existing run is forced to extend it by one more slot, making the next collision more likely too.
Speaker note: Section 10 asks what happens to section 9's probing when a key in the MIDDLE of a probe chain is deleted.
Speaker note: EMPTY is exactly the signal a search uses to give up — clearing a mid-chain slot breaks every key that comes after it.
Speaker note: Search and insert ask genuinely different questions here, which is exactly why they treat a tombstone differently.
Speaker note: The sign is the tombstone, in one image — it changes what a passing search does, without changing what a passing insert may do.
Speaker note: Watch a delete turn a slot into TOMB, then a later find() correctly skip past it to reach a key further along the chain.
Speaker note: No true-empty slot remains at all — only the tries < m bound from section 9 stops find() from probing forever.
Speaker note: The reinserted key lands back at its own home slot, reusing its own tombstone — a satisfying, and correct, round trip.
Speaker note: TOMB is neither "found" nor "safe to stop at" — it must be skipped exactly like any other occupied-but-different slot.
Speaker note: Reusing a tombstone reclaims deleted space without ever breaking any other key's probe chain.
Speaker note: A search was always going to walk past occupied slots anyway — tombstones just widen what counts as "occupied but passable".
Speaker note: The last case is exactly why the tries < m bound from section 9 is load-bearing, not a defensive nicety.
Speaker note: Think about what the slot looks like to a search, once it holds a real key again.
Speaker note: From any other key's point of view, an occupied slot is an occupied slot, whether original or reclaimed.
Speaker note: We now step back from individual algorithms to compare all five organisations side by side, and when to pick each.
Speaker note: The one column every row shares is the unit being counted — block reads and writes, from section 1, never comparisons.
Speaker note: No technique beats reading every block once when every record must be visited anyway — sorting buys nothing there.
Speaker note: The single biggest decision, as in Week 6, is: does this file need efficient exact-match lookup, or will it always be processed whole?
Speaker note: One question drove every section this week: how many block reads and writes does each technique need?
Speaker note: Every idea from Weeks 1, 6, and 10 reappears here, unchanged in logic, now paid for in block reads instead of RAM operations.
Speaker note: Recall section 1 — a block read costs orders of magnitude more than any in-memory operation on its contents.
Speaker note: This is the organizing idea of the entire week, stated once more as a review question.
Speaker note: Recall section 5 — an entire block, not one record, is ruled in or out at each step.
Speaker note: This is exactly the difference between array binary search (Week 1) and file binary search (section 5).
Speaker note: Recall section 6 — an unrelated rejected transaction must never delete valid data as a side effect.
Speaker note: This was a real bug found and fixed in this week's own reference programs while building them — a genuine, not hypothetical, mistake.
Speaker note: Recall section 10 — insert and search are answering fundamentally different questions.
Speaker note: This is the single most commonly mis-implemented detail of open addressing with deletion, in any language.
Speaker note: Recall section 7 — the arithmetic is the same one division and one modulo, no matter how many records exist.
Speaker note: Contrast this with every searching technique this week, whose cost is expressed directly in terms of numBlocks = n / bf.
Speaker note: Recall Week 6 — think about whether a collision grows a side structure, or claims a slot inside the same table.
Speaker note: Section 9's progressive overflow is the other Week 6 family instead — claiming a different slot inside the very same table.
Speaker note: Week 14 answers exactly the question sections 8-10 left open: what happens when a hashed file outgrows its m?
Speaker note: These are the same references listed at the end of the week's written notes.
Speaker note: Knuth's analysis of linear probing is the historical root of this week's "progressive overflow" terminology.