Storage & Indexes
Row-store vs column-store, B-trees, hash and bitmap indexes, LSM-trees, WAL, MVCC.
Storage and indexing is where database design meets disk physics. Every choice — row-store vs column-store, B-tree vs LSM, lock-based vs MVCC — is a trade-off between read latency, write throughput, space efficiency, and durability cost.
For interviews, know the B-tree (it's the default in every relational DBMS for a reason) and the LSM-tree (because most NoSQL stores landed on it). Know WAL because crash recovery is non-negotiable. Know MVCC because it's how Postgres and many modern systems get snapshot isolation without lock contention on every read.
Key concepts
- B-trees optimise for in-place updates and range scans — the OLTP default
- LSM-trees optimise for sequential writes and accept compaction cost
- Column-stores are the right answer for OLAP — the data layout matches the access pattern
- WAL is what makes durability and crash recovery work together
- MVCC gives readers a consistent snapshot without blocking writers
Reference template
// Choosing an index
1. What's the predicate? (equality? range? prefix? full-text?)
2. What's the cardinality? (high → B-tree; low → bitmap)
3. Is it covering? (does it serve the query without a heap fetch?)
4. What's the write amplification? (every index slows writes)
5. Does it help joins? (foreign-key columns are the usual win)Adapt to your problem; the structure is the load-bearing part.
Common pitfalls
- Adding an index for every WHERE clause — write amplification adds up fast
- Forgetting that an index with leading wildcard
LIKE '%x'won't be used - Indexing low-cardinality columns with B-trees — bitmap is much better for OLAP
- Treating MVCC as free — vacuum (Postgres) or undo-log scans (InnoDB) are real costs
Related topics
Items (6)
- Row-Store vs Column-Store
Why OLTP is row-oriented and OLAP is column-oriented; the storage layout that explains the performance gap.
Building Block Intermediate - B-Tree Indexes
The classic disk-friendly tree, fanout, leaf-page linking, why every relational DBMS defaults to B-tree.
Building Block Intermediate - Hash and Bitmap Indexes
Hash indexes for equality lookups, bitmap indexes for low-cardinality columns, the trade-offs vs B-tree.
Building Block Intermediate - LSM-Tree Storage
Memtables, SSTables, compaction. The structure behind LevelDB, RocksDB, Cassandra, ScyllaDB, and DynamoDB's storage.
Building Block Advanced - Write-Ahead Logging and Recovery
Why every durable database writes a WAL, ARIES, redo/undo, checkpointing, crash recovery.
Building Block Intermediate - MVCC — Multi-Version Concurrency Control
Snapshot isolation, vacuum, the trade-off vs lock-based concurrency. Why Postgres, MySQL InnoDB, and Spanner all use MVCC.
Building Block Advanced