Database Indexing

An index is a separate data structure that allows the database engine to find rows matching a condition without scanning every row in the table. A well-placed index can reduce a query from seconds to milliseconds. A poorly placed one wastes disk space and slows down writes. Understanding how indexes work is one of the highest-leverage skills for a backend engineer.

Why Indexes Exist: The Full Table Scan

Without an index, a query like SELECT * FROM orders WHERE customer_id = 42 requires a full table scan (also called a sequential scan or Seq Scan in Postgres): the engine reads every row, evaluates the condition, and returns matching rows. For a table with 100 million rows, this is catastrophically slow.

An index pre-sorts or pre-hashes a column's values and stores pointers back to the rows, allowing the engine to jump directly to matching rows.

B-Tree Indexes (the default)

The B-tree (balanced tree) is the default index type in PostgreSQL, MySQL, and most relational databases. It is a self-balancing tree where each node contains sorted key values and pointers to child nodes or data pages.

                    [30 | 60]
                   /    |    \
            [10|20]  [40|50]  [70|80]
             / |  \   ...       ...
           rows rows rows

Properties:

• Supports =, <, >, <=, >=, BETWEEN, LIKE 'prefix%' queries.
• All leaf nodes are at the same depth (balanced), so lookup time is always O(log N).
• Range scans are efficient: the tree is traversed once to find the start, then leaves are scanned in order.
• Does not support LIKE '%suffix' (middle wildcard) because the index is sorted by prefix.

PostgreSQL B-tree internals:

• Leaf pages contain the indexed value + heap tuple pointer (page number + offset).
• The index does not store the full row — after finding the heap pointer, Postgres must fetch the actual row from the table heap (unless a covering index is used — see below).