Database & Storage Deep Dive

B-Tree vs LSM-Tree, replication strategies, consistency models, CAP theorem practical guide

Technical Reference & Key Concepts

Indexing Strategies

  • B-Tree: Default in most databases. Good for equality + range queries. Tradeoff: Write amplification.
  • LSM-Tree: Used in Cassandra, RocksDB. Sequential writes, great for write-heavy workloads. Tradeoff: Compaction overhead.
  • Hash Index: O(1) point lookups. No range queries. Good for key-value workloads.
  • Inverted Index: Maps terms->documents. For full-text search (Elasticsearch).

Replication

  • Single-leader: One primary writes, replicas read. Simple but failover is manual.
  • Multi-leader: Multiple primaries. Good for multi-datacenter. Tradeoff: Conflict resolution.
  • Leaderless: Quorum-based (Dynamo, Cassandra). High availability. Tradeoff: Stale reads.

Consistency Models

  • Linearizability: Strongest. Reads return most recent write. Hard to achieve in distributed systems.
  • Serializability: Transactions appear to run sequentially. Not the same as linearizability.
  • Snapshot Isolation: Each transaction sees a consistent snapshot. Prevents dirty reads.