Database Index

A database index is a data structure that accelerates query performance by maintaining sorted pointers to table rows, enabling the database to locate data without scanning every row. Without an index on a column, finding all users named 'Alice' requires examining every row in the table (a full table scan).

With a B-tree index on the name column, the database traverses a balanced tree structure directly to 'Alice' entries, typically examining only log(n) entries instead of n. The speedup on large tables is dramatic: milliseconds instead of minutes. Indexes have costs. They consume storage space, often 10-20% of the table size per index.

They slow write operations because every INSERT, UPDATE, or DELETE must update not just the table but also all relevant indexes. Over-indexing a heavily written table can significantly degrade write performance.

Index types serve different purposes: B-tree indexes handle equality and range queries; hash indexes excel at exact matches; GiST and GIN indexes support full-text search and geometric data; partial indexes cover only rows matching a condition. Composite indexes span multiple columns, supporting queries filtering on combinations.

Covering indexes include all columns a query needs, eliminating table lookups entirely.