Indexes

The problem it solves

A users table holds 1 billion rows of about 200 bytes each: 200 GB. The login path runs SELECT * FROM users WHERE email = ? 2,000 times a second. Without an index, the database has one way to answer: read every row and compare.

Where the 200 GB lives	Sequential read speed	One full scan
Local NVMe SSD	about 2 to 3 GB/s	70 to 100 s
Cloud block volume (gp3 baseline)	125 MB/s	about 27 min
Already in RAM, one core	a few GB/s	about a minute

One login takes between a minute and half an hour, and the workload asks for 2,000 a second. No hardware closes that gap.

An index is a second copy of some of the data. It’s sorted by the column you search on, with a pointer back to the row. Because it is sorted, the database can find one email in about four page reads, instead of 12 million. The upper levels of the index stay in memory. So one lookup is about one random disk read: 0.1 ms on NVMe.

That second copy is not free, and the costs are the rest of this page:

• Every write maintains it. An insert into a table with five indexes updates six structures.
• It takes space. Often 20 to 50% of the table per index, and more for wide keys.
• It only helps queries shaped like it. An index on (country, city) does nothing for a query on city alone.

The question is which structure, on which columns, and how much write cost the read speed is worth.

How it works

Step 1: Sort it, then binary search

The simplest index is the column’s values in sorted order, each with the row’s address. Binary search finds any key in log₂(1 billion) = 30 probes, 30 random reads of 0.1 ms: 3 ms. Two problems remain: 30 reads is still a lot, and inserting into the middle of a sorted file means shifting everything after it.

A hash index fixes the first problem, for exact lookups. Hash the key, jump to the bucket, and do one read. (Bitcask keeps such a map in RAM, pointing into an append-only log.) But hashing scatters neighbors. So it cannot answer created_at > ?, ORDER BY or LIKE 'abc%'. Ranges need order, and order on disk needs a tree.

Step 2: The B-tree, a sorted file in pages

A B-tree cuts the sorted keys into fixed-size pages: 8 KB in Postgres and SQL Server, and 16 KB in MySQL’s InnoDB. It builds a small index of pages above them, and an index of that index above that. This repeats until one page remains, called the root. Each page holds hundreds of keys. So each level divides the search space by hundreds, instead of by two.

A B+ tree: separators above, sorted keys in the leaves

Scroll or pinch to zoom, drag to pan

• Color key
• Root and internal pages
• Leaf pages

Databases call it a B-tree, and almost all build a B+ tree. Internal pages hold only separators and child pointers. Entries live in the leaves, and the leaves are linked. So a range scan descends once, and then walks sideways.

Fanout decides height. An internal entry is the separator key plus a 6 to 8 byte child pointer plus a few bytes of overhead. For a bigint key that is about 16 bytes, so a 16 KB page has a fanout of about 1,000. For the email index above, with 30-byte keys:

Level	Pages	Size	Where it lives
Root	1	16 KB	RAM, always
Internal	about 21	336 KB	RAM, always
Internal	about 8,300	133 MB	RAM, almost always
Leaves	about 3.3 million (300 entries each)	53 GB	Disk, hot ones cached

Four levels hold a billion keys. The 133 MB of internal pages stay in the buffer pool. So a point lookup costs one random read: the leaf. A range scan adds one read per 300 matching entries. Height ≈ log_fanout(rows), which is 3 to 4 for nearly any table.

Step 3: Writing to a B-tree

An insert descends to the right leaf and changes it in place:

1. Append the change to the write-ahead log (WAL) and fsync it. This is the durable part.
2. Read the leaf into the buffer pool if it is not there: a random read on the write path.
3. Insert the key in sorted position inside the page, and mark the page dirty.
4. Later, a checkpoint writes the whole page back to disk.

A full leaf splits: half its entries move to a new page and a separator goes up to the parent, which may split in turn. A split of the root creates a new root, the only way a B-tree grows taller, so every leaf stays at the same depth.

Under random inserts, splits leave the average leaf about 69% full (ln 2). So a B-tree takes about 1.4 times the space of its data. Sequential keys behave better. When a key lands past the end of the rightmost leaf, InnoDB and Postgres split so the old page stays nearly full. So sequential keys pack pages to 90% or more. That is why time-ordered IDs beat random UUIDs as primary keys. (The unique ID generator works through it.)

The price of updating in place is write amplification: bytes written to disk per byte changed. A 100-byte change dirties a 16 KB page. If the page is flushed before another change lands on it, that is 160 to 1, plus the WAL. Postgres also logs a full page image on the first change after each checkpoint. And InnoDB writes every page twice (the doublewrite buffer). Both do this to survive torn pages. Hot pages absorb many changes per flush. But random writes to a large B-tree stay expensive.

Step 4: The LSM tree, never update in place

If random writes are the problem, stop doing them. A log-structured merge tree (LSM tree) turns every write into an append and a memory insert, and does its sorting later in big sequential passes.

LSM write path (top) and read path (bottom)

Scroll or pinch to zoom, drag to pan

• Color key
• On disk
• In memory

