The idea of LSM Tree Index is to have 2 parts of the database: The memtable and the sorted data file.

The memtable could be any self balanced tree like red-black tree.

When write come, the table in memory will be updated accordingly.

When the table grow big enough (few MB), data will be write to a log structured data file. See §202109081437 Sorted String Table.

When a read come, first lookup in the mem table, then in the most recent segment, then in the next-recent on-disk segments.

In case a key does not exist in the tree, lookup could be slow, it can be optimized by using Bloom Filters.

Periodically, we should perform §202109072236 Index Compaction in the background to reduce duplication.

In case of crash, most recent writes that not yet written to disk could be lost. We can keep a separated unsaved log on disk, use it to recover if needed, and remove that lag when the segment is saved to disk.

Because data is stored in the sorted order, range queries can be done easily. On disk data is sequential written so write throughput will be high.


Source: Designing Data-Intensive Applications, Ch. 3
#database