Database Indexing: How It Works

A database index is a data structure that speeds up data retrieval. Without an index, the database reads every row in the table. This is called a full table scan, and it is slow on large tables.

Think of a phone directory. Finding someone by name is fast because the names are sorted alphabetically. Finding someone by address requires scanning every entry. An index creates that sorted shortcut for your database queries.

Key sources: PostgreSQL documentation on indexing, "Database Internals" by Alex Petrov.

How Indexes Work

The most common index type is a B-tree (balanced tree). It organizes data in a sorted structure where finding any value takes O(log n) lookups. A table with 10 million rows needs about 24 comparisons to find any row via a B-tree index.

An index on a column allows the database to jump directly to the relevant rows instead of scanning everything.

-- Without index: sequential scan, slow on large tables
SELECT * FROM orders WHERE customer_id = 42;

-- Create index
CREATE INDEX idx_orders_customer ON orders(customer_id);

-- With index: fast lookup
SELECT * FROM orders WHERE customer_id = 42;

Types of Indexes

B-tree: The default. Good for equality lookups, range queries, and sorting.

Composite: An index on multiple columns. Column order matters. The most selective column should come first.

Partial: Only indexes a subset of rows. Smaller and faster for targeted queries.

Covering: Contains all columns a query needs. The database answers the query entirely from the index without touching the table.

Common Pitfalls

Indexes speed up reads but slow down writes. Every INSERT, UPDATE, or DELETE must update every relevant index. A table with 10 indexes is 10 times slower to write to.

Do not index low-cardinality columns. A boolean column (true/false) splits data into two groups. An index does not help much because the database still reads half the table.

Measure before indexing. Profile your slow queries and index accordingly.

Key Takeaways

1. Indexes turn full table scans into quick lookups but add write overhead.
2. Composite indexes should order columns by selectivity.
3. Partial and covering indexes optimize specific query patterns.
4. Do not over-index. Profile first, then add indexes for identified slow queries.