Indexing & Storage Engines

Intermediate · 17 min read · High-Level Design, Storing Data

B-Trees vs LSM-Trees, secondary indexes, and why writes and reads pull in opposite directions.

Without an index, finding a row means scanning the whole table — fine for 1,000 rows, catastrophic for a billion. An index is an additional data structure that lets the database find rows by some column(s) without scanning everything, the same way a book's index lets you jump to a page.

Indexes are central to performance, and understanding how they're built — B-Trees vs LSM-Trees — explains why some databases are better at reads and others at writes.

The fundamental trade-off

Every index speeds up reads on the indexed columns and slows down writes, because each insert, update or delete must also update every index on that table. Indexes also consume disk and memory.

B-Tree indexes

The B-Tree (in practice, B+Tree) is the default index structure in nearly every relational database (PostgreSQL, MySQL InnoDB, SQL Server, Oracle).

LSM-Tree storage

The Log-Structured Merge-Tree is designed for write-heavy workloads. It powers Cassandra, ScyllaDB, RocksDB, LevelDB, HBase and Bigtable.

B-Tree vs LSM-Tree

Types of indexes

A consequence: in InnoDB, a secondary index lookup costs two B-Tree traversals (secondary index → primary key → row). Choosing a compact, monotonically increasing primary key keeps this fast and avoids page splits on insert — which is one reason random UUIDv4 primary keys can hurt insert performance, and why…

Indexes in distributed databases

When data is sharded, secondary indexes get harder:

Common mistakes

Interview questions

  • Why are LSM-Trees faster for writes than B-Trees?
  • A query on a 500M-row table is slow even though there's an index on the filtered column. What could be wrong?
  • What is a Bloom filter and why do LSM-based databases use it?
  • Why might random UUIDs as primary keys hurt performance?

Practice

Write your answer before opening the suggested one. Anything you mark "Partly" or "Missed it" comes back in your review deck.

Further reading

Key takeaways

  • Indexes trade write speed and storage for read speed — index for actual query patterns.
  • B-Trees update in place: great for reads and ranges, the default in relational databases.
  • LSM-Trees append and compact: great for write-heavy workloads, at the cost of read and compaction overhead.
  • Composite index column order matters: equality columns first, range/sort column last.
  • In sharded systems, local indexes need scatter-gather reads; global indexes need cross-shard (often async) writes.

Previous: Choosing a Database: SQL vs NoSQL · Next: Transactions, Isolation & MVCC