• WAL and memtable. A write is appended to the log, and inserted into the memtable. That’s a sorted structure in RAM: a 64 MB skip list in RocksDB. Nothing on disk is read or modified.
• Flush. A full memtable is written as an SSTable (sorted string table). It’s an immutable file of sorted 4 KB blocks, with a sparse index of each block’s first key, and a Bloom filter. This is one sequential write.
• Read path. Memtable first, then SSTables newest to oldest, stopping at the first hit, the newest version. A delete writes a tombstone that hides older versions.
• Compaction. Background merges keep the newest version of each key and drop what tombstones cover. Without it, a read would check every file ever written.

Two pieces of RAM metadata keep reads cheap:

• Fence pointers: each file’s min and max key, and the first key of each block. They rule out files whose range cannot hold the key.
• A Bloom filter per SSTable. From a bit array, it answers “definitely not here” or “maybe here”. At 10 bits a key, it says “maybe” for about 1% of absent keys. It never says “no” for a present one. So a point read touches the disk about once, for the file that has the key.

A billion keys at 10 bits each is 1.25 GB of filters. They must fit in memory for this to work.

Step 5: Compaction is where the cost went

LSM trees moved the work from the write into compaction, and the compaction strategy decides who pays.

Leveled vs size-tiered compaction

Scroll or pinch to zoom, drag to pan

• Color key
• Service

Leveled compaction keeps each level below L0 as one sorted run of 64 MB files. Each level is 10 times larger than the one above. An overflowing level merges one file into the roughly 10 it overlaps below. So a key can be rewritten up to about 10 times per level. Total write amplification of 10 to 30 is common. In return, a point read checks at most one file per level. And with 90% of the data in the last level, stale versions cost only about 10% extra space.

Size-tiered compaction waits for several runs of similar size (4 in Cassandra). Then it merges them into one run in the next tier. Each key is rewritten once per tier, so write amplification is low. But a key can be in any run, so reads check more files. Old versions linger. And merging the largest tier needs free space equal to its size. That’s why such clusters stay below 50% disk.

Insert keys into both engines, and watch where the writes go. Switch the compaction strategy to replay the same writes. Look keys up, to see which files a read touches. And use Update to create stale versions.

Key, 1 to 9999InsertLook up

+10 random+10 sequentialUpdate 5Reset

B-tree pages of 4 keys, updated in place

Write amp

0

nothing written

Last lookup

-

disk reads

Space amp

-

slots per live key

Height

1

0 pages

LSM tree memtable of 4 keys, immutable files

LeveledSize-tiered

Write amp

0

nothing written

Last lookup

-

disk reads

Space amp

-

entries per live key

Files

0

SSTables on disk

written by the last actionread from diskskipped by key range or Bloom filter

Insert some keys. Try +10 random a few times, then a lookup, then Update 5.

Random inserts leave B-tree leaves about 70% full, sequential ones fill them. The B-tree’s write amplification is the highest even with 4-key pages, and real pages hold hundreds. Leveled compaction rewrites more than size-tiered, and in exchange a lookup touches at most one file per level.

The read path with fence pointers and Bloom filters, and what compaction buys:

