LSM Tree / Log-Structured Merge-tree?

Data structure optimized for write-heavy workloads.
LSM Tree is not a traditional node-and-pointer parent-child tree structure
LSM-Tree = (Memtables(in memory) + SSTables(on disk))

Write Data to LSM Tree?

1. MemTables(In memory/RAM)
  Initially data is written to it.   When (size > 64KB). data is moved to Disk
2. SSTables(Sorted String Table) on Disk
  SSTables are immutable sorted files which store data in sequential manner.

Read Data

Checks Bloom Filter -> Index Summary -> SSTable Data.

Update Data

LSM tree is strictly immutable
LSM-trees handle updates using timestamp-based reconciliation, ie add new value with updated timestamp
Suppose we updated a key, now 2 keys are present in SSTable with different timestamps
Merge and Purge(Compaction): Periodically, a background process merges overlapping SSTables into single new files

Example

Consider a example where {key,value} need to be stored.
Writing to DB: 1st data goes to RAM(Memtables), once size of Memtables(exceeds 64KB) data is moved to disk(SSTables).
Reading from DB: To Read ID: 2: The system checks the MemTable first. If not found, it checks the SSTables from newest to oldest.

Incoming data       Stored in RAM(Memtables)
        {1, A}        
        {3, C}  ---> |{1,A}, {3,C}|
                    (limit reached 64KB)
                            |
                            |-------write------> Disk(SSTable-1)
                                                [ {1,A}, {3,C} ]

        {2,B} ----> |{2,B}|------write---------> [ {1,A}, {2,B}, {3,C} ]
      

Why LSM Trees Scale Horizontally Better Than B-Trees

Core difference between LSM-based storage engines(e.g., Cassandra, RocksDB, ScyllaDB) and traditional B-Tree storage engines (e.g., PostgreSQL, InnoDB) comes down to append-only storage vs. in-place updates.

How postgres stores data?
  In-Place Updates: Overwrites fixed-size disk pages directly.

How LSM Trees store data?
  Append-Only / Immutable: Writes sequentially to RAM, then flushes new SSTables to disk.
  Whenever new data need to be added a new Shard is added and data present on old shard is not touched.
  Shards can paritioned using user_id