Database Systems
Committing your transactions…
Initializing Sorting Algorithms...
Sorting
Trees
Graphs
Preparing interactive visualizations...
Database Systems
Committing your transactions…
A database promises that your data stays correct while thousands of transactions run at once and the power can fail at any moment. Watch the machinery that keeps that promise.
Two transactions on one timeline. Switch from Read Uncommitted to Serializable and watch dirty reads, non-repeatable reads, phantoms and lost updates disappear.
Per-level read rulesLock tableIsolationFind the conflicting operations in a schedule, draw the precedence graph edge by edge, and read the equivalent serial order off it — unless there is a cycle.
O(n²) pairsO(T²) graphPrecedence GraphShared and exclusive locks in a lock table: a growing phase, a lock point, a shrinking phase — and the deadlocks and cascading aborts that strict 2PL deals with.
Waits on conflictLock tablePessimistic LockingEvery update writes a new version. Each transaction reads from its own snapshot, readers never block writers, and old versions wait for garbage collection.
Chain walk per readO(versions)Snapshot IsolationLog records with LSNs are forced to disk before the pages they describe. Then the power fails, and recovery redoes history and undoes the losers.
O(log length) recoveryAppend-only logCrash RecoveryA messy table, its functional dependencies and its update, insert and delete anomalies — then the table splitting apart through 1NF, 2NF, 3NF and BCNF.
Closure per FDLossless splitsSchema DesignParser, logical plan, cost-based optimizer, full scan against index scan, and the iterator model that pulls rows up to the client.
Parse → plan → executeBuffer poolQuery PipelineNested-loop, hash join and sort-merge join on the same two tables, counting every comparison to see which one wins and why.
O(nm) / O(n+m) / O(n log n)O(1) / O(m) / O(n+m)Join StrategyRows flowing through FROM, WHERE, GROUP BY, HAVING, SELECT, DISTINCT, ORDER BY and LIMIT in logical order — which is why a SELECT alias cannot appear in WHERE.
Logical pipelineIntermediate tablesQuery SemanticsSelection, projection, join, union, difference and rename on small tables, evaluating an expression tree from the leaves up.
Bottom-up evaluationOne relation per nodeExpression TreeWrites land in a memtable, flush to immutable SSTables and compact into larger levels; reads check newest first and skip tables with Bloom filters.
O(1) write, O(levels) readO(n) + filtersLog-Structured StorageThe update-in-place index that LSM trees are measured against: wide nodes that split and promote keys to stay shallow.
O(log n)O(n)Split / PromoteThe structure under almost every primary key: values live in linked leaves, so a range scan walks sideways.
O(log n)O(n)Linked LeavesMost concurrency bugs in application code are an isolation level doing exactly what it promised. Knowing which anomalies each level allows tells you when you need a stronger one, or a FOR UPDATE.
A commit returns once a log record is on disk, not the data. Write-ahead logging and its recovery pass are why a crash a millisecond later loses nothing you were promised.
Normal forms remove the redundancy that causes update anomalies, and the join and storage choices underneath decide whether the queries that put the data back together are fast.