Storage engines and indexes

Generated by Claude through GigAI (karthik446/gigai-learning-center 4c0cb514) on 2026-10-13.

Concept: Storage engines and indexes · also covers Relational and non-relational data stores, Data systems (schemas, indexing, partitioning), PostgreSQL · Lesson 3 of 31 in System design · version 1

Practice this

On this page

A database's behaviour under load is decided by how it arranges data on disk and how it finds rows again. This lesson contrasts the two dominant engine families, explains how indexes and multiversion concurrency work, and shows how to verify what the engine actually does with a query.

Read more

How it is done in practice

Teams pick the engine with the database: a relational B-tree store for transactional data, an LSM-based store where ingest volume dominates, and object storage for large immutable blobs. Indexes are added through reviewed migrations, built concurrently to avoid blocking writes, and justified with an EXPLAIN ANALYZE plan from production-like data. Slow query logs and statement statistics drive the tuning queue, while autovacuum behaviour, bloat and long-running transactions are watched as routine health signals.

Technologies

PostgreSQLRocksDBMySQL InnoDBApache CassandraSQLiteAmazon S3pg_stat_statements

Diagram

flowchart TD
  W[Write] --> L[Write-ahead log]
  W --> M[Memtable in memory]
  M -->|flush when full| S0[Level 0 sorted files]
  S0 -->|compaction| S1[Level 1 sorted files]
  S1 -->|compaction| S2[Deeper levels]
  R[Read] --> M
  R --> B[Bloom filters and block cache]
  B --> S0
  B --> S1
  B --> S2
flowchart TD
  W[Write] --> L[Write-ahead log]
  W --> M[Memtable in memory]
  M -->|flush when full| S0[Level 0 sorted files]
  S0 -->|compaction| S1[Level 1 sorted files]
  S1 -->|compaction| S2[Deeper levels]
  R[Read] --> M
  R --> B[Bloom filters and block cache]
  B --> S0
  B --> S1
  B --> S2

Code

sql
CREATE INDEX CONCURRENTLY orders_customer_created_idx
    ON orders (customer_id, created_at DESC);

CREATE INDEX CONCURRENTLY orders_pending_idx
    ON orders (created_at)
    WHERE status = 'pending';

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, total
FROM orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 20;

Subtopics

B-tree and LSM-tree engines

Update in place versus append and merge

A B-tree engine keeps sorted fixed-size pages and updates them in place, protected by a write-ahead log. Reads are predictable, needing a few page visits per lookup, while random writes dirty pages scattered across the disk. An LSM-tree engine such as RocksDB appends each write to a log and an in-memory memtable, flushes full memtables as immutable sorted files, and merges those files in background compaction. Writes become sequential and cheap, and compression is effective, but a read may consult several files, which bloom filters and block caches mitigate. The tradeoff is among write amplification, read amplification and space amplification, and compaction can compete with foreground traffic. Choose by workload: write-heavy ingestion favours LSM, read-heavy transactional work favours B-trees.

Index types and index design

Picking the right structure

PostgreSQL offers several index types. B-tree is the default and supports equality, range and sorted retrieval. Hash supports equality only. GIN suits values containing many elements, such as arrays, JSON documents and full-text search. GiST supports geometric and nearest-neighbour queries. BRIN stores summaries per block range and is tiny for very large tables whose physical order tracks the column, such as timestamps.

Shaping indexes to queries

In a multicolumn B-tree, column order matters: the index is most effective when leading columns have equality conditions. Partial indexes cover only rows matching a predicate, and expression indexes cover computed values. An index that contains every column a query needs enables an index-only scan that avoids the table. Every index slows writes and consumes memory and disk, so add them for measured query patterns and remove unused ones.

MVCC and its costs

Snapshots instead of read locks

Under multiversion concurrency control, each statement or transaction sees a snapshot of the data as of some point in time, so reading never blocks writing and writing never blocks reading. In PostgreSQL an update creates a new row version and leaves the old one for transactions that can still see it. The default isolation level is Read Committed, where each statement sees data committed before it began; Repeatable Read and Serializable hold one snapshot for the transaction and may fail with serialization errors that the application must retry. The cost is garbage: dead row versions accumulate until vacuum reclaims them, and a long-running transaction prevents cleanup, causing table and index bloat. Keep transactions short and monitor the oldest open one.

Reading query plans

EXPLAIN as the source of truth

EXPLAIN shows the plan tree the planner chose: scan nodes at the leaves, such as sequential, index, bitmap or index-only scans, and join or sort nodes above them. Each node carries an estimated startup cost, total cost, row count and row width. EXPLAIN ANALYZE executes the query and adds actual times, row counts and loop counts; the BUFFERS option adds pages hit and read. Read the plan from the innermost node outward and compare estimated to actual rows. A large mismatch points to stale statistics or correlated columns and usually explains a bad join choice. A sequential scan is not automatically wrong: for a query returning a large share of a table it is cheaper than an index. ANALYZE really runs the statement, so wrap data-modifying queries in a transaction and roll back.

Sources

Related lessons

Practice this
Networking for designersReplication and partitioning