LSM trees in write-heavy systems in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

How do LSM trees improve write performance?

LSM trees are designed to optimize write-heavy workloads. What is the main mechanism they use to achieve faster writes compared to traditional B-trees?

A They write each change immediately to disk in random locations.

B They batch writes in memory and write them sequentially to disk later.

C They use multiple indexes to speed up writes.

D They store all data only in memory without writing to disk.

💡 Hint

Think about how writing in groups rather than one by one affects disk speed.

LSM trees collect writes in a memory structure and then write them to disk in large, sequential chunks. This reduces slow random disk writes and improves write speed.

📋 Factual

intermediate

What is a common drawback of LSM trees?

While LSM trees improve write speed, they have a known downside. What is it?

A They require more CPU power for writes.

B They use more memory than B-trees for the same data size.

C They cannot handle concurrent writes.

D They cause slower reads due to data being spread across multiple files.

💡 Hint

Consider how data is stored on disk in LSM trees and how that affects reading.

Because data is stored in multiple sorted files (SSTables), reads may need to check several files, causing slower read performance compared to B-trees.

🔍 Analysis

advanced

Analyzing compaction impact in LSM trees

Compaction is a process in LSM trees that merges multiple files into one. What is the main benefit of compaction?

A It deletes all old data permanently to free memory.

B It increases write speed by delaying disk writes.

C It reduces disk space usage and improves read speed by merging files.

D It duplicates data to improve fault tolerance.

💡 Hint

Think about how merging files affects the number of files to search during reads.

Compaction merges multiple sorted files into fewer larger files, reducing the number of files to check during reads and reclaiming space from deleted or overwritten data.

❓ Comparison

advanced

Comparing LSM trees and B-trees in write-heavy systems

Which statement best explains why LSM trees are preferred over B-trees for write-heavy workloads?

A LSM trees write data sequentially to disk, reducing random writes, while B-trees perform random writes for each update.

B B-trees store data only in memory, causing slower writes than LSM trees.

C LSM trees use hashing which is faster than B-tree indexing for writes.

D B-trees require compaction which slows down writes, unlike LSM trees.

💡 Hint

Focus on how disk write patterns differ between the two structures.

LSM trees batch writes and write them sequentially, which is faster on disk. B-trees update nodes in place causing many random writes, which are slower on disk.

❓ Reasoning

expert

Predicting system behavior with LSM trees under heavy writes

In a system using LSM trees, what is the expected effect on read latency immediately after a large burst of writes before compaction runs?

A Read latency increases because data is spread across many new files that need to be checked.

B Read latency decreases because recent writes are cached in memory.

C Read latency remains unchanged because compaction does not affect reads.

D Read latency decreases because the system prioritizes reads over writes.

💡 Hint

Consider how many files the system must search before compaction merges them.

After many writes, data is stored in multiple new files. Reads must check more files, increasing latency until compaction merges them.