A query filters on two columns and sorts on a third. What index do you create, and what does it cost you?

Column order comes from the predicate shapes

An index on several columns is a single sorted structure keyed on the tuple of those columns in order, and that is the whole basis of the rule. Entries are ordered by the first column, then within equal first values by the second, and so on. So the engine can seek directly on a prefix of the columns and read a contiguous range, and it loses that ability the moment a column is used in a way that leaves the remaining columns unordered.

The consequence is a specific ordering rule. Columns compared for equality go first, in any order among themselves, because each equality narrows the search to one contiguous block. The column used for a range comparison or for the ordering goes last, because once you are scanning a range of one column, everything after it in the key is no longer in a useful global order.

-- The query: the most recent open orders for one tenant.
SELECT id, total FROM orders
WHERE  tenant_id = $1 AND status = 'OPEN'
ORDER  BY created_at DESC
LIMIT  20;

-- Equality columns first, the ordering column last and in the query's direction.
CREATE INDEX orders_open_recent ON orders (tenant_id, status, created_at DESC);

That index does three jobs at once, and naming all three is what separates a good answer from "I would index the WHERE clause". It resolves the filter with one seek. It supplies the rows already in created_at DESC order, so there is no sort step and therefore no sort memory and no spill to disk. And because the rows arrive in the right order, the LIMIT stops the scan after twenty of them rather than after the whole matching set has been produced and sorted. On a tenant with two million open orders, that is the difference between reading twenty index entries and reading two million rows.

Reverse the order to (created_at, tenant_id, status) and none of it works. The leading column is not constrained by the query at all, so there is no prefix to seek on, and the engine either scans the whole index or ignores it and scans the table. This is the failure that produces the complaint that "the index isn't being used" — it is being correctly judged useless.

Two refinements are worth having ready. If the query selects only columns present in the index, the engine can answer entirely from the index without touching the table at all, which is an index-only scan and roughly halves the I/O; adding total to the index as an included column buys that, at the cost of a wider index. In PostgreSQL an index-only scan additionally depends on the visibility map being current for those pages, so a table that has not been vacuumed recently silently loses the optimisation, which is a genuinely surprising operational detail. And where the filter is a small, stable subset — status = 'OPEN' on a table that is 98 percent closed orders — a partial index with that predicate in its WHERE clause is dramatically smaller and stays hot in memory.

Every index is a tax on every write

The reason not to add indexes freely is that an insert must write every index on the table, not just the one you needed. Five indexes means an insert performs six writes. An update to an indexed column is worse: it must remove the old index entry and insert the new one, in each index that includes the column. And index pages compete with table pages for the same buffer pool, so an index nobody uses is still evicting pages somebody does.

This is why the audit matters as much as the design. Unused indexes are pure cost, redundant ones are nearly so — an index on (tenant_id) is subsumed entirely by one on (tenant_id, status), because any seek the narrower one serves is served by the prefix of the wider one. Dropping the narrower is free except that it is marginally larger to scan.

There are also good reasons a planner declines an index you consider obviously applicable, and being able to name them is a strong signal. Selectivity is the usual one: if the predicate matches a large fraction of the table, following index entries to scattered table rows costs more random I/O than reading the table sequentially, so a sequential scan is genuinely the cheaper plan and the planner is right. Stale statistics are the second, where the estimated row count bears no relation to reality and the plan is chosen on bad information. And a predicate wrapped in a function or subject to an implicit type coercion is not a comparison against the indexed value at all — WHERE lower(email) = $1 cannot use an index on email, and needs an expression index on lower(email).

What the storage engine changes underneath all of this

Everything above is about which structure to build. The other half of the question is how the engine maintains it, and the two dominant designs make opposite trades.

A B-tree keeps a balanced tree of fixed-size pages and updates them in place. A read is a handful of page fetches, bounded and predictable, and a range scan follows sibling pointers through pages already in key order, so ordered reads are close to optimal. A write must find the right leaf page and modify it, which is a random write, and if the page is full it splits and the split may propagate upwards. Under a write-heavy random-key workload that becomes many small scattered writes, plus the write-ahead log entry that makes them durable.

An LSM tree never updates in place. Writes land in an in-memory sorted structure and, separately, in a sequential log for durability; when the memory buffer fills it is flushed whole as an immutable sorted file on disk. Writes are therefore sequential and cheap, which is why LSM engines absorb ingest rates a B-tree struggles with. The cost is paid on the read side and in the background. A key may live in the memory buffer or in any of several on-disk files, so a point lookup may have to check many of them — Bloom filters make the negative checks cheap and are the reason point reads stay fast, but they only answer "definitely absent" or "possibly present", and they do not help a range read, which must merge across every file that overlaps the range. Compaction then continuously rewrites those files to merge and discard superseded entries, which consumes disk bandwidth and CPU permanently in the background and causes latency variance rather than steady degradation.

Deletes are the sharpest difference. An LSM engine cannot remove a record from an immutable file, so it writes a tombstone marker that shadows the old value, and the record is only truly gone once compaction has processed every file containing it. Until then, every range read across that region must read and discard the tombstones. A workload that deletes heavily — a queue table, or anything with short-lived rows read in ranges — can therefore get slower and slower at reading a region that logically holds nothing at all, which is a failure mode with no B-tree equivalent and one worth naming explicitly.

So the choice follows the mix rather than the brand. Read-mostly, range-heavy, update-in-place workloads with strong transactional requirements are B-tree territory, which is what PostgreSQL, MySQL's InnoDB and most relational engines give you. Write-heavy append-mostly workloads with keys that arrive out of order — event ingest, time series, metrics — are what LSM engines such as RocksDB and Cassandra are built for. And one detail that changes index design in InnoDB specifically: the table is stored clustered by its primary key, and every secondary index entry stores the primary key rather than a physical row pointer, so a secondary index lookup that is not covering costs a second traversal into the clustered index. That makes covering indexes worth more there, and makes a wide primary key expensive in every secondary index at once.