JLsmReadDemo.javaPylsm_tree.pyC#LsmTree.csGolsm_tree.goTSlsm-tree.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class LsmReadDemo {
    // FNV-1a, 32 bits. Two seeds give the two base hashes a Bloom filter needs.
    static long fnv1a(String s, int seed) {
        int h = (int) 2166136261L ^ seed;
        for (byte b : s.getBytes(java.nio.charset.StandardCharsets.UTF_8)) {
            h ^= b & 0xff;
            h *= 16777619;
        }
        return h & 0xFFFFFFFFL;
    }

    // About 10 bits a key and 7 hashes give roughly 1% false positives and never a false
    // negative, so a "no" lets a read skip the file without touching the disk.
    static class BloomFilter {
        private final boolean[] bits;
        private final int k = 7;

        BloomFilter(int n) { bits = new boolean[Math.max(64, n * 10)]; }

        private long[] positions(String key) {
            long a = fnv1a(key, 0), b = fnv1a(key, 0x5BD1E995) | 1;
            long[] p = new long[k];
            for (int i = 0; i < k; i++) p[i] = ((a + i * b) & 0xFFFFFFFFL) % bits.length;
            return p;
        }

        void add(String key) { for (long p : positions(key)) bits[(int) p] = true; }

        boolean mightContain(String key) {
            for (long p : positions(key)) if (!bits[(int) p]) return false;
            return true;
        }
    }

    // An immutable sorted file. Its min and max key (fence pointers) and its Bloom filter are
    // kept in RAM; reading the keys themselves costs a disk read.
    static class SSTable {
        final String[] keys;
        final String[] values;
        final BloomFilter bloom;

        SSTable(TreeMap<String, String> sorted) {
            keys = sorted.keySet().toArray(new String[0]);
            values = sorted.values().toArray(new String[0]);
            bloom = new BloomFilter(keys.length);
            for (String k : keys) bloom.add(k);
        }

        String get(String key) {
            int i = Arrays.binarySearch(keys, key);
            return i >= 0 ? values[i] : null;
        }
    }

    static class LsmTree {
        private TreeMap<String, String> memtable = new TreeMap<>(); // a skip list in RocksDB
        final List<SSTable> tables = new ArrayList<>(); // newest first
        private final int limit;
        private final boolean useBloom;
        int diskReads = 0;

        LsmTree(int memtableLimit, boolean useBloom) {
            this.limit = memtableLimit;
            this.useBloom = useBloom;
        }

        // A write is a log append (not shown) plus a memory insert: no disk seek at all.
        void put(String key, String value) {
            memtable.put(key, value);
            if (memtable.size() >= limit) {
                tables.add(0, new SSTable(memtable)); // one sequential write
                memtable = new TreeMap<>();
            }
        }

        String get(String key) {
            if (memtable.containsKey(key)) return memtable.get(key);
            for (SSTable t : tables) { // newest first, so the first hit is the latest version
                if (key.compareTo(t.keys[0]) < 0 || key.compareTo(t.keys[t.keys.length - 1]) > 0) {
                    continue; // fence pointers: outside this file's range
                }
                if (useBloom && !t.bloom.mightContain(key)) continue; // definitely not in this file
                diskReads++;
                String v = t.get(key);
                if (v != null) return v;
            }
            return null;
        }

        // Merge every file into one, keeping the newest version of each key. Reads then touch
        // one file, at the price of rewriting all the data.
        void compact() {
            TreeMap<String, String> merged = new TreeMap<>();
            for (int i = tables.size() - 1; i >= 0; i--) { // oldest first: newer values overwrite
                SSTable t = tables.get(i);
                for (int j = 0; j < t.keys.length; j++) merged.put(t.keys[j], t.values[j]);
            }
            tables.clear();
            tables.add(new SSTable(merged));
        }
    }

    static LsmTree build(boolean useBloom) {
        LsmTree lsm = new LsmTree(100, useBloom);
        for (int i = 0; i < 1000; i++) {
            int n = (i * 7919) % 1000; // shuffled order, so every file spans the whole key range
            lsm.put(String.format("user:%04d", n), "v" + i);
        }
        return lsm;
    }

    static int reads(LsmTree lsm, boolean present) {
        lsm.diskReads = 0;
        for (int n = 0; n < 1000; n++) {
            lsm.get(String.format("user:%04d", n) + (present ? "" : "x")); // "x": in range, absent
        }
        return lsm.diskReads;
    }

    public static void main(String[] args) {
        LsmTree withBloom = build(true), noBloom = build(false);
        System.out.printf("%d SSTables after 1,000 writes%n", withBloom.tables.size());
        System.out.printf("present key, no Bloom filters: %5d disk reads per 1,000 gets%n", reads(noBloom, true));
        System.out.printf("absent key,  no Bloom filters: %5d disk reads per 1,000 gets%n", reads(noBloom, false));
        System.out.printf("present key, Bloom filters:    %5d disk reads per 1,000 gets%n", reads(withBloom, true));
        System.out.printf("absent key,  Bloom filters:    %5d disk reads per 1,000 gets%n", reads(withBloom, false));
        withBloom.compact();
        System.out.printf("after compaction to 1 file:    %5d disk reads per 1,000 gets%n", reads(withBloom, true));
    }
}

Without Bloom filters, a present key costs 5.4 reads across 10 overlapping files and an absent key almost 10. With them, about one read and almost none. Compacting to one file makes the read exact, at the price of rewriting every key.

Step 6: The three amplifications

Every storage engine trades three costs, and no design minimizes all three at once (the RUM conjecture: read, update, memory).

Engine	Write amplification	Read amplification (point get)	Space amplification
B-tree	High for small random writes: a page per change, plus WAL and page images	About 1 disk read (internal pages cached)	About 1.3 to 1.5 (pages 70% full, fragmentation)
LSM, leveled	10 to 30: up to about 10 rewrites per level	About 1 read with Bloom filters; ranges merge every level	About 1.1
LSM, size-tiered	Low, about the number of tiers (4 to 10)	Several files per read; ranges merge many runs	Up to 2, more during a large merge

LSM trees lose on range scans. Bloom filters cannot help a range. So a scan merges iterators over the memtable, every L0 file and every level. A B-tree just walks consecutive leaves.

B-trees lose on random writes larger than RAM. Each insert costs a random read, and later a page write. An LSM tree writes sequentially, and compresses its immutable files well. Facebook moved its main user database from compressed InnoDB to MyRocks, an LSM engine for MySQL. It reported that this cut storage by more than half.

Step 7: Secondary indexes and their write cost

A secondary index is one more tree, sorted by its own columns, pointing back to the row:

• InnoDB stores rows inside the primary key’s tree. This is called a clustered index. So a secondary entry holds the primary key, and a lookup by email takes two descents.
• Postgres keeps rows in a heap, and every index holds the row’s physical address. That’s one descent plus a heap read. But a row that moves must be re-pointed in every index.

One INSERT into a table with three secondary indexes

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database

