Database Indexing: Why B-Trees Read Fast and LSM-Trees Write Fast

The query looked innocent: SELECT * FROM events WHERE user_id = 91823. In staging, against ten thousand rows, it returned instantly. In production, against fifty million, it took nine seconds and pinned a CPU — because there was no index on user_id, so the database did the only thing it could: read every single row and throw away 49,999,999 of them to find yours.

That is a full table scan, and it is the default fate of any lookup the database can’t answer any other way. An index is the structure that makes the database not do that — the difference between walking to the right page of a book and reading the whole book to find one sentence.

The intuition: the index at the back of the book

A textbook has a few hundred pages and, at the back, an index: terms in alphabetical order, each pointing at the pages where it appears. Nobody finds “mutex” by reading the book cover to cover — they jump to M and follow the pointer. The index isn’t the content; it’s a smaller, ordered structure that exists only to make lookups fast.

Every database index is a version of this trade. It is redundant data, kept in sorted (or hashed) order, maintained on every write, whose only job is to turn “scan everything” into “jump to the answer.” Which means an index is never free — you pay for it on the way in to save on the way out.

From here the members-only deep dive picks up: the annotated B+ tree vs LSM-tree diagram, the three amplifications (read, write, space) storage engineers argue over, the composite-index code walkthrough with the leftmost-prefix and covering-index rules, who uses which family in the wild, the full tradeoff comparison, and an interview corner with a “pick the right index” challenge and a self-check quiz.