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 fillfactor to 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 CLUSTER command reorders a heap once; it is not maintained as rows change.

Recall

These cards are also in your review deck, scheduled with spaced repetition.