LSM Tree / Log-Structured Merge-tree?

Data structure optimized for write-heavy workloads.
LSM Tree is not a traditional BTree node-and-pointer parent-child tree structure
LSM-Tree = RAM(Memtables) + Hard Disk(SSTables (Sorted String Table))

Write Data in LSM Tree?

1st data is written to RAM(ie memtables). When (size > 64KB). data is moved to Dis(SSTables)k
SSTables are immutable sorted files stored on Disk 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

{key,value} need to be stored.
Writing to DB: 1st data goes to RAM(Memtables), once size of Memtables > 64KB data is moved to disk(SSTables).
Reading from DB: 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 noSQL Scale Horizontally wrt SQL

1. SQL(ACID), noSQL(BASE)

SQL: ACID(Atomicity, Consistency, Isolation, Durability)
  Consistency SQL DB wants transaction to be consistent. if tables are stored on 3 seperate machines. SQL want data should be committed and ACKed. 2 Phase Commit