System Design Data Storage and Databases Syllabus

Data Storage and Databases syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Data Storage and Databases in System Design, not a summary of it.

1. 1

   Relational Databases

   4 topics

   • ACID Transactions
   • Normalization and Schema Design
   • Indexing and B-Trees
   • Isolation Levels and Locking
2. 2

   NoSQL Databases

   5 topics

   • Key-Value Stores
   • Document Stores
   • Wide-Column Stores
   • Graph Databases
   • BASE vs ACID
3. 3

   Database Scaling

   4 topics

   • Replication
   • Sharding and Partitioning
   • Federation and Denormalization
   • Read Replicas and Write Scaling
4. 4

   Storage Engines and Data Structures

   4 topics

   • LSM Trees and SSTables
   • B-Tree Storage Engines
   • Write-Ahead Logging
   • Bloom Filters
5. 5

   Specialized Data Stores

   4 topics

   • Time-Series Databases
   • Search Engines and Inverted Indexes
   • Object and Blob Storage
   • Data Warehouses and OLAP
6. 6

   Distributed Transactions

   4 topics

   • Two-Phase Commit
   • Saga Pattern
   • Outbox Pattern
   • Idempotency and Exactly-Once Semantics

Data Storage and Databases flashcards for System Design

24 of 51 cards from the Data Storage and Databases deck — real questions with worked answers.

1. What does the ACID acronym stand for in database transactions?

   Atomicity, Consistency, Isolation, Durability. Together they guarantee that transactions are processed reliably even under failures and concurrency.

2. Define Atomicity in the context of ACID transactions.

   A transaction is all-or-nothing: either every operation commits successfully, or the entire transaction is rolled back leaving no partial effects.

3. What does Durability guarantee in an ACID transaction?

   Once a transaction is committed, its changes persist permanently even if the system crashes immediately afterward, typically ensured via write-ahead logging or fsync to non-volatile storage.

4. In relational normalization, what condition defines First Normal Form (1NF)?

   Every column holds atomic (indivisible) values and there are no repeating groups or arrays; each cell contains a single value.

5. State the rule for Second Normal Form (2NF).

   The table is in 1NF and every non-key attribute is fully functionally dependent on the whole primary key (no partial dependency on part of a composite key).

6. State the rule for Third Normal Form (3NF).

   The table is in 2NF and has no transitive dependencies: non-key attributes depend only on the primary key, not on other non-key attributes.

7. What is Boyce-Codd Normal Form (BCNF) and how does it strengthen 3NF?

   BCNF requires that for every non-trivial functional dependency $X \to Y$, $X$ must be a superkey. It removes anomalies that 3NF can still permit when candidate keys overlap.

8. What is the main trade-off of normalization?

   Normalization reduces data redundancy and update anomalies but requires more joins at read time, which can hurt read performance; denormalization trades storage/consistency for faster reads.

9. What is a database index and what is its primary purpose?

   An auxiliary data structure that maps column values to row locations, allowing lookups to skip full table scans, reducing search from $O(n)$ toward $O(\log n)$.

10. Why are B-Trees (B+ Trees) the standard structure for database indexes?

    They are balanced, keep data sorted, have high fan-out so trees stay shallow, and support $O(\log n)$ lookups, inserts, deletes, and efficient range scans while matching disk page sizes.

11. In a B+ Tree, where are the actual data pointers stored versus internal nodes?

    All keys and record pointers live in the leaf nodes, which are linked in a sorted linked list; internal nodes hold only routing keys to guide the search.

12. For a B-Tree of order $m$ holding $n$ keys, what is the search time complexity?

    $O(\log_{m} n)$ node accesses, so height stays low; because fan-out $m$ is large (hundreds), even billions of rows need only a few disk reads.

13. What is the trade-off between more indexes and write performance?

    Each index speeds reads but must be updated on every insert/update/delete, adding write overhead and storage; over-indexing slows writes.

14. Name the four standard SQL isolation levels from weakest to strongest.

    Read Uncommitted, Read Committed, Repeatable Read, Serializable.

15. Which read phenomenon does Read Committed prevent but Read Uncommitted allow?

    Dirty reads (reading uncommitted data from another transaction). Read Committed only sees committed data; Read Uncommitted can see uncommitted changes.

16. What is a phantom read and which isolation level prevents it?

    A phantom read occurs when a re-executed range query returns new rows inserted by another committed transaction. Only Serializable fully prevents phantoms.

17. Match the three read anomalies to the isolation levels that permit them.

    Read Uncommitted allows dirty reads, non-repeatable reads, phantoms. Read Committed allows non-repeatable reads and phantoms. Repeatable Read allows phantoms only. Serializable allows none.

18. What is the difference between a shared lock and an exclusive lock?

    A shared (read) lock permits concurrent readers but blocks writers; an exclusive (write) lock blocks all other readers and writers. Multiple shared locks coexist; an exclusive lock is incompatible with any other lock.

19. What is Two-Phase Locking (2PL) and its two phases?

    A concurrency protocol guaranteeing serializability: a growing phase where a transaction only acquires locks, and a shrinking phase where it only releases them. No lock is acquired after any is released.

20. What is Multi-Version Concurrency Control (MVCC)?

    A technique where writes create new versions of rows rather than overwriting, so readers see a consistent snapshot without blocking writers, avoiding read-write lock contention.

21. What is a key-value store and its core operations?

    The simplest NoSQL model: an associative map of unique keys to opaque values, supporting $O(1)$ average get(key), put(key, value), and delete(key). Examples: Redis, DynamoDB, Riak.

22. What data model does a document store use and how does it differ from key-value?

    It stores semi-structured documents (JSON/BSON/XML) whose fields can be indexed and queried, unlike opaque key-value blobs. Examples: MongoDB, CouchDB.

23. Describe the wide-column store data model.

    Data is stored in tables of rows keyed by a row key, where each row can have different columns grouped into column families; optimized for large-scale writes and sparse data. Examples: Cassandra, HBase, Bigtable.

24. What problem are graph databases optimized for, and what are their core primitives?

    They model highly connected data using nodes (entities) and edges (relationships with properties), enabling efficient traversal of relationships (e.g., social graphs) that would require many costly joins in SQL. Examples: Neo4j, Amazon Neptune.

See more Data Storage and Databases flashcards →

Planning Data Storage and Databases for System Design

Data Storage and Databases (System Design) FAQ