Databases
Indexes
Auxiliary structures (usually B-trees) that let the database find rows without scanning the whole table, turning linear lookups into logarithmic ones — critical for WHERE, JOIN and ORDER BY on large tables. The cost: every index slows writes and consumes space, and the planner will ignore an index if you wrap the column in a function.
Purpose
An index is an auxiliary structure — usually a B-tree — that lets the database locate rows without scanning the whole table, turning O(n) lookups into O(log n). It is the single most important tool for query performance on any table that grows.
When to Use It
Index the columns your queries actually filter, join and sort on: foreign keys, lookup fields, sort orders. Composite indexes serve multi-column predicates (leftmost-prefix rule); specialised types — like PostgreSQL's GIN for full-text or trigram search — cover cases B-trees cannot.
Trade-offs
Every index must be updated on every write, so each one taxes inserts and updates and consumes storage. Indexes also go unused if the query defeats them — wrapping the column in a function, mismatched types, or a leading wildcard LIKE '%…' — so more indexes is not automatically better.
Implementation
Find slow queries via the database's statistics, then check with EXPLAIN whether they scan or seek. Add the narrowest index that serves the predicate, order composite columns by selectivity and usage, and periodically drop indexes the planner never touches.