Indexes, B+ trees, LSM trees and Bloom filters

Why it matters

Many database performance questions come down to an index: is there one the query can use, does the planner choose it, and what does it cost on writes? System-design interviews add the engine question, because a write-heavy event store and a read-heavy catalog want different structures. Knowing the mechanics lets you estimate instead of guess.

Core ideas

B+ trees. Inner nodes hold separator keys and child pointers; leaves hold keys with row pointers (or the rows themselves in an index-organized table) and are linked for range scans. With 8 KB pages and entries of roughly 16 bytes, fanout is in the hundreds, so a tree over 100 million keys is three or four levels deep and its upper levels stay in memory. A point lookup costs one page per level; a range scan costs the descent plus the matching leaves, plus one heap fetch per row when the index does not cover the query. An insert into a full leaf splits it and pushes a separator upward, which keeps the tree balanced. Concurrent access uses short latches with crabbing: release the parent once the child cannot split or merge.

Using indexes well. A composite index on (a, b, c) serves predicates on a, on a and b, and on all three, in that prefix order; put equality columns before the range column. An index-only scan answers from the index alone when it contains every needed column (PostgreSQL also consults its visibility map). For predicates that match a large fraction of rows a sequential scan is usually faster, because random heap fetches cost more than reading pages in order; the planner decides from statistics. Every index slows inserts and updates of the indexed columns. Hash indexes serve only equality; BRIN-style indexes store per-block-range minimum and maximum values and suit naturally ordered data such as append-only timestamps.

LSM trees. Writes go to a log and an in-memory sorted memtable. A full memtable is flushed as an immutable sorted file; background compaction merges files to discard overwritten values and deletion markers (tombstones). A read checks the memtable and then files from newest to oldest, so per-file Bloom filters and key-range metadata avoid most useless file reads.

Amplification. Write amplification is bytes written to storage per byte of user data; read amplification is pages or files touched per lookup; space amplification is storage used per byte of live data. Leveled compaction (one sorted run per level, each level about ten times larger than the previous) keeps reads and space low but rewrites each byte many times as data moves down the levels. Tiered compaction (several runs per level, merged together) writes less but reads and stores more. B+ trees update in place: low read amplification, but each small change dirties a whole page. The RUM conjecture frames the tradeoff: you can optimize two of read cost, update cost and memory (space) overhead, not all three.

Bloom filters. A bit array of m bits and k hash functions. Inserting a key sets k bits; a lookup that finds any of its bits unset proves the key is absent. With n keys the false-positive rate is about (1 − e^(−kn/m))^k, minimized near k = (m/n)·ln 2. Ten bits per key gives roughly a 1% false-positive rate. Standard Bloom filters do not support deletion and do not help range queries.

bits_per_key = 10, k = 7:  (1 - e^(-0.7))^7 ≈ 0.008

Common misconceptions

• "An index always makes a query faster." For predicates that match many rows a sequential scan wins, and every index slows writes.
• "B+ tree lookups are O(log n) random reads, so they are slow." The logarithm's base is the fanout: three or four levels with cached upper levels mean one or two real I/Os.
• "Column order in a composite index does not matter." It decides which predicates can use the index and whether a sort can be avoided.
• "LSM trees are always faster for writes." Their writes are cheap up front, but compaction consumes I/O and CPU continuously and can cause latency spikes and write stalls.
• "Bloom filters give exact answers." They return false positives (never false negatives) and use memory proportional to the number of keys.
• "Learned indexes replace B+ trees." Benchmarks show wins mainly for read-only, in-memory lookups; updates, worst cases and integration remain open.

How to approach it

Do the arithmetic once by hand: page size, entry size, fanout, height, then I/Os per query, and a Bloom filter's false-positive rate for two settings. Then run EXPLAIN in PostgreSQL on queries against a table with a composite index and watch the plan switch between index, bitmap and sequential scans as selectivity changes. In interviews, ask about the read/write mix, key distribution, point versus range queries and latency targets before choosing a structure, and quantify amplification instead of saying "LSM is write-optimized".