The NoSQL Landscape

SQL's rigidity is a feature, until it becomes a bottleneck. A rigid schema means every write has to fit the same shape, and a single table's guarantees get harder to maintain the moment you need to split that table across multiple machines (a problem the next module tackles directly). NoSQL databases relax exactly this rigidity in exchange for horizontal scalability.

• -Key-Value: a giant hash map (Redis, DynamoDB). Fastest possible lookups by key, no querying by value.
• -Document: JSON-like nested records (MongoDB, Firestore). Flexible schema, good for content that varies shape between records.
• -Wide-Column: rows with dynamic, sparse columns grouped into families (Cassandra, HBase). Built for massive write throughput.
• -Graph: nodes and edges as first-class citizens (Neo4j, Neptune). Built for traversal queries like "friends of friends" that would need many expensive joins in SQL.

The B-tree index from the last chapter is read-optimized: it keeps data sorted on disk at all times, so every write has to find the right spot and update it in place, which means random disk I/O. Wide-column stores like Cassandra and HBase, along with embedded engines like RocksDB and LevelDB, use a different structure entirely to get their write throughput: the Log-Structured Merge-Tree, or LSM-tree.

An LSM-tree never updates data in place. Every write is first appended to an in-memory, sorted structure called a memtable, an operation that costs no disk I/O at all. Once the memtable fills up, it is flushed to disk as a new, immutable, sorted file called an SSTable (Sorted String Table), and a fresh, empty memtable takes over for new writes. Because a flush writes one large sequential block instead of many scattered updates, it is dramatically cheaper than the random writes a B-tree needs to keep itself sorted in place.

The cost shows up on reads instead. A single key might exist in the memtable, or in any of several SSTables on disk (whichever one was current when it was last written), so a lookup may have to check multiple places, newest first, until it finds the key. A background compaction process periodically merges older SSTables together, both to reclaim space taken by overwritten or deleted keys and to bound how many separate files a read ever has to check.