Each index adds a descent, a leaf change, WAL volume and a later page write. The email index is the expensive one. With random keys, once it outgrows RAM, most inserts read a leaf from disk first. A unique index hurts an LSM tree most. The duplicate check puts a read on a write path that was fast because it never read. An update that changes an indexed column is a delete plus an insert in that index. And in Postgres, an update can touch every index (see below).

Go deeperPostgres HOT updates and the InnoDB change buffer1 min

In Postgres, any update writes a new row version at a new address. So every index gets a new entry. The exception is a HOT update (heap-only tuple). That’s when no indexed column changed, and the new version fits on the same page. Then the indexes keep pointing at the old slot, which forwards to the new one. Uber’s 2016 write-up of its move from Postgres to MySQL put this write amplification at the center. Tables with hot update paths are often given a lower fillfactor, so HOT updates find room.

InnoDB attacks the same cost differently. Its change buffer holds changes to non-unique secondary index leaves that are not in memory. It merges them when the page is next read. That turns random reads on the write path into later, batched work. Unique indexes cannot use it, because the duplicate check needs the page now. Since MySQL 8.4, it is off by default.

As a rough budget, each secondary index on a write-heavy table costs on the order of 10 to 30% of insert throughput. It costs more when its keys are random and it does not fit in memory.

Step 8: Composite indexes and the leftmost prefix

A composite index on (country, city, age) sorts by country, then by city within a country, then by age within a city. Physically each key is the three columns laid end to end, so a prefix of the columns is a prefix of the key. That gives the one rule that governs composite indexes: the index can seek on a leftmost prefix of its columns, and only on that.

Query predicate	Uses the index how
country = 'IN'	Seek to the IN block, scan it
country = 'IN' AND city = 'Pune'	Seek straight to the (IN, Pune) block
country = 'IN' AND city = 'Pune' AND age > 30	Seek to (IN, Pune, 31), scan to the end of the block
country = 'IN' AND age = 30	Seek on country only, then read every city in IN and filter
city = 'Pune'	No seek possible: the Pune entries are scattered under every country
country = 'IN' ORDER BY city	Already in order: no sort step

Order the columns equality first, then sort, then range. (MongoDB documents this as the ESR rule.) A range on a column stops the seek there. Take (country, age, city). The query country = 'IN' AND age > 30 AND city = 'Pune' can seek on country and the age range. But it must filter city row by row.

JCompositeIndexDemo.javaPycomposite_index.pyC#CompositeIndex.csGocomposite_index.goTScomposite-index.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CompositeIndexDemo {
    // A composite key is the columns laid end to end in an order-preserving encoding, so
    // sorting the keys sorts by country, then city, then age. Fixed-width numbers keep 9 before
    // 10. The row id at the end makes every key unique, as databases do for secondary indexes.
    static String indexKey(String country, String city, int age, int rowId) {
        return String.format("%s|%s|%03d|%06d", country, city, age, rowId);
    }

    record Result(int matches, int examined) {}

    // An index on (country, city, age): one sorted list of keys, like the leaves of a B-tree.
    static class CompositeIndex {
        private final List<String> keys;

        CompositeIndex(List<String> keys) {
            this.keys = new ArrayList<>(keys);
            Collections.sort(this.keys); // CREATE INDEX sorts once; later inserts would go into place
        }

        // The binary search is the B-tree descent: it finds the first key >= probe.
        private int lowerBound(String probe) {
            int lo = 0, hi = keys.size();
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (keys.get(mid).compareTo(probe) < 0) lo = mid + 1; else hi = mid;
            }
            return lo;
        }

        // Seek to the first key with this prefix, read until the prefix stops matching.
        Result scanPrefix(String prefix) {
            int i = lowerBound(prefix), examined = 0;
            while (i < keys.size() && keys.get(i).startsWith(prefix)) { examined++; i++; }
            return new Result(examined, examined);
        }

        // With every column before age fixed, a range on age is one contiguous slice.
        Result scanAgeRange(String prefix, int lo, int hi) {
            int i = lowerBound(prefix + String.format("%03d", lo)); // seek straight to age lo
            int matches = 0, examined = 0;
            while (i < keys.size() && keys.get(i).startsWith(prefix)) {
                examined++;
                if (Integer.parseInt(keys.get(i).split("\\|")[2]) > hi) break; // sorted by age: done
                matches++;
                i++;
            }
            return new Result(matches, examined);
        }

        // A predicate on a column after a gap can only filter: every key under the prefix is
        // read and checked. With an empty prefix this is a full index scan.
        Result scanFilter(String prefix, int column, String value) {
            int i = lowerBound(prefix), matches = 0, examined = 0;
            while (i < keys.size() && keys.get(i).startsWith(prefix)) {
                examined++;
                if (keys.get(i).split("\\|")[column].equals(value)) matches++;
                i++;
            }
            return new Result(matches, examined);
        }
    }

    static void show(String query, Result r) {
        System.out.printf("%-48s %6d rows, %6d entries read%n", query, r.matches(), r.examined());
    }

    public static void main(String[] args) {
        String[] countries = {"BR", "DE", "IN", "US"};
        List<String> keys = new ArrayList<>();
        for (int i = 0; i < 100_000; i++) {
            keys.add(indexKey(countries[i % 4], String.format("c%02d", (i / 4) % 25), 18 + (i / 100) % 60, i));
        }
        CompositeIndex idx = new CompositeIndex(keys);

        show("country='IN' AND city='c07'", idx.scanPrefix("IN|c07|"));
        show("country='IN' AND city='c07' AND age 30..39", idx.scanAgeRange("IN|c07|", 30, 39));
        show("country='IN' AND age=30 (skips city)", idx.scanFilter("IN|", 2, "030"));
        show("city='c07' (no leading column)", idx.scanFilter("", 1, "c07"));
    }
}

