LSM Tree
এলএসএম ট্রি
Log-Structured Merge Tree — write সব ধীরে append-only log-এ, read অনেক sorted run ঘেঁটে; write-heavy workload-এর engine।
also: log-structured-merge-tree
Path: memtable (sorted, memory) → full হলে SSTable flush → মাঝে মাঝে compaction merge। Write = sequential append + in-memory sort; এজন্য B+ tree-এর চেয়ে write throughput বহুগুণ।
- Read amplification: key এক run-এ নেই মানে সব run দেখতে হবে — bloom filter এখানেই
- Size-tiered: একই মাপের run জমে merge; Leveled: প্রতি level-এ overlap cap
- Tombstone ছাড়া delete অসম্ভব — পুরনো run-এ value আছেই, marker ছাড়া ঢেকে দেওয়া যায় না
RocksDB, Cassandra, LevelDB — একই DNA; trade-off ভিন্ন tuning।