Interview casebook · quick reference

Database Patterns

A decision sheet for storage layout, indexes, transactions, query execution, and data movement.

DB MAP
OLTPShort consistent writes
OLAPScans and aggregates
IndexExtra writes for fast reads
LogOrder, replay, recovery

Storage engine decision

B-treePage-oriented ordered index. Strong point and range reads, in-place page updates, broad OLTP fit.
LSM treeMemtable plus immutable sorted files. High write throughput, compaction cost, Bloom filters for missing keys.
Append logSequential writes and simple recovery. An in-memory directory finds latest records; compaction removes stale versions.
Column storeValues grouped by column for compression and analytical scans over a subset of fields.

Index menu

  • Hash: equality lookup, no ordering.
  • B-tree: equality, range, prefix, and ordered traversal.
  • Composite: leading-column order determines usable query prefixes.
  • Covering: index contains every field needed by the query.
  • Inverted: token or field value to matching document IDs.
  • Geo: geohash, quadtree, R-tree, or search-engine geo index.
selectivity = matching rows / total rows

Query execution

  1. Parse SQL into an abstract syntax tree.
  2. Resolve names, types, and permissions.
  3. Rewrite predicates and estimate cardinalities from statistics.
  4. Choose access path, join order, and physical operators.
  5. Execute as iterators or vectorized batches.
  6. Spill hash tables or sorts when memory budget is exceeded.
nested loop ≈ outer_rows × inner_lookup_costsort ≈ O(N log N)

Transactions and concurrency

2PLLocks are held through the transaction. Conflicts block; deadlocks need detection or ordering.
MVCCReaders see a snapshot while writers create versions. Vacuum reclaims obsolete versions.
OCCRead freely, validate version at commit, retry after conflict. Effective under low contention.
WALLog records reach durable storage before changed pages. Recovery redoes committed work and undoes incomplete work.

Distributed data patterns

  • Outbox: write domain change and outgoing event in one local transaction.
  • CDC: convert database log changes into an ordered event stream.
  • Idempotency: unique operation key returns the original result on retry.
  • Saga: coordinate local transactions through events and compensations.
  • Quorum: choose read and write replica counts for overlap.
  • Reconciliation: compare derived state with an authoritative source and repair drift.
strong overlap when R + W > N

Fast calculations

QPS ≈ daily operations / 86,400storage ≈ rows × bytes/row × retention × replicasbandwidth ≈ QPS × average payloadavailability series ≈ A₁ × A₂ × ... × Aₙavailability parallel ≈ 1 - Π(1 - Aᵢ)

Recall test

  1. Which index serves equality plus range queries?
  2. What durable ordering rule makes WAL recovery work?
  3. When does OCC perform well?
  4. How does an outbox prevent a database and queue split?