The same index reads 171 entries when the query uses all three columns. It reads 25,000 when the middle column is skipped, and all 100,000 when the leading column is missing. Some engines narrow the gap with a skip scan: they seek once per distinct leading value (Oracle, MySQL 8.0.13 and later, Postgres 18). That helps only when the leading column has few distinct values.

Step 9: Covering, partial and expression indexes

Covering indexes. If the index holds every column a query needs, the database answers from the index alone, and skips the table read. This is an index-only scan. Postgres and SQL Server can store extra columns in the leaves, without sorting on them: CREATE INDEX ON orders (customer_id) INCLUDE (status, total). InnoDB secondary indexes always cover the primary key. In Postgres, vacuum must also mark the heap page all-visible. Otherwise the scan checks the heap anyway.

Partial indexes. Index only the rows queries look for: CREATE INDEX ON runs (due_at) WHERE state = 'pending'. If 0.1% of a billion rows are pending, the index holds a million entries, stays in memory, and ignores writes to finished rows. A partial unique index enforces rules like “one active trip per rider”. Postgres and SQLite have them, SQL Server calls them filtered indexes, MySQL has none.

Expression indexes. CREATE INDEX ON users (lower(email)) serves WHERE lower(email) = ?. The query must use the same expression, and the function must be deterministic.

Step 10: When the index is not used

The planner prices each plan and picks the cheapest, so an index can exist and be ignored. The common causes:

Cause	Example	Fix
Low selectivity	WHERE status = 'active' matches 60% of rows	Correct behavior: a scan is cheaper. A partial index on the rare values
Function on the column	WHERE date(created_at) = '2026-10-28'	Rewrite as a range: created_at >= '2026-10-28' AND created_at < '2026-10-29', or add an expression index
Implicit cast	A varchar column compared with a number (MySQL), or nvarchar parameters on a varchar column (SQL Server)	Pass the column’s own type: a cast on the column means no seek
Leading wildcard	WHERE name LIKE '%son'	A trigram or full-text index; B-trees only seek on prefixes
Not a leftmost prefix	WHERE city = ? on (country, city)	Another index, or reorder columns
Collation	Postgres LIKE 'abc%' on a column with a non-C collation	text_pattern_ops or COLLATE "C" on the index
Stale statistics	A table grew 100x since the last ANALYZE	Run ANALYZE; check autovacuum and auto-analyze thresholds

For low selectivity, the crossover comes early. By default, Postgres prices a random page read at 4 times a sequential one. So matching a few percent of a table can make a sequential scan win. (On SSDs, setting random_page_cost near 1.1 moves it.) EXPLAIN ANALYZE shows the chosen plan, and the rows each step actually read.

Go deeperInverted and geospatial indexes2 min

A B-tree sorts one value per row along one line. Two kinds of query do not fit that shape.

Many values per row. Full-text search, tags and JSON keys put many terms in one row. An inverted index flips the mapping. Each term points to a sorted, compressed posting list of the rows that contain it. A query intersects the lists. Postgres builds these as GIN indexes, for tsvector, arrays and jsonb. Elasticsearch and Lucene are built around them, with the same LSM idea of immutable segments merged in the background. The search block covers tokenizing, ranking and sharding. Metrics stores in the style of Prometheus use the same structure for label values, as the metrics and monitoring design shows.

Two dimensions. A B-tree on (lat, lng) is sorted by latitude first. So “within 500 m” reads a whole band of latitude across the planet. There are two fixes:

• An R-tree (PostGIS on a GiST index) nests bounding rectangles, and searches the plane directly.
• A space-filling curve (geohash, S2, H3) maps each point to a one-dimensional cell id. Its prefixes are nested cells. So a radius becomes a few range scans on an ordinary B-tree.

The proximity service works through both.

Options and tradeoffs

Storage engine: B-tree or LSM tree

Option	Best at	Weak at	Used by	Pick when
B-tree	Point reads, range scans, predictable latency, transactions	Random writes larger than RAM; space at 70% page fill	Postgres, MySQL InnoDB, SQL Server, Oracle, SQLite, LMDB	Read-heavy or mixed OLTP, many secondary indexes, range queries
LSM, leveled	Write throughput with good point reads; compression	Write amplification of 10 to 30; compaction competes for IO	RocksDB, LevelDB, MyRocks, CockroachDB (Pebble), TiKV	Write-heavy with point reads, SSDs, space matters
LSM, size-tiered	Highest ingest rate, lowest write amplification	Reads check many files; up to 2x space; slow tombstone cleanup	Cassandra STCS, ScyllaDB, RocksDB universal	Append-mostly data, writes far beyond reads, disk headroom available

