1. Index

A separate data structure:

• Stores column value
• Plus a pointer to the actual row location
• Speed up queries, helps:
  • WHERE
  • JOIN
  • ORDER BY
  • GROUP BY
• Too much indexes causing slower writes, every write must:
  1. Insert/update table
  2. Update every affected index
  3. Rebalance B+ Tree if needed
• Do NOT use index if

  • Column has less data options, like only MALE / FEMALE

    • Optimizer may prefer full table scan
    • Still be indexed when combined in composite index

  • WHERE function(column) = ...

    • Example: WHERE YEAR(created_at) = 2025
    • Index not used because:
      • Index is on created_at
      • DB must compute YEAR() for every row

  • Leading % in LIKE

    • B+ Tree is ordered from the start
    • %abc has no known prefix → cannot navigate tree

    LIKE '%abc'   ❌ no index
    LIKE 'abc%'   ✅ index usable
    

B+ Tree

• Supports: =,<, >, ORDER BY, LIKE 'abc%'
• Balanced → tree height is small
• All actual data pointers are in leaf nodes
• Leaf nodes are linked (for fast range scan)

// Example of index on email:
                [m@]
              /       \
        [f@]             [t@]
       /    \           /     \
 [a@][c@][e@]     [n@][r@][z@]

• Behind the scenes:

  SELECT * FROM users WHERE email = '[email protected]';
  

  1. Optimizer checks available indexes
  2. Chooses idx_email
  3. Traverses B+ Tree:
     • Root → internal → leaf
  4. Finds matching key
  5. Uses row pointer to fetch actual row

Clustered vs Secondary Index

Clustered Index (InnoDB primary key)