Database Indexing

What an Index Does

An index is a separate data structure that maps column values to the physical locations of rows. Without an index, the database must perform a sequential scan (full table scan), reading every row to find matches. With an index, the database navigates a much smaller structure to locate rows directly.

B-tree Structure

The default index in PostgreSQL and MySQL (InnoDB) is a B-tree -- a balanced, sorted tree where the root node contains boundary keys and pointers to child nodes, internal nodes narrow the search range at each level, and leaf nodes hold the indexed values paired with pointers to the actual table rows. Leaf nodes are linked in order, so range scans walk the leaf chain without returning to upper levels.

A lookup traverses from root to leaf in O(log n) steps. For a table with 10 million rows, a B-tree typically requires 3-4 page reads to locate a single value.

How a Lookup Works

1. The query planner determines that an index is useful for the query.
2. The database reads the root page and follows pointers through internal pages based on comparison with search keys.
3. It reaches a leaf page containing the target value and a pointer to the heap (table row).
4. It fetches the row from the heap (unless the index covers all required columns).