Clustered vs Unclustered Indexes

An index maps search-key values to the locations of matching rows. But "location" can mean two very different things depending on how the underlying table is organized. A clustered index (also called a clustering index or, in index-organized tables, the index is the table) is built over a file whose rows are physically sorted by the index's search key — or, equivalently, the index directly determines row placement. Consequently, rows with adjacent key values live on the same or physically adjacent disk pages. An unclustered index (also called a secondary or non-clustering index) is built over the same sorted or heap file but on a different key, or on the same key when the file's true physical order is something else entirely. Its leaf entries store key values paired with row identifiers (RIDs) — pointers to wherever the corresponding row physically resides. Because the table can only be sorted one way, at most one index per table can be the clustered index; every other index on that table is necessarily unclustered. The crucial vocabulary: a RID (record identifier, e.g., page-number + slot-number) is the physical address used by all indexes, clustered or not, to reach the actual row once the index has narrowed the search to a key or key range. In a clustered index, consecutive RIDs in key order tend to fall in the same page, so a range of keys maps to a contiguous run of pages. In an unclustered index, consecutive RIDs in key order are scattered across the file with no relationship to physical page boundaries, so a range of keys maps to a scattered set of pages — potentially one page fetch per matching row. This single structural fact — sequential runs versus scattered scans — is the entire story behind why clustering matters so much for range queries and comparatively little for point queries.

Building a clustered index. The table's rows are stored, and maintained, in sorted order by the chosen search key. This is typically implemented as a sorted (or B+-tree-organized) file: the leaf level of the index is the data file, or the data file is kept sorted and the index is a sparse structure with one entry per data page (since consecutive keys share a page, you don't need an entry per row). Insertions must go to the correct sorted position, which may require shifting rows within a page or splitting a page — more expensive than an unclustered insert, but the tradeoff buys sequential range scans forever after.

Building an unclustered index. The index is a dense B+-tree (or hash structure) whose leaves list every search-key value paired with the RID of the matching row, wherever that row happens to physically sit. Insertions are cheap — append a leaf entry, no need to move any table row — but nothing links keys that are numerically close to pages that are physically close.

Point lookup, either type. Traverse the index from root to leaf ($O(\log_B N)$ node fetches for a B+-tree of fan-out $B$), then fetch the one page holding the row. Cost is nearly identical for clustered and unclustered indexes: a few index-page I/Os plus one data-page I/O.

Range lookup — the divergence. Traverse the index to find the start of the range, then:

• Clustered: walk forward through the sorted leaf/data pages, which are contiguous or nearly so on disk. Each page yields many qualifying rows, so I/O cost scales with the number of pages touched.
• Unclustered: walk forward through leaf entries, but for each entry follow the RID to a (likely different) data page. Without further optimization, I/O cost scales with the number of rows touched, since consecutive leaf entries can point to arbitrary, non-adjacent pages.

Below is language-agnostic pseudocode for the two range-scan procedures, made explicit so the I/O pattern is visible. ``` // CLUSTERED range scan: index leaves ARE (or point densely into) sorted data pages function clusteredRangeScan(index, keyLow, keyHigh): leafPage = index.findLeafContaining(keyLow) // O(log_B N) I/Os, tree traversal result = [] page = leafPage while page != null: for row in page.rowsInKeyOrder(): if row.key > keyHigh: return result if row.key >= keyLow: result.append(row) page = page.nextPageInPhysicalOrder() // sequential fetch, 1 I/O return result // UNCLUSTERED range scan: leaves are dense, RIDs point to scattered data pages function unclusteredRangeScan(index, keyLow, keyHigh): leafEntry = index.findLeafContaining(keyLow) // O(log_B N) I/Os result = [] entry = leafEntry while entry != null and entry.key <= keyHigh: row = fetchPageAndSlot(entry.rid) // possibly 1 random I/O EACH time result.append(row) entry = entry.nextLeafEntry() return result ``` A key optimization for the unclustered case, when the result set is large, is index-only evaluation (if the query needs only indexed columns) or sorting the retrieved RIDs by page number before dereferencing them, converting many random fetches into fewer, batched sequential-ish fetches. This is exactly the trick used by bitmap-index-assisted scans and by "RID sort" strategies in real query engines — it doesn't eliminate the asymptotic gap but shrinks the constant factor by exploiting the buffer pool.

Index traversal cost. For a B+-tree with fan-out $B$ (number of children per internal node) over $N$ rows, the height is $\Theta(\log_B N)$, so locating the first qualifying leaf costs $O(\log_B N)$ I/Os regardless of clustering — this part is identical for both index types, and with $B$ typically in the hundreds, this is effectively 2–4 I/Os even for huge tables.

Range scan, clustered case. Let $M$ be the number of data pages that hold matching rows and $r$ be rows per page. Because matching rows are packed contiguously (or nearly so — clustered files are usually not perfectly compact but close, and periodic reorganization keeps them so), the scan touches

page fetches, and because the pages are contiguous on disk most storage systems can prefetch them sequentially, multiplying effective throughput by a large constant (sequential I/O is often 10–40× faster in raw bandwidth than random I/O on spinning disks, and still meaningfully faster on SSDs due to fewer, larger requests and better prefetch behavior).

