Column-Family Stores (Cassandra, ScyllaDB, BigTable, SSTables)

Traditional relational databases use B+ Trees, which require updating data pages in-place on disk. In-place updates force slow, random disk I/O seeks that cap single-node write throughput.

Apache Cassandra and ScyllaDB use a Log-Structured Merge (LSM) Tree architecture that converts ALL write mutations (INSERTs, UPDATEs, and DELETEs) into sequential append-only disk operations:

1. CommitLog Append (Sequential Disk I/O): The write is appended sequentially to the on-disk CommitLog file to guarantee crash durability (no random seeks).
2. Memtable Insertion (In-Memory): Simultaneously, the row is inserted into an in-memory sorted data structure called the Memtable (implemented as a concurrent SkipList in RAM).
3. Instant Acknowledgment: Once written to both CommitLog and Memtable, the database immediately returns a success response to the client (~1ms) with zero random disk I/O!
4. SSTable Flush: When the Memtable fills up (e.g., exceeds 512MB), it is flushed sequentially to disk as an immutable SSTable (Sorted String Table) file.
5. Tombstones for Deletions: Deleting a row does not erase data from disk immediately. Cassandra appends a special marker called a Tombstone with a timestamp. The tombstone suppresses older records until background compaction reclaims the disk space.