Database Indexing

Why indexes exist

Without an index, finding a row means a full table scan: O(n) pages read from disk. On a 100 million row table that can mean seconds of I/O per query. An index is a separate structure, sorted or hashed by the indexed columns, that lets the database locate matching rows in O(log n) page reads, typically 3 to 4 for a B-tree even on very large tables.

The cost is paid on writes. Every INSERT, UPDATE, or DELETE must also update every index on the table, so a table with six indexes does roughly seven writes per logical write. Indexes also consume storage, often 20 to 50 percent of table size each, and they occupy buffer pool memory that could cache table data. The design skill is indexing the queries you actually run and nothing more.

A useful interview framing: an index is a materialized sort order. Any question of the form 'find rows where X equals or is between values' benefits from a structure sorted by X.

B-trees: the read-optimized default

The B-tree (technically B+ tree in most databases) is the default index in Postgres, MySQL InnoDB, Oracle, and SQL Server. It is a balanced tree of fixed-size pages (commonly 8 or 16 KB) where internal nodes hold routing keys and leaf nodes hold the indexed values in sorted order, linked for range scans. With a branching factor of a few hundred, a 4-level B-tree addresses billions of rows, so a point lookup costs about 4 page reads, most of which are usually cached.

B-trees update in place: a write finds the target leaf page and modifies it, with occasional page splits when a page fills. This gives strong, predictable read performance and efficient range queries (WHERE created_at BETWEEN two timestamps walks linked leaves sequentially). Writes involve random I/O across the tree, which historically was the bottleneck on spinning disks and still causes write amplification through the write-ahead log plus dirty page flushes.

InnoDB adds a wrinkle worth knowing: the table itself is stored as a B-tree clustered on the primary key, and secondary indexes store the primary key as their pointer. This makes primary key lookups very fast, but a long primary key inflates every secondary index, and random primary keys (like UUIDv4) cause page splits and cache misses; sequential IDs or UUIDv7 insert much more gracefully.

LSM trees: the write-optimized alternative

Log-structured merge trees power Cassandra, RocksDB, LevelDB, HBase, and the storage engines behind many modern systems. Writes go to an in-memory sorted structure (the memtable) and an append-only commit log; when the memtable fills (say, 64 MB) it is flushed to disk as an immutable sorted file (an SSTable). Background compaction merges SSTables, discarding overwritten and deleted entries.

This makes writes sequential and fast: an LSM engine can sustain write throughput several times higher than a B-tree because it never updates pages in place. The price is read amplification: a point read may need to check the memtable plus several SSTables across levels. Bloom filters mitigate this by letting the engine skip SSTables that definitely do not contain the key, cutting most negative lookups to zero disk reads.

Compaction is the operational heart of an LSM system. It causes write amplification (the same data is rewritten each time it moves down a level, commonly 10x to 30x total) and consumes I/O bandwidth that can spike read latencies, which is why Cassandra operators care about compaction strategy (size-tiered for write-heavy, leveled for read-heavy). The rule of thumb: B-trees for read-heavy and range-heavy relational workloads, LSM trees for write-heavy, append-mostly workloads.

Composite, covering, and specialized indexes

A composite index sorts by multiple columns in order, like (user_id, created_at). The leftmost-prefix rule governs its use: this index accelerates queries filtering on user_id alone, or user_id plus created_at, but not created_at alone, because the data is sorted by user_id first. Column order matters: put equality-filtered columns first and range-filtered or sort columns last, so an index on (user_id, created_at) perfectly serves 'the 20 most recent posts by user X'.

A covering index includes every column a query needs, letting the database answer from the index alone without touching the table (an index-only scan). If a query selects only user_id and email, an index on (user_id) INCLUDE (email) in Postgres avoids the heap fetch entirely, often turning a 50 millisecond query into a 2 millisecond one. The tradeoff is a fatter index and more write overhead.

Beyond B-trees, know the specialized options at a sentence each: hash indexes for pure equality lookups, GIN indexes in Postgres for JSONB and full-text search, partial indexes that only cover rows matching a predicate (for example only unshipped orders, keeping the index tiny), and geospatial indexes (R-trees, or geohash-based schemes) for location queries.

Tradeoffs