Compare storing table rows in an unordered heap file, with secondary structures pointing into it, against storing the rows inside the primary-key structure itself (an index-organized or clustered table). What are the tradeoffs?
answer
- heap: unordered, index points at address, extra fetch
- clustered: rows are the primary-key leaves, no fetch
- secondary index stores primary key, costs a second traversal
- random UUID key plus clustered equals page splits
- wide primary key inflates every secondary index
basics
~20 sA heap appends rows wherever there is space, so inserts are cheap and every lookup costs an index probe plus a fetch into the heap. An index-organized table keeps rows sorted inside the primary-key structure, so primary-key lookups and ranges need no extra fetch, but secondary lookups go through the primary key and inserts in random key order cause page splits and reordering.
solid answer
~60 s**Heap file.** Rows sit unordered in pages; each row has a physical address, and every index (including the primary key) is a separate structure mapping key to address. - Inserts go anywhere with free space: cheap, no reordering. - Every index lookup is *probe, then fetch the row from the heap*: one extra random read, unless the index covers the query. - Physical order drifts from any logical order, so a range scan by key becomes scattered heap reads. **Index-organized / clustered.** Rows are the leaves of the primary-key structure, held in key order. - Primary-key point and range lookups return the row with no extra fetch: this is the big win for key-ranged access. - Secondary indexes store the primary key, not a physical address, so a secondary lookup costs a probe plus a full primary-key traversal. - Inserts in random key order (a random UUID primary key) split pages and fragment the structure; sequential keys append cleanly but concentrate contention at the rightmost page. - A wide primary key inflates every secondary index. Choose by access pattern: key-range-dominated reads favour clustering; insert-heavy, many-secondary-index workloads favour heaps.
go deeper
Say a heap stores rows unordered so an index lookup needs an extra fetch, while a clustered table keeps rows sorted by primary key so the lookup ends on the row.
Add the secondary-index difference (primary key instead of address, second traversal) and that insert order matters for the clustered form.
Argue the choice from an access pattern: key-range dominance, secondary-index count, key width, insert key distribution, and the crossover where a heap range scan loses to a full scan.
Treat it as a physical-design decision tied to key design and tenancy: choose the clustering key as the dominant access dimension, size the secondary-index amplification of a wide key, and account for rightmost-page contention at high insert rates.
## Two ways to answer where a row physically lives **Heap organization.** The table is a bag of pages. A new row goes into any page with enough free space; there is no ordering guarantee whatsoever. Indexes are separate structures whose leaf entries hold a key plus a physical row address. The primary key is just another index with a uniqueness constraint. Reading a row through any index means: traverse the index, obtain the address, read that heap page. **Index-organized (clustered) organization.** The primary-key structure *is* the table. Its leaf pages hold the complete rows in primary-key order. There is no separate heap. Secondary indexes cannot store physical addresses reliably, because rows move as the structure splits and rebalances, so they store the primary-key value instead. ## Reads *Primary-key point lookup.* The clustered form wins: the traversal ends on the row itself. The heap form needs one further page read, and that read is random with respect to the index, so it is a cache miss more often than not. *Primary-key range scan.* The clustered form wins decisively. Rows in a key range are physically adjacent, so the scan is sequential and each page read yields many wanted rows. In a heap, the index gives an ordered list of addresses that point all over the file; fetching them is scattered random I/O, so much so that optimizers often abandon the index and scan the whole table instead once the range exceeds a small fraction of rows. This is why a clustered layout is so attractive for access patterns like "all events for this account, ordered by time", where the leading key column is the tenant or account. *Secondary index lookup.* The heap form wins. A secondary index gives an address, one hop to the row. In the clustered form it gives a primary-key value, requiring a full traversal of the primary structure: several page reads instead of one. The gap widens if the primary key is wide, since the secondary index is larger and has more levels. *Covering queries.* Both forms behave the same: if the index holds every column the query needs, there is no fetch at all. ## Writes *Insert.* Heaps are hard to beat. A row goes wherever there is space; the only ordered work is maintaining the indexes. In a clustered table the row must go in its key position. Sequential keys (an increasing identity or a time-ordered identifier) append to the rightmost page cleanly, though this concentrates latch and lock contention at that page, an issue at high insert rates. Random keys, notably random UUID primary keys, insert into arbitrary pages: pages fill, split into two half-full pages, and the structure fragments, inflating size and turning a would-be sequential workload into random writes. This is the single most commonly cited operational failure of clustered layouts. *Update.* Updating a non-key column is comparable in both. Updating the primary key in a clustered table physically relocates the row and rewrites the entry, which is why changing a clustered key is discouraged. In a heap, growing a row beyond its page's free space forces a move, which must be handled either by rewriting index entries or by leaving a forwarding pointer behind. *Delete.* Comparable; both leave space to reclaim, and both must eventually clean index entries. ## Space The clustered form removes the duplication of storing the primary key in both a separate index and the row, which saves space for narrow tables. It gives that back if the primary key is wide, because every secondary index now carries that wide key as its pointer. A 40-byte natural composite primary key with five secondary indexes is a well-known way to double a table's total footprint. Heaps waste space differently: through partially filled pages and, in some engines, through forwarding pointers left by migrated rows. ## How to choose Favour **clustered** when: reads are dominated by primary-key point lookups and ranges; the leading key column matches the dominant access pattern (tenant id, user id, time); the primary key is narrow and insert order is roughly sequential; there are few secondary indexes. Favour **heap** when: the workload is insert-heavy with random keys; there are many secondary indexes and lookups arrive through them; the natural primary key is wide; or no single ordering serves the access patterns, so no clustering choice would win. ## The engine dimension Some engines make one form the only option (rows always live in the primary-key structure), some default to heaps and offer a clustering operation as a one-off reorganisation that decays as rows are updated, and some support both as an explicit table property. The concept transfers; check which model you are on before designing keys, because the same primary-key choice can be harmless in one model and a serious insert bottleneck in the other.
- Why is a random UUID primary key particularly bad in an index-organized table?Because inserts land in arbitrary key positions across the whole structure rather than appending at one end. Pages fill and split into two half-full pages, so the table grows larger than its data warrants and becomes fragmented, and the write pattern is random rather than sequential, defeating both caching and device-friendly sequential I/O. Time-ordered identifiers avoid this by restoring roughly append-only insert order.
- Why do secondary indexes in a clustered table store the primary key rather than a physical address?Because rows move. Page splits, merges and rebalancing in the primary structure relocate rows routinely, and if secondary indexes held physical addresses every one of them would need updating on every split. Storing the primary-key value makes secondary entries immune to relocation, at the cost of a second traversal on lookup and of carrying the key's width in every entry.
- An optimizer switches from an index range scan to a full table scan once a range exceeds a few percent of the rows in a heap table. Why?Because in a heap the index yields addresses scattered across the file, so each qualifying row can cost a separate random page read, while a full scan reads pages sequentially at much higher throughput. Beyond a crossover selectivity the sequential scan is simply cheaper. In a clustered table the crossover barely exists for primary-key ranges, since the rows in the range are already physically adjacent.
saying these in an interview costs you the question
- Claiming a clustered table is always faster because it avoids the heap fetch
- Believing secondary indexes in a clustered table hold physical row addresses
- Ignoring that a wide primary key is duplicated into every secondary index
- Assuming a heap keeps rows in insertion order, so ordering can be relied upon
- Recommending a random UUID primary key for a clustered table with no consideration of split behaviour