---
title: "Databases overview"
description: "Watch SQL reshape rows, indexes trade page reads, B+ and LSM trees organize storage, and MVCC snapshots select among concurrent row versions."
source: https://vizlearn.app/cs/databases
---

# Database Visualizations

Database queries become easier when you separate the logical result from the physical work used to produce it. **SQL Joins** derives one relation from two source tables. **GROUP BY & Aggregation** partitions one relation and reduces every group to one result row. **Window Functions** computes across related rows while preserving every row identity. **Database Indexing** holds the result constant while comparing the heap and index pages touched by several access paths. **B+ Tree** opens one ordered access path and shows how its pages split, route, and link together. **LSM Tree** follows a write-optimized path from WAL and memtable through sorted flushes, newest-first reads, and compaction. **MVCC** adds concurrency: one stored row may have several logical versions, and each snapshot selects the newest version visible to it.

The distinction matters. Joins can expand cardinality, grouping can contract it, and a window function preserves it. An index changes where the engine looks, an LSM tree changes when sorted-storage work occurs, and MVCC changes which stored version is valid for one reader's snapshot.

## Compare the lessons

| Lesson | Input shape | Deciding rule | Cardinality trap |
|---|---|---|---|
| SQL Joins | two relations | emit every row pair whose keys compare `TRUE`; the join type decides which unmatched rows survive | duplicate keys multiply: `L_k × R_k` |
| GROUP BY & Aggregation | one relation | assign each row to its complete grouping-key tuple, then emit one row per group | `COUNT(*)` and `COUNT(column)` disagree when the column contains `NULL` |
| Window Functions | one relation | partition, order within each partition, then compute one value per current row | window-local `ORDER BY` controls calculation, not final output order |
| Database Indexing | one page-backed relation plus a predicate and projection | choose a scan, hash bucket, or ordered leaf path; follow RIDs unless the leaf covers the projection | a valid low-selectivity index can cost more page reads than a scan |
| B+ Tree | ordered insert, search, and range operations | route through internal guides; copy leaf separators, push internal separators, then scan linked leaves | treating a guide as the only record copy can make a range silently lose data |
| LSM Tree | versioned put, get, and delete operations | append WAL, update ordered memory, flush sorted L0 runs, then keep the greatest sequence during compaction | treating a tombstone as a miss or searching old runs first can resurrect stale data |
| MVCC | one logical row, concurrent transactions, and snapshots | scan versions newest to oldest; creator must be committed in the snapshot and no committed superseder may hide the candidate | a committed new version cannot be reclaimed while an active old snapshot still selects its predecessor |

The first three diagrams do not promise a physical algorithm. They explain logical pairs, groups, partitions, frames, and peers. Database Indexing then isolates the physical-choice layer with an explicit cold-page model. SQL specifies the relation you should get; the optimizer decides how to get it.

## A Recommended Order

Start with **SQL Joins** on the default LEFT JOIN. Key 10 creates two result rows because Ada has two matching offices. Keys 20 and 40 have no office partner, so LEFT preserves their employee rows and fills the right columns with `NULL`. The closing ledger compares INNER 3, LEFT 5, and FULL 6 on the same inputs.

Then run **GROUP BY & Aggregation** with `GROUP BY region`. Seven interleaved sales rows form North, South, and West groups. North receives three rows but only two non-`NULL` amounts, so it emits `COUNT(*) = 3`, `COUNT(amount) = 2`, `SUM(amount) = 200`, and `AVG(amount) = 100`. Finish on the grouping selector: the same source relation produces 1 global group, 3 region groups, or 6 `(region, channel)` groups.

Next run **Window Functions** with Running SUM. North and South form independent partitions, each ordered by day. The prefix frame grows to the current row and writes its sum back to that row id, so seven input rows remain seven output rows. Switch to RANK and DENSE_RANK to see peer rows share a value while only ordinary RANK leaves gaps after a tie.

