LSM Trees

B-Trees vs LSM Trees

B-trees are read-optimized: lookups are fast (3-4 disk reads), but every write requires updating pages in place — random disk I/O.

LSM trees flip this tradeoff: all writes go to an in-memory buffer first, then flush to disk as sorted files. Writes are sequential (fast), but reads may need to check multiple files.

The LSM Tree Architecture

class LSMTree {
	private memtable: SortedMap<string, Row>; // in-memory, sorted
	private immutableMemtables: SortedMap<string, Row>[] = []; // being flushed
	private levels: SSTable[][] = [[], [], [], []]; // L0, L1, L2, L3

	// WRITE: always goes to memtable (RAM) — blazing fast
	async put(key: string, value: Row): Promise<void> {
		// 1. Write to WAL (for durability)
		await this.wal.append(key, value);

		// 2. Insert into memtable (in-memory sorted structure)
		this.memtable.set(key, value);

		// 3. If memtable is full, flush to disk
		if (this.memtable.size >= this.maxMemtableSize) {
			this.immutableMemtables.push(this.memtable);
			this.memtable = new SortedMap();
			await this.flush();
		}
	}

	// READ: check memtable first, then each level
	async get(key: string): Promise<Row | null> {
		// 1. Check active memtable
		if (this.memtable.has(key)) return this.memtable.get(key)!;

		// 2. Check immutable memtables (being flushed)
		for (const mem of this.immutableMemtables) {
			if (mem.has(key)) return mem.get(key)!;
		}

		// 3. Check SSTable levels (L0 first, then L1, L2, ...)
		for (const level of this.levels) {
			for (const sst of level) {
				const result = await sst.get(key);
				if (result !== null) return result;
			}
		}

		return null;
	}
}

SSTables (Sorted String Tables)

When the memtable flushes to disk, it becomes an SSTable — an immutable, sorted file:

interface SSTable {
  // Metadata
  minKey: string;
  maxKey: string;
  bloomFilter: BloomFilter; // quick "definitely not here" check
  index: Map<string, number>; // sparse index: key → file offset

  // Data
  dataBlocks: DataBlock[]; // sorted key-value pairs

  // Lookup
  async get(key: string): Promise<Row | null> {
    // 1. Check bloom filter — fast rejection
    if (!this.bloomFilter.mightContain(key)) return null;

    // 2. Binary search the sparse index
    const blockOffset = this.findBlock(key);

    // 3. Read and search the data block
    const block = await this.readBlock(blockOffset);
    return block.find(key);
  }
}

Compaction

Over time, LSM trees accumulate many SSTable files. Compaction merges them to reduce read amplification and reclaim space:

// Level-based compaction (used by LevelDB, RocksDB)
async function compact(level: number): Promise<void> {
	// Pick overlapping SSTables from this level and the next
	const source = selectSSTables(level);
	const target = findOverlapping(level + 1, source);

	// Merge-sort all entries
	const merged = mergeSorted([...source, ...target]);

	// Write new SSTables to level + 1
	const newSSTables = await writeNewSSTables(merged, level + 1);

	// Remove old SSTables
	await deleteOldSSTables([...source, ...target]);
}

// Size-tiered compaction (used by Cassandra)
// Merge SSTables of similar size into larger ones
// Simpler but uses more space during compaction

Tradeoffs: Read/Write/Space Amplification

	B-Tree	LSM Tree
Write amplification	~10x (page splits, in-place updates)	~10-30x (compaction rewrites)
Read amplification	1x (single B-tree lookup)	~1-5x (check multiple levels)
Space amplification	~1.5x (page fill factor)	~1.1-2x (temporary duplicates)
Write throughput	Lower (random I/O)	Higher (sequential I/O)
Read latency	Lower (predictable)	Higher (varies)

Key Takeaways

1. LSM trees buffer writes in memory and flush sorted files to disk — all sequential I/O
2. Reads check multiple levels — bloom filters and sparse indexes minimize disk reads
3. Compaction merges files to keep read performance manageable and reclaim space
4. B-trees win on reads, LSM trees win on writes — pick based on your workload