Storage Internals
Indexes: B-Trees and LSM Trees
Two ways to keep data findable, and why every index you add is a tax on every write.
By the end of this chapter
- Explain how a B-tree and an LSM tree each turn a lookup into a handful of reads
- Compare the two on write, read and space amplification
- Predict when an index will be ignored by the planner or will slow the system down
- Order the columns of a composite index from the queries it must serve
What an index actually is
A table without an index is a heap of rows in roughly the order they arrived. To find the rows matching a condition, the database reads all of them. An index is a separate, sorted structure that maps a key to where the matching rows live — a second copy of some of your data, arranged for one particular question.
That framing explains both halves of the trade. Reads get faster because the sorted structure can be searched rather than scanned. Writes get slower because every copy has to be kept in step with the table, and the database does that work synchronously, inside your write.
The cost of not having one
A 100-million-row orders table, about 200 bytes per row, queried by customer_id. Numbers are illustrative.Table size ≈ 100,000,000 × 200 B ≈ 20 GBWithout an index on customer_id, every query must read all of it.Scan at an assumed 500 MB/s sequential read ≈ 40 s
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inYou’ve reached the end
What this chapter was for:
- An index is a second copy of some of your data, sorted for a particular question.
- B-trees update pages in place and favour reads; LSM trees append and merge later and favour writes.
- Every secondary index is maintained on every insert, update and delete that touches it.
- An index on a low-selectivity column is often slower than scanning the table.
- Column order in a composite index decides which queries it can answer.