Range scan, unclustered case. In the worst case, no two matching rows share a page, so the cost is

one random-ish page fetch per row. Even in the best case, where the underlying heap happens to co-locate a few matching rows per page by coincidence, there is no guarantee of this — the unclustered index carries no information that would make it likely.

Why this asymptotic gap is real, not just a constant-factor annoyance. The formulas above are not merely worst-case bogeymen: for typical uses (e.g., "all orders in the last 30 days" from a table clustered by date) matching rows genuinely span a small, contiguous page range, giving $M \ll |\text{result}|$. For an unclustered index (e.g., an index on `customer_id` for a table physically ordered by `order_date`), rows for one customer are smeared across the entire table's history, so $M \approx |\text{result}|$ for large enough result sets — a linear factor of $r$ (rows per page, commonly tens to hundreds) difference in I/O count, which dominates total query time.

Correctness invariant. Both index types must satisfy the basic index-correctness invariant: every row with key $k$ is discoverable by a lookup on $k$, and the traversal never misses or duplicates rows. What clustering changes is not correctness but cost — it is purely a physical data-organization decision layered on top of a correct search structure. This is why the choice is orthogonal to the tree/hash structure of the index itself and belongs to physical database design, alongside topics like Index Selection.

Tradeoffs. Clustering isn't free: maintaining sort order on inserts/updates can require page splits, migrated rows, and more expensive writes (especially with "hot" insert keys, e.g., always inserting at the end causes contention, or inserting mid-file causes cascading splits). This is why systems often prefer a clustering key that is monotonically increasing (like an auto-increment ID or timestamp) to keep insertions append-only and cheap, even though this may not match the most common query pattern — an example of the recurring key-selection tension addressed in Index Selection.

Consider a table `Orders` with $N = 1{,}000{,}000$ rows, $r = 100$ rows per data page (so $10{,}000$ data pages), and a B+-tree fan-out of $B = 100$ giving tree height $\lceil \log_{100} 1{,}000{,}000 \rceil = 3$. Suppose we ask: "Return all orders placed in March 2024," and March 2024 accounts for 50,000 rows (5% of the table).

Case A — clustered index on `order_date`. Rows are physically sorted by date, so March's 50,000 rows occupy $\lceil 50{,}000/100 \rceil = 500$ contiguous data pages.

Case B — unclustered index on `order_date`, table physically ordered by `order_id` (insertion order). The same 50,000 rows are scattered essentially uniformly across all 10,000 data pages, because order IDs and order dates are only loosely correlated at this granularity (many customers, many concurrent orders). Assume, pessimistically but realistically, that almost every matching row lands on a distinct page (birthday-paradox-style collisions are rare when 50,000 rows are drawn against 10,000 pages with ~100 slots each — actually here rows will collide, but each colliding page still needs a fetch, and dereferencing is not sorted by page, so the buffer pool cannot exploit locality without an extra sort step).

Even after accounting for some buffer-pool reuse (a few matching rows do land on the same page, and hot pages might already be cached), Case B is roughly two orders of magnitude more page fetches than Case A, and each of those fetches is a random access rather than a cheap sequential one — compounding the gap further in wall-clock time. This is precisely why query optimizers assign a much higher cost to using an unclustered index once the estimated result size crosses roughly 5–10% of the table (a common optimizer heuristic), often falling back to a full sequential heap scan (10,000 sequential I/Os) instead — which, notice, would actually beat the unclustered index plan in this example.

The clustered/unclustered distinction emerged directly from early work on file organization and access methods for the relational model, once it became clear that logical query languages needed to be decoupled from physical storage decisions — the very separation that let optimizers choose access paths automatically.

Every major relational database engine exposes this distinction, though the terminology varies. SQL Server and Sybase use "CLUSTERED INDEX" explicitly as a `CREATE INDEX` option. MySQL's InnoDB storage engine always organizes a table as a clustered index on the primary key (an index-organized table), meaning secondary indexes there are inherently unclustered and store the primary key as their "RID." Oracle offers both heap-organized tables (all indexes unclustered) and index-organized tables (primary key acts as a clustered structure), plus a separate feature literally called a "cluster" for co-locating related tables. PostgreSQL takes a hybrid approach: it supports a one-time `CLUSTER` command that physically reorders a heap according to an index, but does not maintain that order automatically on subsequent inserts, illustrating the real engineering cost of keeping a table clustered over time. Data warehouses and analytics engines lean on the same principle at a coarser grain: columnar formats, partitioning, and sort keys (e.g., Redshift's `SORTKEY`, Snowflake's clustering keys, BigQuery's clustered tables) are essentially clustered indexes generalized to whole columns or partitions, chosen specifically so that range and equality filters on the sort key prune most of the data with sequential reads. Log-structured merge trees in systems like Cassandra and RocksDB achieve clustering implicitly by sorting each on-disk segment by key, trading write amplification for read locality. Understanding when to pay for clustering — and on which column — is the central question of Index Selection, and the same tension between key order and physical layout reappears, in higher-dimensional form, in Multidimensional Indexes like R-trees and space-filling curves.

Ask the tutor: How does a query optimizer decide the selectivity threshold at which it abandons an unclustered index in favor of a full table scan?