30-Second Glance
- Hash:
O(1)point lookups, sequential writes, RAM-bound keyspace, no ranges. Pick for point-only KV. - B-Tree: sorted, paged,
O(log n), native ranges, bounded RAM. Default for OLTP. - LSM: MemTable + SSTables + compaction; max write throughput at the cost of read/write/space amplification. Default for write-heavy sorted logs.
- Interview move: decide from the query pattern (point vs range) + write/read ratio + RAM budget, then name the engine (Bitcask / InnoDB / RocksDB-Cassandra).
Head-to-Head Comparison
| Dimension | Hash index (Bitcask) | B+Tree (InnoDB/Postgres) | LSM-tree (RocksDB/Cassandra) |
|---|---|---|---|
| Read complexity | O(1) + 1 seek | O(log n), ~3–4 page reads | O(levels) gated by Bloom, ~1 block typical |
| Write pattern | Sequential append | Random page read-modify-write + splits | Sequential flush + background merge |
| Write throughput (SSD) | Very high (log speed) | Moderate (~1–50K updates/s/node) | Highest sustained (100K–1M+/s/node) |
| Range scans | No (full scan) | Excellent (leaf walk) | Good but merge-heavy |
| RAM requirement | All keys resident | Only hot pages (buffer pool) | Bloom filters + block cache + MemTables |
| Amplification | Compaction I/O only | Split/fragmentation overhead | WA 2–50×, RA O(files), SA 10–50% |
| Crash recovery | Replay log to rebuild map | WAL redo of page diffs | Replay MemTable WAL; SSTables immutable |
| Deletes | Tombstone + compact | Free page space in place | Tombstone until compacted past |
| Canonical systems | Riak Bitcask | MySQL InnoDB, Postgres | RocksDB, LevelDB, Cassandra, Bigtable |
loading diagram…
When to Use Each
| Workload | Pick | Reason |
|---|---|---|
| Session store, dedup table, feature flags (point GET/PUT, small keys) | Hash | Cheapest reads/writes; keyspace fits RAM; no range need |
Orders, users, inventory, bookings (mixed reads/writes + BETWEEN, ORDER BY, joins) |
B-Tree | Only structure with efficient ranges + bounded RAM + mature transactions |
| Metrics, event logs, chat inboxes, time-series ingest | LSM | Absorbs write bursts; sorted flushes compress well; compaction debt is manageable |
| Full-text / geo / vector search | Secondary specialty index (inverted, R-tree, HNSW) | B-Tree/hash/LSM all fail these query shapes — layer the right index alongside the primary |
Two traps interviewers set: (1) "100% writes, then range-scan everything" — LSM wins ingest but the scan pays merge cost, so ask about the read pattern before committing; (2) "UUID PK with 1M inserts/sec" — B-Tree splits die, LSM absorbs; either switch structures or use time-ordered keys (UUIDv7, TSIDs).
The Decision Script (Say This Aloud)
- Query shape? Point-only → hash or LSM. Any range/order/join → B-Tree (or LSM if write-dominated).
- Write/read ratio? >10:1 sustained → LSM. Balanced or read-heavy → B-Tree. Pure point KV → hash.
- RAM budget? Keyspace fits memory → hash allowed. Otherwise B-Tree/LSM.
- Ops tolerance? Zero compaction ops → B-Tree. Team can tune compaction, Bloom, tombstones → LSM.
- Name the engine + numbers: "InnoDB 16 KB pages, ~500 fan-out, 3-level tree for 100M rows" beats "use a B-Tree".
Secondary-index discipline applies to all three: every extra index taxes the write path (B-Tree: another tree update; LSM: another MemTable/SSTable set; hash: another map). Cap OLTP tables at a handful of secondary indexes.
Trade-offs
| Approach | Pros | Cons | Use when |
|---|---|---|---|
| Hash | Simplest; fastest point ops; sequential writes | RAM-bound; no ranges | Point-only KV, small keys |
| B-Tree | Best generality: ranges + bounded RAM + transactions | Write-throughput ceiling; split/fragmentation care | Default OLTP |
| LSM | Best ingest; sequential I/O; compression-friendly | Amplification trilemma; compaction ops; tombstones | Write-heavy sorted/event data |
Interview One-Liners
- Q: Hash vs B-Tree vs LSM in 30 seconds? A: Hash: O(1) points, no ranges, keys in RAM. B-Tree: O(log n) everything with ranges, bounded RAM, moderate writes. LSM: max writes via MemTable+SSTable merging, reads pay amplification.
- Q: Default choice for an orders table? A: B-Tree (InnoDB): range predicates, joins, and secondary indexes dominate; write rate rarely justifies LSM ops cost.
- Q: Default choice for a metrics pipeline at 500K points/sec? A: LSM (Cassandra/RocksDB/ClickHouse merge-tree family): sequential ingest + time-ordered compaction; B-Tree random writes would collapse.
- Q: Why not hash indexes everywhere for speed? A: No ordering means every range/analytic query becomes a full scan, and the keyspace must fit in RAM.
- Q: What single number decides B-Tree depth? A: Fan-out: 16 KB pages ÷ entry size ≈ 200–1000, so depth stays 3–4 up to ~100M–1B rows.
- Q: What single number characterizes an LSM design? A: Its amplification triple (write/read/space) set by the compaction strategy — tiered favors writes, leveled favors reads.