Database Indexes — Speeding Up Reads

Without an index, the database performs a full table scan — reading every row to find matches. For a 100M-row table, this reads gigabytes of data. An index is a separate data structure (typically a B-tree) that stores the indexed column values sorted, with pointers to the row locations. With an index, the DB finds matching rows in O(log N) time instead of O(N).

Analogy: a book's index at the back vs reading every page. The index trades write overhead and storage for dramatically faster reads.

The most common index type in relational databases (MySQL InnoDB, PostgreSQL). A balanced tree where leaf nodes contain the indexed value and a pointer (row_id or primary key) to the actual data row.

Properties: sorted order supports range queries (BETWEEN, <, >). O(log N) lookup, insert, and delete. Works well for cardinality from 2 (boolean) to millions (user_id). InnoDB's clustered index stores the full row in the leaf node — the primary key is always the clustered index. Secondary indexes store the primary key in the leaf, then a second lookup fetches the row.

A composite index covers multiple columns: INDEX(last_name, first_name, age). This index can satisfy queries filtering on: last_name only, last_name + first_name, or all three columns. It cannot efficiently satisfy queries filtering on first_name only (because the index is sorted by last_name first).

Rule: put the most selective column (highest cardinality, most rows filtered) first. Put columns used in WHERE before columns used in ORDER BY. The leftmost prefix rule: a query must use a prefix of the composite index to benefit.

Covering index: an index that includes all columns needed by a query, so the DB never needs to fetch the actual row. Very fast — no secondary lookup needed. CREATE INDEX idx ON orders (user_id, status, total) covers SELECT status, total FROM orders WHERE user_id = 123.

Every INSERT, UPDATE, and DELETE must also update all indexes on that table. A table with 5 indexes requires 5 index writes per row insert. For write-heavy workloads (time-series, event logs, message queues), excessive indexes degrade write throughput significantly.

Index maintenance is why wide tables (many columns) with many indexes are problematic — every column update requires index updates even if the indexed value didn't change (because the DB doesn't know which columns changed without reading the index).

Guidelines: only index columns that appear in WHERE, JOIN, or ORDER BY clauses of frequently-run queries. Remove indexes that are never used (database query plan statistics show index usage). For write-heavy analytics tables, prefer batch bulk inserts and build indexes afterward.

Hash index: exact-match lookups only, no range queries. Faster than B-tree for equality (O(1)). Used by Memcached, hash indexes in PostgreSQL. Not useful for ORDER BY or BETWEEN.

Full-text index: tokenizes text columns (like tweet content) for keyword search. MySQL FULLTEXT index, PostgreSQL tsvector. Uses inverted index under the hood. Much faster than LIKE '%keyword%' which cannot use B-tree indexes.

Bitmap index: stores one bit per row per distinct value. Highly compressed for low-cardinality columns (gender: M/F, status: active/inactive). Used in data warehouses (Oracle, Redshift). Terrible for high-cardinality columns or OLTP (high write rates).

Partial index: only indexes rows matching a condition. CREATE INDEX idx ON orders (created_at) WHERE status = 'pending'. Smaller, faster than a full index. Useful when queries always filter on a constant value.