TradeoffA B-tree engine by default, an LSM engine when writes dominate

We gain

Range scans and secondary indexes that stay fast, one read per lookup, and decades of tooling. An LSM engine is chosen deliberately, for a write rate or a data volume that a B-tree’s random IO cannot sustain.

We give up

A B-tree pays a page write per small change and about 40% of space in half-empty pages. An LSM tree pays compaction IO in the background, tail-latency spikes when compaction falls behind, and slower range scans.

Go deeperOther compaction strategies1 min

Cassandra also ships leveled compaction, and time-window compaction. Time-window compacts each time window alone, and drops it whole when its TTL expires. It’s the right choice for time series. Since 5.0, Cassandra also has a unified strategy that tunes between tiered and leveled. RocksDB’s universal compaction is its size-tiered variant. ScyllaDB adds an incremental strategy that splits big tiered merges into small steps, to avoid the 2x space peak. Choose by workload, not by database.

Index structure: match the query shape

Structure	Answers	Cannot answer	Example
B-tree	Equality, ranges, prefixes, ORDER BY, min/max	Suffix and infix matches, 2D nearness	Almost every index you will create
Hash	Equality only, O(1)	Ranges, order, prefixes	Postgres hash index, Bitcask keydir, InnoDB adaptive hash
Inverted (GIN)	“Rows containing term X”, arrays, JSON keys	Order by anything but relevance	Full text, tags, jsonb @>
R-tree (GiST)	Overlap, containment, nearest neighbor in 2D+	Plain equality cheaply	PostGIS geometry, ranges, exclusion constraints
BRIN (block range)	Ranges on columns that follow physical order	Anything on randomly ordered columns	created_at on an append-only 5 TB events table: a few MB of index
Bitmap	Combining low-cardinality filters in analytics	Frequent concurrent updates	Oracle data warehouses; columnar engines use similar per-block min/max

TradeoffB-tree unless the query shape rules it out

We gain

One structure that serves equality, ranges and ordering, so one index often serves several queries.

We give up

For text search, 2D queries or huge append-only tables, a B-tree is either useless or many times larger than the specialized index.

Primary key layout: clustered or heap

InnoDB and SQL Server store rows inside the primary key’s tree. Postgres and Oracle keep a heap, and point every index at it (Step 7). In a clustered table, the primary key choice shapes every index.

Go deeperClustered vs heap, side by side1 min

Option	How rows are stored	Strengths	Weaknesses
Clustered (InnoDB, SQL Server default)	Rows live in the primary key’s B-tree leaves	Primary key range scans read adjacent rows; no extra hop	Random primary keys split pages everywhere; secondary lookups take two descents; wide primary keys bloat every secondary index
Heap (Postgres, Oracle default)	Rows in insert order; every index points to an address	Primary key is just another index; insert order costs nothing	Every lookup is an index read plus a heap read; updates may touch every index

TradeoffA short, time-ordered primary key in a clustered table

We gain

Inserts append at the right edge, pages fill to 90%+, and every secondary index stays small, because each of its entries carries the primary key.

We give up

The key leaks creation order and time, and in a range-partitioned distributed store all new rows land on the last range.

Secondary indexes in a partitioned store: local or global

Once data is partitioned, a secondary index can live with each partition or be partitioned by its own key.

Option	Write	Read by the indexed column	Examples
Local (per partition)	One partition, same transaction as the row	Scatter to every partition and gather	Cassandra secondary indexes and SAI, MongoDB on a sharded cluster, Elasticsearch
Global (partitioned by term)	Row and index entry on different nodes: async or a distributed transaction	One partition holds every match	DynamoDB GSI (eventually consistent), Spanner and CockroachDB (transactional)

TradeoffGlobal indexes for high-volume lookups, local for occasional ones

We gain

A global index turns a 100-partition scatter into one targeted read.

We give up

Every write becomes a cross-node write. Async global indexes return stale results for a short window, and in DynamoDB an under-provisioned GSI throttles writes to the base table.

How many indexes

Start with the primary key, and the indexes the known hot queries need. Prefer one composite index that serves several queries over several single-column ones. And remove indexes that statistics show are never used.

TradeoffFew, composite, measured indexes

We gain

Write throughput, buffer pool space for the indexes that matter, and fewer plan surprises.

We give up

Some rare queries scan, and adding an index later on a large table is an operation that needs planning (see At scale).

How it fails

