CS 411 Visual Guide to Database Internals

An index tells a database where to look. It does not make the data free to read. A join combines records, but its implementation determines whether a table is read once or repeatedly. Transactions can overlap without behaving as though they ran one at a time.

This guide follows those mechanisms beneath the query language. It deliberately skips SQL syntax. The seven diagrams are small, step-by-step teaching models based on the supplied CS 411 lectures, not implementations of a particular database engine.

Use Next to change one state at a time, Back to compare, and Reset to replay. Changing a scenario restarts that diagram. On narrow screens, scroll horizontally instead of shrinking the labels.

Pages and scans

The unit transferred between disk and memory in the course model is a page, also called a block. Even if only one record is needed, the database reads its page first.

The diagram has twelve records, two per page. Find keys 5 through 8 using either a table scan or an index. Then scatter the same records across more pages.

The result is always four records. The clustered index path reads two data pages; the scattered path reads four; the table scan reads six. An index’s sorted entries do not imply that the corresponding records are physically adjacent.

These counters cover data-page reads only. Index navigation is additional work. Assume a cold start, no eviction of visited pages, and no index-only answer: the query needs data beyond the index. A real buffer pool, prefetching, and sequential versus random I/O affect elapsed time. Page counts are a useful model, not a stopwatch.

B+ tree navigation and leaf splits

Internal keys direct the search; leaf entries lead to records. For a range, find its lower bound once, then follow the leaf chain until the keys exceed the upper bound.

Key 25 is absent, but the range still returns 30, 40, 50, 60, and 65. Seeing 80 establishes where to stop. Fetching records is separate from navigating the index.

Switch to insertion. With the lecture’s convention d=2, a non-root leaf holds two to four keys. Adding 25 to a full leaf creates an overflow. Split it into two and three entries, repair the next-leaf links, and copy the first key of the right leaf into the parent. That key remains in the leaf.

Intermediate frames explain an update; they are not states exposed to concurrent readers. The parent has space here. A full parent could force further splits, possibly creating a new root. Internal-node splitting is not identical to copying a leaf separator. Deletion, redistribution, latching, and recovery are outside this example.

Hash directory growth and bucket splitting

A hash index groups keys by hash bits rather than maintaining an ordered leaf chain. This section uses extensible hashing, with the lecture’s leftmost-bit convention.

Global depth determines directory size. Local depth records how many bits distinguish one bucket. Several directory entries may point to the same physical bucket.

In the first scenario, the full bucket has local depth equal to global depth. Grow the directory, split that bucket, and redistribute entries using one more bit. Doubling the directory does not duplicate every data page.

The second scenario starts after the first insertion and an additional 0000. The directory uses two bits, but the shared 0 bucket uses one. Inserting 0101 only requires splitting that bucket and redirecting pointers; the directory stays at four entries.

The bit strings are hash outputs, not encryption. This example avoids identical hashes and stops before exhausting its four-bit space. Long shared prefixes can require repeated expansion; an in-memory directory and one bucket read are assumptions, not an unconditional one-I/O guarantee. Linear hashing, a separate technique in the lectures, grows more gradually and may retain overflow pages.

External merge sort

When a relation does not fit in memory, sorting needs temporary storage. First sort memory-sized chunks into runs on disk. Then merge the runs, keeping only an input page from each run and an output buffer in memory.

Here B(R)=6 and M=3. Run generation reads six pages and writes six. The merge reads those six pages again. It compares current heads, preserves duplicates, and loads another page only when needed.

The course excludes the final output write because another operator may consume it directly. Under that convention, the total is 3B(R)=18 page I/Os. Turn on Write final output to include six more writes: 4B(R)=24. Temporary run writes are counted in both modes.

A two-pass sort requires ceil(B(R)/M) ≤ M−1: the initial runs must fit the available merge input buffers. With three buffers, six pages fit that limit, but nine pages produce three runs and need another merge pass. This is the simple fixed-size-run algorithm; replacement selection and engine-specific optimizations are not modeled.

Join buffers and repeated reads

Block nested-loop join keeps an outer chunk in memory while scanning the inner relation. The expensive part is often starting that inner scan again for the next chunk.

Reserve one buffer for the inner relation and one for output. That leaves M−2 for the outer relation. The read cost is:

B(R) + ceil(B(R) / (M − 2)) × B(S)

With four pages on each side, three buffers force four complete scans of S. Four buffers reduce that to two scans. Six buffers hold all of R, so S is scanned once. Assume no extra cache retains S between scans; output writes and CPU costs are excluded.

This does not make nested loops the universal choice. A one-pass hash join builds a lookup structure from the smaller input when it fits the memory budget, then probes while scanning the other input. With larger data, partitioned hash join first writes matching hash partitions to disk and joins each pair; skew can leave a partition too large. Sorted inputs can favor merge join. Memory, key distribution, indexes, and required output order all matter.

Filter placement and intermediate rows

A logical rewrite can reduce work before choosing a physical join algorithm. If an inner join is followed by a filter using only customer columns, moving that filter onto the customer input can reduce rows entering the join without changing the answer.

The synthetic data is uniform: one hundred customers, exactly ten orders each, and valid references from every order to one unique customer. At 5% selectivity, filtering first produces fifty joined rows instead of a thousand. At 80%, the gap is smaller.

These are row counts, not runtime estimates. Both plans fully scan the base inputs here. There is no index shortcut. Output can be pipelined rather than materialized as a temporary table. This comparison isolates the amount of data passing through the join.

An optimizer also considers access paths, join order, algorithms, and statistics. The lectures build larger candidate plans from smaller ones using dynamic programming. If estimates are wrong because of skew or correlated columns, an apparently cheap plan can be expensive. Do not generalize this rewrite to every outer join, aggregate, or expression with side effects.

Transaction schedules and conflict graphs

Operations can interleave while remaining equivalent to a serial order. To check conflict serializability, build a precedence graph.

Each node is a transaction. Add an edge from the earlier transaction to the later one when operations touch the same item and at least one is a write. Read/read pairs do not conflict. Check all relevant earlier operations, not only the adjacent one.

Both examples preserve each transaction’s R(A), W(A), R(B), W(B) sequence. Only their interleaving changes. The first requires T1 before T2 consistently. The second requires T1 before T2 on A but T2 before T1 on B, producing a cycle.

An acyclic complete graph gives a conflict-serializable schedule; a topological ordering gives an equivalent serial order. No cycle yet is not a final verdict on an unfinished schedule. A cycle rejects conflict serializability, but does not by itself settle the broader question of view serializability.

This is not a deadlock diagram: edges mean conflicting-operation order, not waiting for a lock. Commit, abort, recoverability, locking protocols, and MVCC are separate topics, not implied by a successful graph check.

Using the diagrams for revision

Before advancing, ask what must change: a page in memory, a pointer, a buffer allocation, an intermediate row count, or an edge. Explain why that change is necessary. Predicting the next state is more useful than remembering an animation.

Continue with B+ trees and hash indexes, physical operators, query optimization, or transactions and isolation for the fuller notes.

Lecture sources and scope

Based on the supplied CS 411 Database Systems lecture material by Abdu Alawini. These are independently drawn study aids, not official course animations. Corresponding transcripts inform the explanations; spoken or transcribed numerical slips are not treated as definitions.

Recovery and WAL are not added here: the supplied lecture set has no dedicated recovery lecture. SQL, ER modeling, and product-specific engine behavior are also outside this guide’s scope.