Continue with **Database Indexing** on its default B+ tree point lookup. The same one-row result costs eight heap-page reads by scan, three reads through a non-covering B+ tree, and two through either the hash or covering path. Then switch to `low-selectivity`: the selected non-covering tree costs 12 reads against the scan's eight, making optimizer rejection concrete.

Then run **B+ Tree** to see where an ordered leaf path comes from. Six inserts at order 3 produce a cascading split and a three-level tree. Leaf separator 30 is copied upward while its record stays in the right leaf; internal guide 20 is pushed into a new root and removed from both split internal pages. The closing range descends once, follows three leaf links, and returns `10, 15, 20, 25`.

Then run **LSM Tree** to compare a write-optimized ordered structure. Six mutations become two sorted L0 files. A memtable update and tombstone both stop reads before an older L0 value can leak through. Full bottommost compaction reads six stored versions, writes three live L1 records, installs the output, and only then retires its inputs. The Read amplification preset leaves three overlapping L0 runs so a missing key probes memory plus all three files.

Then run **MVCC** at Repeatable Read. T1 freezes S1=`{T0}` and keeps returning `$100` while T2 appends and commits `$120`; later snapshot S2 includes T2 and returns `$120`. Cleanup first stops because S1 still needs the old version, then reclaims it after T1 ends. Switch to Read Committed to hold the update fixed while statement snapshots change the third T1 result to `$120`.

That order moves from expansion to contraction to row-preserving analytics, then from logical results to physical access, two different ordered-storage strategies, and finally concurrent visibility. Once the cardinality rules are explicit, a common reporting bug becomes easier to diagnose: if a join duplicates an order before grouping or windowing, later calculations faithfully see every duplicate. Indexing cannot repair that logical mistake; it can only change how the database reaches those rows. MVCC likewise does not change the query's rule; it chooses the row version that satisfies one snapshot.

## What to Watch

- In SQL Joins, count row pairs, not distinct key values. Two left rows and three right rows at one key produce six matched rows.
- `NULL = NULL` is not `TRUE` in the equality join lesson, so it creates no matched pair.
- In GROUP BY, every source row has exactly one membership for the selected key tuple.
- Grouping treats multiple `NULL` key values as one group. That is deliberately different from equality-join matching.
- `COUNT(*)` counts rows. `COUNT(amount)`, `SUM(amount)`, and `AVG(amount)` ignore `NULL` amounts.
- In Window Functions, `PARTITION BY` restarts the calculation without collapsing the partition.
- A running `ROWS` frame grows by logical row position; ranking peer groups are defined by equal window-order values.
- `RANK` leaves gaps after peers; `DENSE_RANK` does not.
- Result order is unspecified in all three logical relation lessons until a query adds outer `ORDER BY`.
- In Database Indexing, count page reads rather than matching rows. Several RIDs on one heap page share one fetch.
- Hash indexes support equality but do not preserve the key order needed by `BETWEEN`.
- A covering leaf avoids a heap fetch only when it stores the current query's projected column.
- In B+ Tree, equality follows the child to the right of a matching guide because copied leaf separators name the right subtree's first key.
- Leaf splits copy a separator; internal splits push one. Check whether the separator still appears in the split pages.
- A range scan descends once and then follows `next`; restarting at the root discards the main benefit of the leaf chain.
- In LSM Tree, every mutation reaches the WAL before memory, while a flush follows sorted key order rather than arrival order.
- L0 reads run newest to oldest and stop on either a value or a tombstone. Compaction chooses by sequence number, not input position.
- A tombstone can disappear only after the modeled full overlap reaches bottommost L1; dropping it with older unselected data can resurrect that data.
- In MVCC, distinguish the newest stored version from the newest version visible in one snapshot.
- Repeatable Read keeps T1's first-statement snapshot fixed; Read Committed refreshes it for each statement.
- Cleanup follows the oldest active visibility need, not merely the latest committed balance.

Pick the layer you need to understand, then keep your eye on its unit: one row per matching pair, one row per group, one value per preserved row, one logical page read per physical page touched, one guide or record key in its B+ tree layer, one logical mutation/source probe/rewritten version in the LSM tree, or one row version selected for one snapshot.