Speaker note: Week 13 gave us a sorted file and a bucket-hashed file. This week asks: can a small index make search cheaper, can the index itself stay balanced forever, and can a hashed file grow without ever being rebuilt?
Speaker note: Eleven animations carry the whole lecture; every drawing labels disk pages by number and tracks reads/writes on the right.
Speaker note: Every term gets a full definition the first time it appears; this table just says where to find it again.
Speaker note: external_merge_sort and replacement_selection create real run files, but always inside a folder they create and delete themselves.
Speaker note: Everything this week either speeds up the sorted file with an index, or fixes the hashed file's fixed bucket count.
Speaker note: Today's B-tree family generalises Week 4's tree idea to pages that hold many keys, not one.
Speaker note: Every box on this map gets its own slides below, each with a step-by-step animation and a complete C/Java program.
Speaker note: Section 1 opens the indexing family: a tiny, memory-resident structure that turns page-by-page search into one page read.
Speaker note: Yes — if the structure is small enough never to touch disk at all, only the ONE data page read remains a real cost.
Speaker note: The tabs never leave your hand (memory); only opening the one right chapter costs a real "page turn" (disk read).
Speaker note: Because it holds one entry per page (not per record), it stays tiny even for a huge file.
Speaker note: The index alone can already prove a key absent, with zero disk I/O, in the "below range" edge case.
Speaker note: Normal example: 12 keys, block=4 — watch the index scan (free) hand off to a single page read.
Speaker note: Every single query is smaller than the smallest key: zero disk reads across the whole scenario.
Speaker note: The index is sorted, so once an entry's first_key exceeds the target, the loop can stop.
Speaker note: page == -1 short-circuits before any disk access; otherwise exactly one page is read and scanned.
Speaker note: A bigger installation would binary-search the index too, but the disk cost stays O(1) either way.
Speaker note: The third mistake is exactly ISAM's motivation for multiple index levels, coming up next.
Speaker note: Think about what a single page read already gives you once you know which page to read.
Speaker note: This is exactly why "sparse" works: the index only needs to answer "which page", not "which slot".
Speaker note: Section 2 generalises indexing to any attribute, including one that repeats across many records.
Speaker note: Yes — a dense index, sorted by the secondary key itself, makes duplicates cluster together.
Speaker note: The catalogue is dense (one card per book) and sorted by a DIFFERENT key than the shelves.
Speaker note: Dense costs more space (O(n)) than sparse (O(n/B)), the direct price of supporting any attribute.
Speaker note: Two matches sharing a page cost only one read total — the search tracks pages already visited this query.
Speaker note: Normal example: 12 records, block=4 — watch matches cluster together even though the data file is not sorted by this key.
Speaker note: The whole index is one giant cluster — the search still finds every match in a single pass.
Speaker note: "else if (count > 0) break" is the key line: it only stops once a cluster has actually started and ended.
Speaker note: Dense trades sparse's tiny footprint for the ability to search ANY attribute, including duplicates.
Speaker note: The data file's physical order and the dense index's sort order are usually completely unrelated.
Speaker note: Think about what a sparse index's "one entry per page" trick relied on.
Speaker note: A sparse index's trick only works because the file itself is sorted on that exact key.
Speaker note: Section 3 combines a multi-level index with a growth mechanism: the overflow area.
Speaker note: ISAM answers with two ideas: index LEVELS to keep the index small, and an OVERFLOW AREA to keep growth cheap.
Speaker note: ISAM predates the B-tree (1972) by roughly a decade — it is the file-organisation problem's first industrial answer.
Speaker note: The home page and its index entry never move; only its overflow chain grows.
Speaker note: This trade-off — cheap growth, degrading search — is exactly why real ISAM files need scheduled maintenance.
Speaker note: Normal example: 12 keys, block=4, fill=3 — watch two direct inserts, then a third that overflows.
Speaker note: Three inserts target the same already-full page; the third has to walk past two overflow nodes to be appended.
Speaker note: The two-level descent (find_group, then find_page) is the whole "index the index" idea in four lines.
Speaker note: L (index levels) stays small even for huge files, exactly the point of grouping level-2 under level-1.
Speaker note: The new record always attaches to its OWN home page's chain — never the shortest chain, never a neighbour.
Speaker note: Think about what happens to a single-level sparse index over a truly enormous file.
Speaker note: Exactly like a phone book's tabbed sections before the sorted page underneath.
Speaker note: Section 4 opens the B-tree family: an index that IS a self-balancing tree of disk pages.
Speaker note: That structure is the B-tree — every "node" a whole disk page, splitting and merging to stay balanced.
Speaker note: A B-tree's height stays O(log n) no matter how the file grows or shrinks — no separate rebalancing step, ever.
Speaker note: Growth always happens at the top (the root), never by adding a new bottom shelf.
Speaker note: In this week's presets, m=4 (mixed data) and m=3 (worst case, to make splits visible).
Speaker note: This cascading split is the entire mechanism that keeps the tree height O(log_m n).
Speaker note: Normal example: order=4, 12 mixed keys — watch the first split push a median up, then later a root split.
Speaker note: With order large relative to n, the whole tree stays a single leaf node — a clean contrast to the splitting cases.
Speaker note: A plain shift-insert into a sorted array — the same idea used by every insertion sort you have already seen.
Speaker note: The while loop is the cascade: it keeps checking upward until a node does not overflow, or the root splits.
Speaker note: Cascades reaching every level are rare in practice — most inserts cost just one leaf write.
Speaker note: Real B-trees use an order in the hundreds, sized so one node fills exactly one disk page.
Speaker note: Think about where growth happens, and how often.
Speaker note: Unlike an unbalanced BST, every leaf is always at the same depth as every other leaf.
Speaker note: Section 5 asks the simpler question: given a tree that already exists, how cheap is one lookup?
Speaker note: The answer will turn out to be bounded by the tree's height, plus one, no matter what.
Speaker note: A B-tree keeps every key reachable along a correctly-guided descent; falling off a leaf proves absence.
Speaker note: Normal example: order=4, 12 keys, 3 searches — watch a root-level hit versus a deeper, more expensive search.
Speaker note: With order=12 and only 10 keys, the whole file fits on one page — found or not, every search costs exactly one read.
Speaker note: The leaf check must come AFTER the match check but BEFORE descending — descending on a leaf reads garbage.
Speaker note: "Not found" is NOT free — the search still walks all the way to a leaf to be sure.
Speaker note: A wrong child index sends the search down the wrong subtree entirely — silently wrong, not a crash.
Speaker note: Think about what is true of every leaf's depth in a B-tree.
Speaker note: This is the direct structural guarantee Section 4's split-and-grow-from-the-root mechanism provides.
Speaker note: Section 6 mirrors insertion's split with deletion's two repair moves: borrow, or merge.
Speaker note: Yes — a page just short of the minimum can often borrow a single spare key from a neighbour instead.
Speaker note: Every delete reduces, one way or another, to a leaf removal plus a possible chain of fix-ups above it.
Speaker note: Borrow resolves in one step, touching 3 pages; merge removes a page and a key from the parent.
Speaker note: This is the only way a B-tree ever loses a level — always at the top, never by pruning a leaf.
Speaker note: Normal example: order=4, 12 keys, 3 deletes — watch a leaf removal that needs no fix-up at all.
Speaker note: Seven deletions on an order=3 tree, each a merge, until the root itself empties and the tree loses a level.
Speaker note: A borrow is strictly cheaper — it resolves in one step, with no risk of cascading further.
Speaker note: The real removal always happens at the PREDECESSOR's original leaf, never at the internal node itself.
Speaker note: Think about how many pages each option touches, and whether either can cascade.
Speaker note: Same "cheaper local fix first" spirit as a dynamic array preferring in-place growth over reallocation.
Speaker note: Section 7 asks about range queries — and answers with one structural change: a chain linking every leaf.
Speaker note: Yes — if every leaf already knows which leaf comes next, no climbing is ever needed again.
Speaker note: The chain turns "re-descend for every match" into "walk sideways", a huge win for large result sets.
Speaker note: Forgetting to splice next before overwriting it silently drops every leaf after the split point.
Speaker note: Normal example: order=4, 12 keys, 3 range queries — watch the orange chain arrows carry the query sideways.
Speaker note: The query walks the ENTIRE chain to the end — never once climbing back to the root.
Speaker note: ONE descent (find_leaf), then a pure sideways walk — no recursion, no re-visiting internal nodes.
Speaker note: The bigger the result set, the bigger the B+-tree's advantage over a plain B-tree's range query.
Speaker note: The third mistake works correctly, but throws away the entire benefit of the leaf chain.
Speaker note: Think about what information a B+-tree leaf has that a plain B-tree leaf does not.
Speaker note: This one pointer per leaf is the entire structural difference behind the B+-tree's range-query speed.
Speaker note: Section 8 returns to hashing, now letting the bucket count itself grow on demand.
Speaker note: Extendible hashing's answer: separate a small, memory-resident directory from the data buckets on disk.
Speaker note: This directory/data separation is the design pattern later reused by dynamic and distributed hash tables.
Speaker note: Doubling is pure memory work — zero disk cost — it just creates more, finer-grained pointers to redirect.
Speaker note: The retry is essential — without it, a key that shares the new bit with everything else would be lost.
Speaker note: Normal example: capacity=2, 10 keys — watch the directory double the first time a bucket's local_depth catches up.
Speaker note: Every key is 8 mod 16 — the directory grows all the way to depth 7 before the keys finally separate.
Speaker note: The recursive retry at the end is what handles the "one split was not enough" cascading case.
Speaker note: Every doubling allows twice as many future inserts before the next one is needed.
Speaker note: An unlucky split can leave a brand-new bucket with zero keys, waiting for a future insert.
Speaker note: Think about how many directory slots can point to the NEW bucket right after a split.
Speaker note: Doubling first creates exactly the additional slots the split then needs.
Speaker note: Section 9 achieves the same dynamic growth as Section 8, but with no directory at all.
Speaker note: Linear hashing's answer: commit in advance to a fixed, predictable splitting order.
Speaker note: Litwin's scheme traded extendible hashing's directory for a single counter, n.
Speaker note: The address rule's one "bump" condition is the entire trick that keeps addressing correct as buckets split.
Speaker note: This is linear hashing's most distinctive — and most often mis-implemented — rule.
Speaker note: Normal example: N0=4, capacity=2, 10 keys — watch an overflow trigger a split of a DIFFERENT bucket.
Speaker note: N0=2, capacity=1 — splits happen so often that a full round completes, n resets, and level increases.
Speaker note: split() always operates on h->n — never on whichever bucket triggered the call.
Speaker note: Simplicity (no directory) is paid for with a looser worst-case bound on any one bucket.
Speaker note: The split target is always "whichever bucket comes next in round-robin order" — completely predictable.
Speaker note: Think about how predictable the next split target is.
Speaker note: The price: a bucket can grow past capacity until its own turn to split finally arrives.
Speaker note: Section 10 tackles sorting a file too large for RAM — a genuinely different algorithm from Week 10's.
Speaker note: The divide step adapts easily; the combine (merge) step needs a fundamentally different implementation.
Speaker note: The two-phase run-then-merge structure traces directly back to this tape-based era.
Speaker note: RAM only ever holds FAN_IN buffers plus one output buffer, however enormous the file is.
Speaker note: This is a small but real optimisation this week's programs implement.
Speaker note: Normal example: 12 values, RUN_SIZE=4, FAN_IN=2 — watch the first merge's small per-run buffers shrink as values are consumed.
Speaker note: Every value starts as its own run — many more merge passes are needed than the normal case.
Speaker note: Only the CURRENT front value of each run needs to be in RAM — never a whole run at once.
Speaker note: Both external_merge_sort and replacement_selection follow this same safe lab-folder pattern.
Speaker note: Dramatically less than trying to load the whole file into memory at once.
Speaker note: FAN_IN buffers, one per run merged simultaneously — bounded by real available memory, not convenience.
Speaker note: Think about how much of a run a k-way merge actually needs to see at once.
Speaker note: The exact generalisation of Week 10's two-way merge, which likewise only ever looks at two "current" elements.
Speaker note: Section 11 asks: can Phase 1's runs be made longer than RAM, using the SAME RAM?
Speaker note: Replacement selection's answer: a record smaller than the last one WRITTEN starts the next run instead.
Speaker note: The comparison is against the last value WRITTEN, never against the window's own current minimum.
Speaker note: The worst case is no better than Section 10's plain fixed-size chunking — the win is average-case, not guaranteed.
Speaker note: Normal example: RAM=4, 12 mixed values — watch window boxes switch between "current" and "next" labels.
Speaker note: With RAM big enough to hold everything, the result is always ONE fully sorted run, whatever the input order.
Speaker note: Returns -1 when nothing is tagged CURRENT — the signal that this run has ended.
Speaker note: The code here scans the window linearly, O(m) per record, for clarity — a heap makes it O(log m).
Speaker note: This average-case win is exactly why real database and OS sort utilities use replacement selection.
Speaker note: Carrying over the previous run's last value would wrongly tag some of the new run's earliest records.
Speaker note: Think about what fraction of the window is typically CURRENT-tagged at any moment.
Speaker note: A classical result, analysed in full in Knuth's TAOCP, Volume 3.
Speaker note: The closing section turns everything this week covered into one decision table.
Speaker note: The index rows assume a mostly-static file; ISAM's overflow area is what makes inserts survivable at all.
Speaker note: "Never reorganise" is the B-tree family's other great property, alongside logarithmic search.
Speaker note: This is the exact same question Week 13 first raised — sharpened now by everything this week added.
Speaker note: Every B-tree-family operation keeps the tree balanced as it goes — no separate rebalancing pass, ever.
Speaker note: Both hashing schemes grow one bucket at a time, on demand, with no reorganisation pass.
Speaker note: Ten questions, restated from the week's notes, one per slide pair.
Speaker note: Recall Section 1.
Speaker note: Only the one data page it points to is a real disk read.
Speaker note: Recall Section 2.
Speaker note: This is what makes duplicate values cluster together in a dense index.
Speaker note: Recall Section 3.
Speaker note: This trade-off is exactly why real ISAM files need periodic reorganisation.
Speaker note: Recall Section 4.
Speaker note: Half the keys stay, half move to a new sibling, and the median separates them in the parent.
Speaker note: Recall Section 5.
Speaker note: A search either finds its key early, or walks to a leaf — never past one.
Speaker note: Recall Section 6.
Speaker note: A B-tree only merges when NO sibling has a spare key to lend.
Speaker note: Recall Section 7.
Speaker note: A plain B-tree has no such shortcut between neighbouring leaves.
Speaker note: Recall Section 8.
Speaker note: Doubling creates the spare, more-specific slots a split then needs to redirect.
Speaker note: Recall Section 9.
Speaker note: This predictability is exactly what removes the need for any directory.
Speaker note: Recall Section 11.
Speaker note: A classical result analysed in Knuth's TAOCP, Volume 3.
Speaker note: Every structure from this week remains in daily production use — B+-trees in almost every relational database, external merge sort in every database's sort/index-build utility.
Speaker note: These are the same references listed at the end of the week's written notes.
Speaker note: The historical references — Bayer/McCreight, Fagin et al., Litwin — are what today's "short history" slides drew on.