Indexing

An index is a second data structure that makes one class of lookup cheap and makes every write do more work. Name the query, then name the index. The other order is how you get a slow database with a large disk.

B-trees

The default in Postgres, MySQL, and most relational engines. Leaves are sorted, so equality, range, and ORDER BY can all use the same structure. A composite index (a, b, c) supports predicates that use a left prefix: a, then a,b, then a,b,c. It does not efficiently support b alone.

Put columns you test with = first. Put the range or the sort last. A covering index includes the extra columns the query selects, so the engine never visits the table. A partial index restricts who is in the index (WHERE status = 'open'). That is the right tool for a work queue: the index stays proportional to the backlog, not to history.

Hash indexes only do equality. They are rarely the thing you ask for by name.

LSM trees

Log-structured merge trees, used by Cassandra, RocksDB, LevelDB, and many modern storage engines, turn a write into an append to a memory buffer. When the buffer fills, it flushes as a sorted run. Reads check the memory buffer and then the runs, skipping runs with a bloom filter. Compaction merges runs so reads do not degrade forever.

Choose an LSM-backed store when the workload is write-heavy and the reads are by the primary key you designed. The bill comes due as write amplification and as worse performance on read-modify-write of a random old row.

Inverted indexes

An inverted index maps a term to the list of documents that contain it. That is search. Rankers (BM25) score those postings. Postgres can do a smaller version with tsvector and GIN. Elasticsearch and OpenSearch are this structure with a distributed query layer. Updates are not like row updates: changing one word rewrites a segment, which is why search indexes are often rebuilt from a change stream rather than updated in place on the request path.

Geospatial and vector indexes

Geospatial indexes (geohash, R-tree, S2 cells) answer “what is near this point?” without scanning the planet. You still decide the radius and the tie-break. Vector indexes (HNSW, IVF) answer “what is near this embedding?” approximately. Both degrade when you also apply a very selective filter. Say whether you filter first (and risk a tiny candidate set the index cannot navigate) or search first and filter after (and risk missing good neighbors that failed the filter). That sentence is the whole deep dive.

Every index costs memory and write latency. In the interview, two or three justified indexes beat a schematic covered in them.