Part 131: How Indexes Work: B-Trees & B+Trees Explained

Without an index, searching for a user requires a Full Table Scan—scanning every single disk page one-by-one: $O(N)$ complexity.

1. The B-Tree / B+Tree Data Structure

A B+Tree is a self-balancing search tree data structure: - Root Node: Entry point into the tree. - Branch / Internal Nodes: Contain routing keys guiding searches to child pages. - Leaf Nodes: Hold the indexed values alongside pointers to physical row addresses (TIDs / RowIDs) on disk. - Doubly-Linked Leaves: Leaf nodes are linked horizontally, enabling instantaneous range scans (BETWEEN 10 AND 50).

                 [ Root Page ]
                 ┌─────┴─────┐
          [ Branch ]      [ Branch ]
          ┌───┴───┐        ┌───┴───┐
       [Leaf]  [Leaf]   [Leaf]  [Leaf] (Linked horizontally for fast ranges)

In a table with 100,000,000 rows, a B+Tree is typically only 3 to 4 levels deep. Any single row can be found in just 3 or 4 page reads!

Key Takeaways

• Indexes reduce search complexity from $O(N)$ to $O(\log N)$.
• B+Trees support equality lookups, range queries, and ordered sorting.

In Part 132, we compare Clustered vs Non-Clustered Indexes!