Indexing
How B+tree, hash, composite and covering indexes speed up reads, what they cost on writes, and where LSM trees and inverted indexes fit.
What an index is
Without help, finding rows with user_id = 42 means reading the whole table. That is a full table scan: cost grows with table size.
An index is a second, smaller structure kept sorted (or hashed) by one or more columns. It maps a column value to the location of the row. The idea is the same as the index at the back of a book.
- Reads that match the index get much faster.
- Every write now has extra work to keep the index current.
- The index uses disk and memory.
1 of 9