Explain the difference between a table whose rows are stored in a clustered (index-organized) structure and a table stored as a heap, and how each locates a row.
answer
- Heap: unordered pages + physical row id
- Clustered: table IS the B+tree, rows in leaves
- Clustered PK lookup = no extra fetch
- Secondary under clustering stores the clustering key, not an address
- One clustering order per table only
basics
~20 sIn clustered storage the table IS the index: rows live in the leaves of a B+tree ordered by the clustering key. In a heap, rows sit in unordered pages and are addressed by a physical row id, with every index a separate structure pointing at those ids.
solid answer
~60 s**Heap storage:** rows are written wherever there is free space, in no particular order. Each row has a physical **row identifier** (file/page/slot). Every index — including the primary key index — is a separate B+tree whose leaves hold key values plus those row ids. Finding a row means: descend the index, get the row id, then read that table page directly. **Clustered / index-organized storage:** the table has no separate existence; rows are stored *inside the leaf pages of a B+tree keyed by the clustering key* (usually the primary key), so the table is physically ordered by that key. A primary-key lookup descends the tree and the row is right there — no second fetch. Secondary indexes cannot store a physical address, because rows move as pages split; they store the clustering key instead, so a secondary lookup descends the secondary tree and then descends the clustered tree again. The tradeoff: clustered storage makes key-ordered access and PK lookups very cheap, heap storage makes every index symmetric and keeps row addresses stable.
code
text · 8 linesHEAP
table pages : [row][row][row] (unordered) <- addressed by rid(page,slot)
pk index : leaf: key -> rid
sec index : leaf: col -> rid
CLUSTERED
clustered tree leaf : key -> FULL ROW (table is the tree)
sec index leaf : col -> clustering key -> re-descend clustered treego deeper
State the core difference — rows in key order inside the tree versus unordered pages with row ids — and that a PK lookup on a clustered table needs no extra row fetch.
Add the secondary-index consequence: the clustering key is stored as the row reference, so secondary lookups take two descents and a wide key inflates every index.
Discuss which workloads favour which model — range locality and PK-dominant access versus multi-column access, wide keys and random inserts — and heap forwarding pointers as the counterpart maintenance issue.
Treat it as a schema-level design decision: one physical ordering per table, its interaction with key choice, write patterns and cache locality, and how it changes as access patterns evolve.
## The two storage models A relational engine has to decide where the actual row bytes live. There are two answers in wide use. **Heap.** The table is an unordered collection of pages. An inserted row goes into any page with enough free space; there is no relationship between key value and physical position. Each row is identified by a **row identifier** — conceptually (file, page number, slot number) — that names its physical location. Indexes are entirely separate B+trees; each leaf entry pairs a key value with a row id. The primary key index is just one more index, structurally identical to the others. **Clustered / index-organized.** The table is stored *as* a B+tree keyed by the clustering key, and the full row lives in the leaf pages of that tree. Rows are therefore in key order. There is no separate heap file — the tree is the table. ## How a lookup differs **Heap, lookup by any indexed column:** descend that index (a few page accesses) → read the row id from the leaf → fetch that exact table page → read the row. Every index costs the same shape of work. The row id is a direct address, so the fetch is a single page read. **Clustered, lookup by clustering key:** descend the tree → the row is in the leaf you landed on. No second fetch at all. This is the model's headline advantage. **Clustered, lookup by a secondary index:** the secondary index cannot store a physical address, because rows physically move when leaf pages split or reorganize; a stored address would be invalidated constantly. So secondary leaves store the **clustering key** as the row reference. A lookup therefore descends the secondary tree to get the clustering key, then descends the clustered tree to reach the row — two traversals instead of one traversal plus one page fetch. ## What each model is good at **Clustered storage wins when:** - Access is dominated by the clustering key — point lookups and, especially, ranges ("all rows for this customer", "orders in this date window"). Because rows are in key order, a range is a sequential leaf walk that returns whole rows, with excellent locality. - You want output already sorted by the key without a sort step. - You want to avoid the extra row fetch on your hottest access path. **Heap storage wins when:** - Access is spread across many different columns, so no single ordering helps and you would rather every index be equally cheap. - The primary key is wide, since a wide clustering key is embedded in every secondary index under the clustered model. - Insert patterns are random with respect to the key, since clustered storage forces every insert into its ordered position, causing page splits and fragmentation, while a heap simply appends to free space. - You want stable row addresses, which simplifies index maintenance. ## The consequences you should be able to name 1. **Only one clustering order is possible per table.** Physical order is a single choice; you cannot cluster on both customer and date. Choosing it is a real design decision about which access pattern gets the locality. 2. **The clustering key propagates.** Every secondary index carries it as the row reference, so its width multiplies across all indexes. 3. **Secondary lookups cost more under clustering.** Two descents instead of one descent plus a direct fetch. 4. **Insert order matters much more under clustering.** Rows must land in key position, so a key that increases monotonically appends to the rightmost pages, while a random key scatters inserts across the whole tree, dirtying many pages and splitting them. 5. **Heaps have their own maintenance issue.** When an updated row no longer fits in its page, engines may relocate it and leave a forwarding pointer behind, so a lookup follows an extra hop until the table is reorganized. ## The distinction candidates most often blur "Clustered index" is a statement about **where the rows physically live**, not merely about an index being sorted. Every B+tree index is sorted in its own leaves. What makes an index clustered is that the table's rows *are* its leaf payload — so there is exactly one, and it determines the table's physical order. ## Saying it in one breath "A heap stores rows in unordered pages addressed by a physical row id, and every index — including the PK — points at those ids. A clustered table stores the rows inside the leaves of a B+tree on the clustering key, so the table is physically ordered by that key: PK lookups need no row fetch and key-ordered ranges are sequential, but secondary lookups need a second descent and the clustering key is embedded in every secondary index."
- Why can't a secondary index in a clustered table just store a physical row address?Because rows physically move. Inserting into an ordered structure splits leaf pages and relocates rows, and any stored physical address would be invalidated by every split, requiring updates to every secondary index that referenced the moved rows. Storing the clustering key instead is a logical reference that survives relocation, at the price of a second tree descent per secondary lookup.
- How many clustered indexes can a table have, and why?At most one, because clustering defines the physical order of the rows themselves and a set of rows can only be laid out in one order. Additional indexes must be secondary structures that reference rows rather than contain them. This is why choosing the clustering key is a design decision about which single access pattern gets physical locality.
- What happens in a heap when an updated row grows and no longer fits on its page?The engine typically relocates the row to a page with room and leaves a forwarding pointer at the original location, so existing index entries pointing at the old row id still resolve. Lookups then pay an extra hop through the forwarding pointer. Accumulated forwarding is a known heap-fragmentation symptom that a table reorganization clears up.
A heap is a warehouse with a location code for every carton; a clustered table is a shelf where the goods themselves are arranged alphabetically — walking a range is easy, but re-sorting is the whole shelf.
saying these in an interview costs you the question
- Saying a clustered index is just an index that happens to be sorted — all B+tree indexes are sorted in their leaves
- Claiming a table can have several clustered indexes
- Believing clustered storage keeps a separate copy of the table alongside the tree
- Thinking secondary lookups are equally cheap in both models
- Assuming heap tables have no primary key index — they do, it is simply a separate structure like any other