Sorted String Table

A sorted string table stores key-value records in sorted order, commonly as an immutable file with an index. LSM-based engines use these files to make persisted batches searchable without rewriting each record in place.

Newer files can contain replacements or deletion markers for keys in older files. Compaction later combines the overlapping information. The exact file format and its metadata depend on the storage engine.