SSTable
Sorted String Table — an immutable file of key-value pairs stored in sorted order on disk. The fundamental storage unit in LSM-tree-based databases (Bigtable, Cassandra, RocksDB, LevelDB).
Properties: when a memtable fills up it's written out as a new SSTable — sorted and immutable (never rewritten, only replaced during compaction). The sorting enables fast binary search and efficient range scans; each SSTable usually has an internal sparse index and a Bloom filter for quick exclusion. The immutability makes writing sequential (fast) and simplifies concurrency (no read locks). Downside: the same key can exist in several SSTables over time → compaction is needed to merge and clean up. The concept comes from Google's Bigtable paper (2006). The cornerstone of modern NoSQL and embedded key-value stores. Related to memtable and compaction.