Databases at Scale

Indexing at Scale

An index trades write cost and storage for read speed — it is a second, ordered copy of some columns that lets a query skip straight to matching rows instead of scanning the table. The two dominant structures, B-trees and LSM-trees, make opposite bets about where that cost lands.

B-tree indexes update in place — reads are fast and predictable, but every write is a random disk I/O to the exact page being modified
LSM-trees (log-structured merge-trees) buffer writes in memory and flush them as sorted, immutable files — writes become sequential and fast, at the cost of background compaction and slower worst-case reads
A secondary index is itself just another index structure mapping a non-primary column back to primary keys — every one you add slows down every write
A covering index includes every column a query needs, letting the database answer entirely from the index without touching the underlying row
Composite (multi-column) index column order matters: an index on (a, b) serves queries filtering on a or on a AND b, but not on b alone

The LSM-tree write path

Writes only ever append; reads may have to check the memtable and several SSTables

The memtable-flush idea, minimized

class SimpleLsmStore {
    private TreeMap<String, String> memtable = new TreeMap<>();
    private final List<TreeMap<String, String>> sstables = new ArrayList<>();
    private static final int FLUSH_THRESHOLD = 1000;

    void put(String key, String value) {
        memtable.put(key, value);
        if (memtable.size() >= FLUSH_THRESHOLD) {
            sstables.add(0, memtable);      // newest first
            memtable = new TreeMap<>();
        }
    }

    String get(String key) {
        if (memtable.containsKey(key)) return memtable.get(key);
        for (var sstable : sstables) {       // newest-to-oldest — first match wins
            if (sstable.containsKey(key)) return sstable.get(key);
        }
        return null;
    }
}

Real LSM engines add bloom filters per SSTable so a miss does not mean scanning every file

B-tree vs LSM-tree
	B-tree	LSM-tree
Writes	Random I/O, in place	Sequential I/O, append-only
Reads	Predictable — one tree lookup	May check memtable + several SSTables
Write amplification	Lower	Higher — data is rewritten during compaction
Used by	PostgreSQL, MySQL InnoDB	Cassandra, RocksDB, LevelDB