Notesstorage🌱 seedling
Clustered Index
Also: Clustered Indexes · Index-Organized Table · Clustered Primary Key · Heap Table
A table stored inside its primary-key [[B-Tree]], with full rows in the leaves, so the rows are physically ordered by key. Its alternative is a heap table, where rows sit unordered and every index, primary key included, points at a physical location.
Why it exists
Where the row lives decides how lookups and updates cost. Putting the row in the primary-key index makes primary-key reads and range scans one tree walk, and keeps secondary indexes stable when rows change.
How it works
- Clustered (InnoDB, SQL Server): one B-tree keyed by primary key holds the rows. Secondary Index entries store the primary key, so a secondary lookup walks two trees.
- InnoDB clusters on the primary key, else the first unique non-null index, else a hidden 6-byte row ID.
- Heap (Postgres): rows in an unordered heap; all indexes are secondary and store a tuple ID (page, item).
- In Postgres an update writes a new row version at a new location, so every index needs a new entry, unless it's a HOT update: no indexed column changed and the new version fits on the same page.
Trade-offs
| Clustered | Heap | |
|---|---|---|
| PK lookup and PK range scan | fastest: row is in the leaf | index walk + heap fetch |
| Secondary lookup | two tree walks | one index walk + one fetch |
| Update to a non-indexed column | secondaries untouched | every index updated unless HOT |
| Wide or random PK | bloats every secondary; random inserts split pages | little effect |
In practice
- Uber (2016) moved a large workload from Postgres to MySQL largely over this: updates rewrote entries in every index, and physical WAL replication shipped all of it between data centres.
- PostgreSQL has narrowed the gap with HOT updates, a lower table
fillfactorto leave room for them, and bottom-up index deletion (v14) to clear version churn.
Pitfalls
- UUIDv4 primary keys in a clustered table scatter inserts across all leaves; prefer sequential or time-ordered (UUIDv7) keys.
- Postgres's
CLUSTERcommand reorders a heap once; it is not maintained as rows change.
Connections
- Part of
- Storage
- In real systems
- MySQLPostgreSQL
Recall
These cards are also in your review deck, scheduled with spaced repetition.