Failure	What happens	Detect	Blast radius	Fix
Index outgrows memory	Random-key inserts read leaves from disk; throughput falls off a cliff	Hit ratio drops; read IOPS rise on a write-only load	Every write to the table	Time-ordered keys, more RAM, partial indexes, partitioning
Too many indexes	Write latency, WAL volume and replica lag grow with each index	Indexes with zero scans in usage statistics	Writes, and every replica	Drop unused indexes and those that prefix another
Plan flips to a scan	After a data or statistics change, a 2 ms query becomes a 30 s scan	One query’s p99 jumps in pg_stat_statements	That query, then the IO it hogs	ANALYZE, fix the predicate; pin a plan only as a last resort
Compaction falls behind	More files per read, then RocksDB slows and stops writes at 20 and 36 L0 files	Pending compaction bytes, L0 file count	The node’s reads, then writes	More compaction IO, throttle ingest, leveled over tiered
Tombstone pile-up	Scans read deleted rows; Cassandra warns at 1,000 per query and fails at 100,000	Tombstone warnings, slow range reads	Queries on that partition	Never use an LSM table as a queue; TTL with time-window compaction
Hot right edge	Increasing keys all hit the last leaf, or the last range in a distributed store	Latch waits on one page; one hot node	All inserts	Hash-prefix the key in distributed stores; accept it on one node

Two of these build up slowly, and then arrive all at once:

• The memory cliff. Take a 500 GB random-key index and a 64 GB buffer pool. About 87% of inserts miss. So 20,000 inserts a second become 17,000 random reads a second, with no code change.
• Compaction debt. For a while, an LSM tree accepts writes faster than it compacts them. The debt arrives hours later, as more files per read, and then write stalls. Under size-tiered compaction, a node at 60% disk may be unable to merge its largest tier at all.

Common mistake

"An index always makes the query faster"

An index helps a query that reads a small fraction of the table through a predicate it can seek on. For a query matching 30% of rows it turns one sequential scan into millions of random reads, and the planner is right to ignore it. Meanwhile it slows every write.

Common mistake

"LSM trees are bad at reads"

Point reads on a leveled LSM tree with Bloom filters cost about one disk read, the same as a B-tree. LSM trees are worse at range scans, which merge every level, and at reads during compaction debt. Those are the cases to name.

At scale

Numbers worth knowing:

Quantity	Typical value
Page size	8 KB Postgres and SQL Server, 16 KB InnoDB
B-tree fanout	Hundreds to about 1,000 per internal page
B-tree height for 1 billion rows	3 to 4 levels, all but the leaf cached
Random 4 KB read	About 0.1 ms NVMe, 0.5 to 1 ms network block storage, 5 to 10 ms disk
Random read IOPS	Hundreds of thousands on NVMe; 3,000 baseline on a gp3 volume; 100 to 200 on a disk
Sequential read	2 to 7 GB/s NVMe, 125 to 1,000 MB/s gp3, 150 to 250 MB/s disk
Bloom filter	10 bits a key for about 1% false positives
RocksDB defaults	64 MB memtable, 256 MB L1, 10x per level, 4 KB blocks
Leveled LSM write amplification	10 to 30
Index size	Key size + 6 to 16 bytes per entry, over about 70% fill

At 10x. A 2 TB table’s indexes no longer fit in RAM, so random-key indexes hit the memory cliff. Time-ordered keys, partial indexes and dropping unused ones keep the hot part in memory. Index builds take hours.

At 100x. The table is partitioned. Every secondary index becomes the local-or-global decision above. A unique constraint on anything but the partition key needs a global index, or a separate uniqueness table. Write-heavy tables at this scale are where LSM stores earn their place: Cassandra, ScyllaDB, and RocksDB under CockroachDB or TiDB.

Building an index on a live table

A plain CREATE INDEX in Postgres blocks writes for the whole build. That’s hours on a billion rows. Every major engine has an online build that keeps the table writable. The price is a slower build, extra IO, and new failure modes: an invalid index left behind, or replicas hours behind.

Go deeperOnline index builds, engine by engine2 min

• Postgres CREATE INDEX CONCURRENTLY scans the table twice and waits for every transaction that could still see old row versions, so one long-running transaction stalls it. It allows reads and writes throughout, cannot run inside a transaction, and on failure leaves an invalid index to drop.
• MySQL InnoDB online DDL (ALGORITHM=INPLACE, LOCK=NONE) builds the index while logging concurrent changes. Then it applies the log under a brief metadata lock. On replicas, the same ALTER runs after it finishes on the primary. By default, it holds up replication behind it, so replicas lag by the length of the build. Tools such as gh-ost build a shadow table from the binary log instead, and throttle on replica lag.
• DynamoDB backfills a new GSI in the background. The base table keeps serving, and the GSI must have enough write capacity or it throttles the table’s writes.

The safe sequence everywhere: build in a quiet window, and throttle on replica lag and IO. Verify with EXPLAIN that the plan uses the new index. Then drop the indexes it replaces.

What to monitor

1. Index size against buffer pool size, per index: the memory cliff is visible months ahead.
2. Hit ratio, and read IOPS on write-heavy tables.
3. Index usage counts: an unused index is pure write cost.
4. Slowest queries by total time, with alerts on plan changes.
5. LSM stores: pending compaction bytes, L0 files, write stalls, tombstones per read, and free disk against the largest compaction.
6. Bloat after update or delete churn, fixed with REINDEX CONCURRENTLY or OPTIMIZE TABLE.

In the interview

Interviewer asksThis query got slow. How do you decide which index to add?

