Clustered vs Non-Clustered Index

Clustered Index

The table data is physically sorted and stored in the order of the index key. The index IS the table. Leaf nodes of B+ Tree contain ACTUAL ROW DATA. Only ONE clustered index per table.

Clustered Index on ID:

Leaf Node 1        Leaf Node 2        Leaf Node 3
id=1 | full row --> id=4 | full row --> id=7 | full row
id=2 | full row     id=5 | full row     id=8 | full row
id=3 | full row     id=6 | full row     id=9 | full row

  actual row data lives inside leaf nodes

Non-Clustered Index

A separate structure that stores the key + a pointer back to the actual row. Index is separate from the table. Leaf nodes store key + pointer (RID or primary key). Multiple non-clustered indexes per table.

Non-Clustered Index on Email:

Index B+ Tree              Actual Table (heap)
alice@ --> ptr ---------> id=3, alice@, age=25
bob@   --> ptr ---------> id=1, bob@, age=30
carol@ --> ptr ---------> id=5, carol@, age=22

MySQL InnoDB Specifics

• Primary Key → always clustered index → leaf nodes store full row data
• Secondary Keys → non-clustered → leaf nodes store the PRIMARY KEY (not row ptr)
• SELECT via secondary index → Two B+ Tree traversals! (secondary index → PK → clustered index)

Tip: This is why choosing a small primary key (int vs UUID) matters in MySQL — every secondary index stores it.

Covering Index — Avoiding Double Lookup

-- Query only needs id and email
SELECT id, email FROM users WHERE email = 'bob@gmail.com'
-- If index is on (email, id) → index already has both columns
-- No need to go back to the table at all!
-- Called a "covering index"

Covering Index — How One Lookup Works

Covering index leaf nodes DO still store the pointer — but the pointer is NEVER FOLLOWED because all needed columns are already in the leaf node itself. The table is never accessed, which is what makes it a single-structure lookup.

Normal non-clustered leaf node:
| user_id = 5 | ptr → row |   <-- must follow ptr (disk read)

Covering index leaf node:
| user_id = 5 | status = active | amount = 500 | ptr |
                                                  ^-- exists but IGNORED
  everything already here -- ptr never followed

Covering Index is a Non-Clustered Index

A covering index is NOT a separate index type. It's a PROPERTY of an index relative to a query. The same index can be covering for one query and non-covering for another.

	Clustered	Non-Clustered	Covering Index
Data storage	Inside leaf nodes	Separate	Separate (+ extra cols)
Per table	One only	Many	Many
Table access needed	Never	Yes	No (for covered queries)
Role/Type	Type	Type	Role (not a type)