What it is
An index is an auxiliary structure that trades extra writes and storage for fast lookups. The two families that matter are B-trees (read-optimised, update-in-place — Postgres, MySQL/InnoDB) and LSM-trees (write-optimised, append-then-compact — Cassandra, RocksDB, HBase). Everything else — hash, composite, covering, inverted, geospatial — is a variation on the same bargain: pay on write and in space, collect on read.
This is the concept that separates candidates who draw boxes from candidates who know what's inside the box. It surfaces as "why is this query slow", as the storage-engine choice in a key-value store design, and as the staff-level probe behind any write-heavy system. The scoring is on whether I can explain why a lookup among a billion rows costs three or four page reads, and what I gave up to make that true.
I'd index exactly the columns my queries filter on — and I'd say out loud that every index slows every insert, so I index the queries I have, not the ones I might have.
The picture
The variants and when to pick each
B-tree — the read-optimised default
A balanced tree whose nodes are disk pages (4–16 KB). Because each page holds hundreds of keys, the tree stays absurdly shallow: height 4 with a branching factor of 500 covers roughly 60 billion rows, so any point lookup is 3–4 page reads, and the top levels live in memory anyway. Range queries fall out for free because leaves are sorted and linked.
This is what Postgres and InnoDB give me by default and it is the right answer for OLTP: predictable point and range reads. The cost is on the write side — updates are in-place random I/O, and inserts into full pages trigger page splits, which is write amplification.
LSM-tree — write-optimised, append and compact
Writes go to an in-memory memtable (plus a WAL for durability), which is flushed as an immutable sorted SSTable; background compaction merges SSTables. The disk only ever sees sequential writes, which is why Cassandra and RocksDB swallow write volumes that would melt a B-tree.
The bill arrives on reads: a lookup may check the memtable and several SSTables, so read p99 gets spiky. Per-SSTable Bloom filters (about 10 bits per key for a 1% false-positive rate) skip most of those checks, and the compaction strategy — leveled versus size-tiered — tunes the read/write/space amplification triangle.
Composite, covering and partial — the practical toolkit
A composite index on (user_id, created_at) serves "this user's recent items" in one descent — but only queries matching the leftmost prefix: it helps user_id alone, and does nothing for created_at alone. A covering index includes every column the query needs, so the database answers from the index without touching the table at all — the cheapest read there is. Partial indexes cover only the rows worth indexing (say, unfinished orders), keeping the structure small and hot.
Specialised indexes to name, not to dwell on
Hash indexes do exact-match only — O(1) but no ranges, which is why they are rare as primary structures. Inverted indexes map terms to documents and are the heart of Elasticsearch and full-text search. Geospatial queries need R-trees, geohashes or S2 cells — regular B-trees can't answer "within 5 km" efficiently. Naming the right one when the query shape demands it shows range; deep-diving uninvited wastes clock.
Numbers worth memorising
| B-tree height 4, branching ~500 | covers ~60B rows in 3–4 page reads |
| Indexed point read vs full scan | ~1–10 ms vs seconds-plus |
| SSD random 4 KB vs sequential 1 MB | ~100 µs vs ~1 ms — why LSM's sequential writes win |
| LSM write amplification | commonly 10–30× via compaction |
| Bloom filter per SSTable | ~10 bits/key for 1% false positives |
Where the interviewer pushes
The first push is the write-side bill: "you added six indexes and inserts got slow — why?" The strong answer is mechanical, not hand-wavy: every insert updates every index, each update is a random page write, and page splits amplify it further. Then the fix: audit which indexes queries use, drop the dead ones, and see whether one composite or covering index can replace three single-column ones.
The second push is the storage-engine choice: "when would you pick RocksDB or Cassandra over InnoDB?" The answer is workload shape — write-heavy streams (logs, metrics, feeds, IoT) go LSM because sequential writes are 10× cheaper than random ones; read-heavy OLTP stays B-tree for predictable point and range reads. And I flag the LSM consequence unprompted: spiky read p99 from SSTable fan-out, mitigated by Bloom filters and compaction tuning — showing I know the cost, not only the benefit.