Indexes and storage engines

Without an index, finding WHERE email = 'a@b.com' means reading every row: a full table scan, O(n). An index keeps a sorted structure on that column, so the lookup becomes O(log n). Indexes are the single biggest performance lever in most databases.

B-trees

The standard index in PostgreSQL, MySQL and most relational databases.

A balanced tree of fixed-size pages (often 4–16 KB). Each page holds sorted keys and pointers to child pages.
A lookup walks from the root to a leaf: ~3–4 page reads even for billions of rows, because each page has hundreds of children.
Leaves are sorted and linked, so range queries (created_at BETWEEN …) are fast.
Updates modify pages in place, with a write-ahead log for crash safety.

LSM-trees (log-structured merge-trees)

Used by Cassandra, RocksDB, LevelDB, HBase and ScyllaDB, which are built for write-heavy workloads.

An LSM-tree: fast in-memory writes, flushed to immutable sorted files, compacted in the background

Each write is appended to a write-ahead log (for durability) and inserted into an in-memory sorted table (the memtable).
When the memtable fills, it’s flushed to disk as an immutable sorted file, an SSTable.
Background compaction merges SSTables, dropping overwritten and deleted values.
Reads check the memtable, then SSTables from newest to oldest. Bloom filters skip files that can’t contain the key.

B-tree vs LSM-tree

B-tree

Fast, predictable reads and range scans
Each key lives in one place: simple transactions and locking
Random writes are slower (in-place page updates)
The default for read-heavy, transactional workloads

LSM-tree

Very high write throughput (sequential appends)
Good compression; small storage footprint
Reads may check several files (Bloom filters help)
Compaction uses background I/O and can cause latency spikes

Designing indexes

Index the columns you filter, join and sort by. Write the queries first.
Composite indexes follow the leftmost prefix rule: an index on (user_id, created_at) serves WHERE user_id = ? ORDER BY created_at, but not WHERE created_at = ? alone.
Covering indexes include every column a query needs, so the database never touches the table.
Selectivity matters. An index on a boolean column rarely helps.
Every index costs writes. Each INSERT updates every index on the table, so don’t index “just in case”.
Secondary indexes in sharded systems are expensive: either every shard keeps a local index (and queries fan out), or there’s a global index (and writes cross shards).