Index Types (Clustered, Non-Clustered, Composite, Covering)

Understanding the physical layout of indexes is crucial for eliminating query latency bottlenecks:

1. Clustered Index (Table IS the Index)

• In a Clustered Index (default Primary Key in MySQL InnoDB, SQL Server), the leaf pages of the B+ Tree contain the actual physical row data (all columns).
• Because physical disk blocks can only be sorted in one physical order, there can be only ONE Clustered Index per table.
• Advantage: A Primary Key point lookup (WHERE id = 1042) reaches the leaf node and immediately has all columns in hand with zero additional disk lookups.

2. Non-Clustered (Secondary) Index

• A Secondary Index is an auxiliary B+ Tree created on non-primary columns (e.g., CREATE INDEX idx_email ON users(email)).
• The leaf nodes of a secondary index do not contain full row data. In MySQL InnoDB, secondary index leaf nodes store the Primary Key value; in PostgreSQL, they store a Tuple ID (TID / Block Pointer) pointing to the row in the heap table file.
• The Double-Lookup Penalty: Searching by email requires two sequential index lookups:
  1. Traverse the email B+ Tree to find the Primary Key (id: 1042).
  2. Traverse the Clustered Primary Key B+ Tree (or Heap File) to fetch the actual row columns (name, balance, created_at).