Start from EXPLAIN ANALYZE. Does it scan? How many rows does each step read, versus return? Build the index from the predicate: equality columns, then the ORDER BY column, then the range column. Then the seek covers the most, and the sort disappears. Include the few selected columns, for an index-only scan. Make it partial if the query touches a slice, or extend an existing index. Then weigh the write cost. On a table taking 20,000 inserts a second, another random-key index may cost more than the query saves.

Interviewer asksWhen would you pick an LSM-based store over a B-tree one?

When writes dominate and outrun random IO: event ingestion, time series, a key-value store at 100,000 writes a second. Writes become sequential appends, files compress well, and with Bloom filters a point read still costs about one disk read. Not for heavy range scans, many secondary indexes or unique constraints. Then pick the compaction: leveled when reads matter and space is tight, size-tiered or time-window for append-mostly data with disk headroom.

Interviewer asksWe added four indexes to the orders table and inserts are three times slower. Why, and what do you do?

Each insert now updates five B-trees: five descents, five leaf changes, five times the WAL. The random-key indexes hurt most, since once they exceed the buffer pool each insert reads a leaf from disk first. Drop unused indexes, merge single-column ones into composites, make indexes partial where queries touch a slice, and keep the primary key time-ordered. If the write rate is the requirement, move heavy queries to a read store fed from the change stream.

Interviewer asksHow do you add an index to a 2 TB table in production?

Never with a blocking build. In Postgres, CREATE INDEX CONCURRENTLY after checking for long-running transactions, dropping the invalid index if it fails. In MySQL, gh-ost or online DDL throttled on replica lag. Watch IO and lag, confirm with EXPLAIN that the planner uses it, then drop what it replaces.

Common mistake

Indexing each column of the WHERE clause separately

Three single-column indexes on country, city and age do not add up to one on (country, city, age). The planner usually picks one and filters the rest, or combines them with a bitmap AND that still reads every matching entry of each. One composite index in equality-sort-range order seeks straight to the answer and costs one tree on writes instead of three.

Mid-level covers

Adds an index for the hot query. Knows a B-tree gives logarithmic lookups and range scans. Knows indexes slow writes, and can say an LSM tree is write-optimized.

Senior adds

Sizes the index and its height, and knows whether it fits in memory. Orders composite columns by equality, sort and range. Uses covering and partial indexes. Explains why the planner ignores an index. Compares B-tree and LSM through write, read and space amplification. Picks a compaction strategy. Knows how to build an index online, and what that does to replicas.

Seen in

• Design a key-value store: an LSM tree with Bloom filters and leveled compaction, because a third of the traffic is writes.
• Design a proximity service: a geohash column on a B-tree turns “within 500 m” into nine prefix scans. The whole geo index fits in memory.
• Design a ride hailing service: a partial unique index allows one active trip per rider. Driver positions move too often for a database spatial index.
• Design a unique ID generator: time-ordered IDs append at the right edge of a B-tree, and 8-byte keys instead of 16 shrink every index.
• Design a distributed job scheduler: two partial indexes make “find due work” a short range scan over pending runs only.
• Design Dropbox: journal reads are B-tree range scans on (namespace, journal id).
• Design a metrics and monitoring system: an inverted index from label values to sorted series IDs, intersected per query.
• Design a URL shortener: listing a user’s links needs a secondary index beside the key lookup.
• Design a distributed message queue: the opposite choice, a log with no per-message index at all, so appends and reads stay sequential.

Recap

Why. A billion-row scan takes minutes, an index lookup one random read. The price is a second copy of the data that every write maintains.

B-tree. Pages of 8 to 16 KB, fanout in the hundreds, 3 to 4 levels for a billion rows. Internal pages are cached, so it’s one disk read per lookup. Updated in place, about 70% full under random keys. Each small write dirties a whole page.

LSM tree. WAL plus memtable, flushed as immutable SSTables, merged by compaction. Fence pointers and Bloom filters keep point reads near one disk read. Leveled: write amp 10 to 30, space amp 1.1. Size-tiered: low write amp, more files per read, up to 2x space.

Using indexes well. Each secondary index is one more tree on every write. Composite indexes seek on a leftmost prefix: equality, sort, range. Covering, partial and expression indexes. Functions on columns, implicit casts, leading wildcards and low selectivity leave an index unused.

Operations. Build online and watch replica lag, track index size against memory, drop unused indexes, and for LSM stores watch compaction debt and tombstones.

Further reading

• On this site:
  • Choosing a database for which engines use which structure.
  • Partitioning for local and global secondary indexes.
  • Search for inverted indexes.
  • The key-value store for an LSM tree inside a full design.
• Martin Kleppmann, Designing Data-Intensive Applications, chapter 3 (Storage and Retrieval): hash indexes, SSTables, LSM trees and B-trees from first principles.
• Markus Winand, Use The Index, Luke: composite indexes, why indexes go unused, and covering and partial indexes, with examples for each major database.
• Patrick O’Neil and others, The Log-Structured Merge-Tree (LSM-Tree), Acta Informatica 1996: the paper that introduced the structure.