Why a Database Index Makes Queries Fast

Without an index

For WHERE email = ? without an index, the database scans every row. At scale that is a disaster. An index is a directory for the column, taking lookup from O(n) to O(log n).

B+tree index

Most relational indexes are B+trees: ordered, short and wide, with linked leaves. Equality seeks down the tree; range scans read along the leaf chain -- both fast.

Two key points

1. Return to table: a secondary index stores only the indexed columns and the primary key; you then look up the rest in the main table. A covering index (it already has the needed columns) avoids this;
2. Leftmost prefix: a composite index (a, b, c) is used from the left only, so WHERE b = ? cannot use it.

More is not always better

• Slower writes: every insert or update maintains the index;
• Space: indexes are data too;
• Wrong column: a low-cardinality column like gender gains almost nothing.