Databases

Overview Serializable isolation guarantees that concurrent transactions produce a result equivalent to some serial order, eliminating every possible race condition. Weaker isolation levels like Read Committed or Snapshot trade that guarantee for higher throughput, deliberately allowing certain read/write anomalies that application code must tolerate or guard against. Comparison Diagram SerializableWeaker IsolationT1T2time (T1 fully precedes T2)No overlap in effect =equivalent to a serial runT1T2time (T1 and T2 overlap)Overlap window =dirty/non-repeatable reads,phantoms, or write skew possible Comparison Table Aspect Serializable Weaker Isolation Isolation guarantee Result equivalent to some serial execution of all transactions Allows specific interleavings; guarantee varies by level (Read Committed, Repeatable Read, Snapshot) Concurrency control Full conflict serializability via strict two-phase locking, serializable snapshot isolation (SSI), or predicate locks Row-level locks or MVCC snapshots that only block on narrower conflict sets (e.g. write-write) Anomalies prevented Dirty reads, non-repeatable reads, phantom reads, and write skew all eliminated Only a subset prevented; phantoms and write skew commonly remain possible Contention behavior Higher rate of lock waits, deadlocks, or serialization-failure aborts under concurrent access Readers rarely block writers (MVCC) or lower lock scope, so contention is reduced Throughput impact Lower throughput and higher latency as concurrency increases, especially with hot rows Higher throughput and better scalability under contention Application responsibility Application can assume correctness; only needs to retry on serialization-failure errors Application must reason about anomalies and add explicit checks (e.g. version columns, SELECT FOR UPDATE) Conflict detection timing Detected either at lock-acquisition time or at commit time (optimistic serializable schemes) Detected only for the narrower conflicts the level covers, often just at commit for MVCC writes Default in major databases Rarely the default; must be explicitly requested (e.g. SET TRANSACTION ISOLATION LEVEL SERIALIZABLE) Default in most systems out of the box (PostgreSQL/Oracle default to Read Committed, MySQL InnoDB to Repeatable Read) Key Differences Serializable enforces true serial equivalence; weaker levels only rule out a defined subset of anomalies. Weaker isolation relies on MVCC snapshots or narrow locks, cutting contention compared to serializable’s broader locking or SSI conflict tracking. Under Serializable, correctness bugs shift into retry loops on abort; under weaker levels, they shift into missed application-level checks. Write skew is the classic anomaly Serializable closes that even Snapshot Isolation leaves open. Choosing a level is a runtime trade-off between guaranteed correctness and throughput, not a one-time schema decision. When to Use Each Serializable ...

Overview B-Trees and LSM Trees are the two dominant on-disk index structures used by databases, and they diverge on how they handle writes. A B-Tree performs in-place updates on a balanced page structure to keep reads fast, while an LSM Tree buffers writes in memory and reconciles them later through background compaction, trading read simplicity for write throughput. Comparison Diagram B-TreeLSM Treerootnodenodeleafleafleafleafupdate overwrites herein-place updates, balanced traversalmemtable (in-memory)L0 SSTablesL1 SSTablesL2 SSTablescompaction merges levelssequential writes, background merge Comparison Table Aspect B-Tree LSM Tree Write path Traverses the tree to locate the target page and updates it in place, splitting nodes as needed Appends the entry to an in-memory memtable plus a write-ahead log; no seek to the record’s final location Read path Single root-to-leaf traversal, O(log n) page reads from one location Checks the memtable then potentially multiple SSTables across levels, often aided by bloom filters Update/Delete handling Overwrites the existing value directly at its page Writes a new version or a tombstone; the old entry is only removed later during compaction On-disk structure One mutable, balanced tree of fixed-size pages, always sorted Immutable sorted SSTable files organized into levels of increasing size Background maintenance Node splits and merges happen incrementally as part of each write Periodic compaction merges SSTables across levels and drops stale versions Write amplification Low to moderate; occasional page rewrites and splits Higher; the same record can be rewritten multiple times as it moves through levels Read amplification & space reclaim Minimal read amplification; deleted space is reclaimed immediately Higher read amplification from scanning multiple levels; space reclaimed only after compaction Range scans Efficient via sorted leaf pages linked in order Efficient within a level but requires merging sorted runs across levels Key Differences A B-Tree updates data in place, while an LSM Tree defers changes through append-only writes to a memtable LSM Trees gain higher write throughput by avoiding random disk seeks, at the cost of ongoing compaction B-Trees give more predictable read latency since each key lives in exactly one place LSM read and space overhead comes from having to consult multiple SSTable levels Deletes in an LSM Tree are recorded as tombstones rather than removed immediately When to Use Each B-Tree ...

Overview SQL (relational) databases organize data into fixed-schema tables linked by foreign keys and queried with a standardized language, prioritizing consistency and structured relationships. NoSQL (non-relational) databases store data as documents, key-value pairs, wide columns, or graphs with flexible or absent schemas, prioritizing horizontal scale and adaptability. The right choice depends on how relational your data is and whether you need strict consistency or elastic scale. Comparison Diagram SQL (Relational)NoSQL (Non-Relational)usersidname1Alice2Bobordersiduser_iditem1011Book1021PenData split across tables,joined via foreign keysuser document{"id": 1,"name": "Alice","orders": [{ "id": 101,"item": "Book" },{ "id": 102,"item": "Pen" }]}Related data embeddedin one flexible document Comparison Table Aspect SQL (Relational) NoSQL (Non-Relational) Data model Tables with fixed rows/columns, normalized via foreign keys Documents, key-value pairs, wide-column, or graph structures with per-record flexibility Schema Schema-on-write, enforced by the engine (types, constraints, CREATE TABLE) Schema-on-read; little to no enforcement, validation left to the application Query language Standardized SQL (SELECT, JOIN, WHERE) Varies by product — Mongo query API, CQL, Gremlin, or simple key lookups Consistency model Strong ACID transactions across tables by default Often eventual/tunable consistency (BASE); some now offer document-level ACID Scaling approach Vertical scaling first; horizontal sharding possible but complex Built for horizontal scaling/sharding across commodity nodes Relationships Modeled via joins and foreign keys Modeled via embedding (denormalization) or manual reference resolution Typical examples PostgreSQL, MySQL, SQL Server, Oracle MongoDB, Cassandra, DynamoDB, Redis, Neo4j Best fit workload Complex multi-entity queries, reporting, transactional integrity High-volume writes, evolving schemas, massive horizontal scale Key Differences SQL normalizes data into related tables with a fixed schema enforced at write time; NoSQL stores flexible, often denormalized records with schema left to the application. SQL guarantees ACID transactions across tables by default; most NoSQL stores trade strict consistency for availability/partition tolerance (BASE). SQL relationships require JOINs across tables; NoSQL typically embeds related data in one document to avoid joins, or resolves references manually. SQL databases scale vertically first and shard with effort; NoSQL databases are architected from the start for horizontal, distributed scaling. Changing a SQL schema requires a migration; NoSQL documents can differ in shape from record to record with no migration needed. When to Use Each SQL (Relational) ...