LSM Tree (Log structure merge tree)

This is used on database implementation other than B-Tree. Some keys may appear in multiply segment file, but we should use the newer version. Append data only, new value will be write into newer segment file.

Construction:

• Keep in memory AVL tree to store key-value
• Also keep write ahead log for recovery if crash
• Write to file when the memory usage exceed threshold
• The file format is sorted by its key (Sorted segment table file)
• Merge sorted segment table files into single file in the background

Pros & cons:

• Write performance and data storage (compression) are better than B-Tree
• Read performance is worse than B-Tree because it may need to check every segment file
• It may stall when doing background merge