Skip to main content
Engineering Career Growth

Reference: Database Indexing

A reference on B-Tree vs LSM-Tree storage engines, composite index column ordering, covering indexes, and where secondary indexes create hot shards.

What it is

An index is a secondary data structure that lets a database find rows without scanning the whole table. Two decisions define its behavior: the storage engine the index is built on (B-Tree vs LSM-Tree), which sets the read/write amplification trade-off, and the index shape (which columns, in which order, and whether the index alone can answer the query).

When you care

Indexing shows up as a follow-up in almost every storage question. You name a database, and the interviewer asks “how would you index this?” or “why is this query slow?” The trap is treating an index as a free “make it fast” button — strong candidates name the write cost, the column order, and what the index can’t accelerate. In a partitioned system, the index choice also decides whether a query hits one shard or fans out to all of them.

Storage engine: B-Tree vs LSM-Tree

The engine underneath the index sets the fundamental trade-off between read and write cost. This is the read/write amplification axis, and it’s the one interviewers probe.

AxisB-TreeLSM-Tree
Write pathIn-place update; may split/merge pagesAppend to in-memory table, flush to sorted files
Write amplificationLower per write, but random I/OHigher (compaction rewrites data), but sequential I/O
Read amplificationLow — one tree traversalHigher — may check several sorted files + bloom filters
SpaceFragmentation from partial pagesBetter compression; compaction reclaims space
Range scansExcellent — leaves are linked and sortedGood, but merges across files
Used byPostgreSQL, MySQL/InnoDB, most RDBMSCassandra, RocksDB, LevelDB, ScyllaDB

B-Tree keeps keys sorted in a balanced tree and updates pages in place — reads are a single predictable traversal, but random writes scatter across disk and page splits add overhead. Reach for it when reads dominate or latency must be predictable (OLTP, read-heavy services).

LSM-Tree buffers writes in a memtable, then flushes them as immutable sorted files that a background compaction process merges. Writes are fast sequential appends; the cost is read amplification — a read may probe multiple files — mitigated by bloom filters that skip files that can’t contain the key. Reach for it when writes dominate (time-series, event logs, metrics, high-ingest KV).

Index shape: composite index column ordering

A composite index spans multiple columns, and the column order determines which queries it can serve. The index is sorted by the first column, then the second within each first-column value, and so on — like a phone book sorted by (last name, first name).

Query predicateIndex (a, b) helps?Why
a = ? AND b = ?FullyBoth columns used, in order
a = ? AND b > ?FullyEquality on a, range on b — ideal
a = ? (b unconstrained)Yes (prefix)Leftmost prefix is usable
b = ? (a unconstrained)NoCan’t skip the leading column
a > ? AND b = ?PartiallyRange on a stops b from being used efficiently

Two rules fall out of this:

  • Equality columns before range columns. Once a query hits a range (>, <, BETWEEN) or a sort, the columns after it can no longer narrow the scan — the range has already spread the read across many leaf entries. Put equality predicates first, the range/sort column last.
  • The leftmost-prefix constraint. An index on (a, b, c) serves queries filtering on a, (a, b), or (a, b, c) — but not b alone. To query b independently, you need a separate index.

Covering indexes and index-only scans

A covering index includes every column a query needs — both the filtered and the selected ones — so the database answers from the index alone, never touching the table rows. This index-only scan removes the random I/O of fetching full rows. The trade-off: a wider index costs more to store and update on every write, so add covering columns only for a hot query that measurably benefits.

Secondary indexes and hot shards

In a partitioned system, a secondary index on a column other than the partition key forces a choice, and each option has a distinct failure mode:

ApproachMechanismHot-shard risk
Local (per-partition) indexEach shard indexes its own rowsRead fans out to all shards (scatter-gather)
Global (partitioned) indexIndex itself partitioned by the indexed valueA low-cardinality or skewed value lands all its entries on one shard

The hot-shard problem lives in the global index: if you build a global secondary index on a skewed column — say status, where 90% of rows are active — every write to an active row and every read of active rows hits the single shard that owns status = active. That shard becomes the bottleneck while the rest sit idle. Mitigations are the usual hot-key ones: index a higher-cardinality composite value, or accept the scatter-gather of a local index instead.

When to pick what

  • Read-heavy / latency-sensitive OLTP: B-Tree engine; composite indexes with equality-before-range ordering.
  • Write-heavy ingest (time-series, events, metrics): LSM-Tree engine; keep index count low — every secondary index multiplies write amplification.
  • A hot query fetching a few columns repeatedly: add a covering index for an index-only scan; measure the write-cost trade first.
  • Filtering on a non-partition-key column at scale: local index if reads tolerate scatter-gather; global index only if the indexed value is high-cardinality and evenly distributed.
  • Query filters on b but your index leads with a: it won’t help — add the index the query’s predicate actually needs.

An index trades write cost and storage for read speed on specific access patterns. Name the engine’s amplification trade-off, order composite columns equality-first, and — in a partitioned system — say which shard the index lands on. Don’t just say “we’ll add an index.”

Tags #system-design#concepts#indexing#reference