2. Leveldb design principle -- LSM

Concept

LSM（Log-Structured Merge Tree）

principle

characteristic

• Convert random writing into sequential writing , Write fast ;
• It may take several times to read data from the disk IO;

Data operation flow

Writing data

1. Additional writing WAL journal ;
2. Update in memory MemTable structure ;

Reading data

1. Try from MemTable Query data in , Return if found ; If not found, go to the next layer to find ;
2. Try from InmemTable Find data in ;
3. Try from level0 Layer of SSTable Find data in file ;
4. Use dichotomy from levelN Layer of SSTable Query data in file ;
5. If no data is found , The returned data does not exist ;

Data merging （compaction）