Database Indexing

B-trees, LSM trees, composite, geospatial and inverted indexes.

Without an index, finding a row means scanning the whole table — fine for a thousand rows, catastrophic for a billion. Indexes are extra data structures that let the database jump straight to what you need. In interviews, they're the first answer to slow reads, before caches or replicas.

B-tree indexes

The default index in almost every relational database (and many NoSQL ones). A B-tree keeps keys sorted in a shallow, wide tree — a billion rows is only 3–4 levels deep — so lookups take a handful of disk reads.

B-trees support:

Equality: WHERE email = 'a@b.com'
Ranges: WHERE created_at > '2026-01-01'
Sorting: ORDER BY created_at DESC without a separate sort step
Prefix matches: WHERE name LIKE 'joh%' (but not '%ohn')

The cost: every write must also update every index on the table, and indexes take storage.

Composite indexes

An index on multiple columns, sorted by the first column, then the second, and so on.

CREATE INDEX idx_posts_user_time ON posts (user_id, created_at DESC);

-- Served entirely by the index:
SELECT * FROM posts WHERE user_id = 42 ORDER BY created_at DESC LIMIT 20;

Column order matters: this index helps queries filtering on user_id (and optionally created_at), but not queries filtering on created_at alone. The rule of thumb is equality columns first, then range/sort columns.

A covering index includes every column a query needs, so the database never touches the table itself.

Hash indexes

Hash a key straight to its location: O(1) equality lookups but no ranges or sorting. Common in in-memory stores and key-value databases; rarely worth choosing explicitly in a relational database.

LSM trees

Log-Structured Merge trees power write-heavy stores: Cassandra, RocksDB, ScyllaDB, and the storage engines under many others.

Writes go to an in-memory table (memtable) and a write-ahead log — very fast, sequential I/O.
When the memtable fills, it's flushed to disk as an immutable sorted file (SSTable).
Background compaction merges SSTables and discards overwritten or deleted data.
Reads check the memtable, then SSTables — using Bloom filters to skip files that can't contain the key.

LSM trees trade some read performance for much higher write throughput than B-trees.

Specialized indexes

Geospatial indexes in a little more depth

Geohash encodes a lat/lng as a string where shared prefixes mean nearby locations. Proximity search becomes a prefix lookup on the current cell plus its neighbors. Simple, and works with any B-tree.
Quadtrees recursively split space into four quadrants, subdividing dense areas more. Great for uneven density (cities vs oceans).
R-trees group nearby shapes into bounding rectangles; they're what PostGIS uses.

[!INTERVIEW] Name the index and the query it serves "We'll add a composite index on (event_id, status) so checking available seats is an index lookup" beats "we'll add indexes." And for proximity search, saying "Postgres with PostGIS handles this fine at our scale" is often better than reaching for a specialized system.