Clustered vs Non-Clustered Indexes
Non-Clustered Index
Read aloud is unavailable in this browser.
The Index That Points to Data
Consider the index at the back of a textbook. It lists topics alphabetically with page numbers, but the book's pages themselves are organized by chapter, not by the index's alphabetical order. To find information about 'Binary Trees,' you look up 'B' in the index, find the page number, and then flip to that page. The index and the content exist as separate structures.
This is precisely how a non-clustered index works in database systems. Unlike a clustered index where the index IS the data, a non-clustered index is a separate structure that contains key values paired with pointers (locators, row IDs) to the actual data rows. The data itself remains stored in its own order—either according to a clustered index or in an unordered heap.
Non-clustered indexes are the workhorses of database query optimization. A table can have dozens of them, each optimized for different query patterns. Understanding their structure, mechanics, and trade-offs is essential for effective database design and query tuning.
By the end of this page, you will understand the precise structure of non-clustered indexes, how they locate data through row locators, the mechanics of bookmark lookups, how covering indexes eliminate lookups, and the performance implications across different query patterns.
Definition and Core Concept
A non-clustered index is a B+ tree index structure that is separate from the table data. The leaf level of a non-clustered index contains index key values and row locators (pointers) that identify where the corresponding data rows are stored. The data rows themselves reside in a different structure—either a clustered index's leaf level or a heap.
The Formal Definition:
A non-clustered index is a B+ tree structure where:
- Internal nodes contain index key values and pointers to child nodes (navigation)
- Leaf nodes contain index key values and row locators pointing to the data
- Leaf nodes are linked for range scans within the index
- The data rows exist in a completely separate storage structure
The Row Locator:
The row locator is the mechanism by which non-clustered index entries point to actual data rows. Its form depends on the table's storage structure:
| Table Type | Row Locator Contents | Lookup Process |
|---|---|---|
| Table with Clustered Index | Clustered index key value(s) | Navigate clustered index to find row |
| Heap (No Clustered Index) | Physical row identifier (File:Page:Slot) | Direct access to data page and slot |
| InnoDB (MySQL) | Primary key value | Always traverse primary key index |
The critical difference from clustered indexes: non-clustered index leaves contain row locators, not actual data rows. Finding a row via a non-clustered index always requires an additional step—following the locator to retrieve the actual data.
Understanding the Two-Structure Model:
Consider a table Products with a clustered index on ProductID and a non-clustered index on CategoryID. The two structures exist independently:
Clustered Index Structure:
- B+ tree organized by
ProductID - Leaf pages contain complete product rows
- Physical data storage
Non-Clustered Index on CategoryID:
- Separate B+ tree organized by
CategoryID - Leaf pages contain (
CategoryID,ProductID) pairs ProductIDis the row locator (clustered key)- Must traverse clustered index to get product details
When you query SELECT * FROM Products WHERE CategoryID = 5:
- Navigate non-clustered index to find all entries with
CategoryID = 5 - Extract the
ProductIDvalues (row locators) - For each
ProductID, traverse the clustered index to retrieve the full row
This two-step process is called a bookmark lookup or key lookup.
Internal Structure Analysis
The internal structure of a non-clustered index is remarkably similar to a clustered index—both are B+ trees. The key difference lies in what the leaf nodes contain.
The B+ Tree Organization:
Like clustered indexes, non-clustered indexes use B+ trees for efficient logarithmic lookups:
- Root Page: Entry point for all searches
- Intermediate Pages: Navigate to narrow search space
- Leaf Pages: Contain (key value, row locator) pairs
- Page Links: Leaf pages linked for range scans
Leaf Page Contents:
Each leaf page in a non-clustered index contains multiple index entries. Each entry consists of:
- Index Key Value(s): The column(s) being indexed
- Row Locator: Pointer to the actual data row
- Included Columns (optional): Additional non-key columns stored in the leaf
Example Entry Sizes:
For a non-clustered index on CategoryID (INT) on a table with clustered key ProductID (INT):
- Index key: 4 bytes
- Row locator: 4 bytes
- Entry overhead: ~7-10 bytes
- Total per entry: ~15-18 bytes
With 8KB pages and ~50% usable space after headers/overhead:
- Entries per page: ~220-270
- A 1 million row table: ~4,000 leaf pages
- Index size: ~32 MB
Non-clustered indexes on wide keys (like VARCHAR(100)) or with large row locators (like composite primary keys) consume significantly more space and reduce fanout. Fewer entries per page means taller trees and more I/O per lookup. Keep non-clustered index keys as narrow as possible.
Row Locator Details:
The row locator's structure profoundly impacts non-clustered index behavior:
When the table has a clustered index:
- Row locator = clustered index key values
- This is why clustered key width matters—it's duplicated in every non-clustered index
- Key lookup requires traversing the clustered index (O(log N) additional)
When the table is a heap:
- Row locator = Physical RID (Row Identifier)
- Typically 8 bytes: FileID (2) + PageID (4) + SlotNumber (2)
- Direct physical access—no tree traversal needed
- BUT: Page splits can invalidate RIDs, requiring forwarding pointers
Trade-off:
- Heaps have faster individual lookups (direct RID access)
- Clustered tables have more stable row locators (logical keys vs physical addresses)
- Clustered tables avoid forwarding pointer chains after row movements
Bookmark Lookup Mechanics
The bookmark lookup (also called key lookup or RID lookup) is the operation that retrieves actual data rows after finding entries in a non-clustered index. Understanding this operation is crucial because it's often the performance bottleneck in query execution.
The Bookmark Lookup Process:
- •Navigate Non-Clustered Index: Traverse from root to leaf to find matching key values
- •Extract Row Locators: Collect the row locators (clustered keys or RIDs) for all matching entries
- •For Each Row Locator: Navigate to the data structure to retrieve the full row
- •Retrieve Required Columns: Extract the columns needed by the query from the data row
- •Return Results: Combine indexed values with retrieved values for the result set
The Performance Problem:
Bookmark lookups are expensive because they involve random I/O. Consider a query that finds 1,000 matching rows via a non-clustered index:
- Non-clustered index scan: Sequential I/O through a few index leaf pages
- Bookmark lookups: 1,000 separate seeks into the data structure
- Each lookup potentially hits a different data page
- Even with caching, this can mean hundreds of disk I/Os
Cost Analysis Example:
Table: 10 million rows, 1 million pages of data, 10,000 rows match the query
| Access Method | Index Navigation | Data Access | Total I/Os | Notes |
|---|---|---|---|---|
| Non-clustered + Lookups | ~50 pages | ~10,000 pages (worst) | ~10,050 | Random I/O for lookups |
| Clustered Index Scan | N/A | ~100 pages (if clustered) | ~100 | Sequential I/O |
| Full Table Scan | N/A | 1,000,000 pages | 1,000,000 | Reads entire table |
Bookmark lookups are only efficient when the number of matching rows is small (typically < 1-5% of the table). Beyond this 'tipping point,' the optimizer often chooses a full table scan over non-clustered index + lookups because sequential I/O is more efficient than many random I/Os.
When the Optimizer Avoids Lookups:
Smart database optimizers compare the cost of:
- Non-clustered seek + bookmark lookups
- Clustered index scan (if query uses clustered key range)
- Full table scan
The optimizer typically uses non-clustered indexes when:
- Very few rows match (high selectivity)
- The index covers all required columns (no lookup needed)
- Lookup costs are acceptable given the selectivity
The optimizer switches to scans when:
- Many rows match (low selectivity)
- Bookmark lookup cost exceeds scan cost
- Statistics indicate a full scan is cheaper
1234567891011121314
-- Query that might use non-clustered index + lookupSELECT ProductName, Price, Description FROM Products WHERE CategoryID = 5; -- Few products per category: Index efficient -- Query that might trigger a scan insteadSELECT ProductName, Price, Description FROM Products WHERE CategoryID IN (1, 2, 3, 4, 5, 6, 7, 8, 9, 10); -- Many categories: Scan likely cheaper -- Check the actual execution plan to see optimizer's choice-- SQL Server: SET STATISTICS IO ON; or examine Execution Plan-- PostgreSQL: EXPLAIN ANALYZE-- MySQL: EXPLAINCovering Indexes: Eliminating Lookups
A covering index is a non-clustered index that contains all the columns required by a query, eliminating the need for bookmark lookups. When an index 'covers' a query, all data can be retrieved directly from the index leaf pages without accessing the base table.
The Power of Coverage:
Consider this query:
SELECT CustomerID, OrderDate, TotalAmount
FROM Orders
WHERE CustomerID = 12345;
With just an index on CustomerID:
- Find matching entries in index (CustomerID, row locator)
- For each entry, perform bookmark lookup to get OrderDate and TotalAmount
- Many random I/Os if customer has many orders
With a covering index on (CustomerID, OrderDate, TotalAmount) or CustomerID INCLUDE (OrderDate, TotalAmount):
- Find matching entries: (CustomerID, OrderDate, TotalAmount) all present
- Return directly—no lookups needed
- Sequential I/O through index leaves only
Creating Covering Indexes with Composite Keys:
You can include additional columns in the index key itself:
CREATE NONCLUSTERED INDEX IX_Orders_Customer_Date_Amount
ON Orders (CustomerID, OrderDate, TotalAmount);
Pros:
- All three columns are in the key
- Can support queries ordering by any key prefix
- Supports range queries on OrderDate within a CustomerID
Cons:
- Index maintains sort order on all three columns
- Inserts must maintain this multi-column order
- Larger index if columns are wide
- May be overkill if you never filter/sort by OrderDate, TotalAmount
When a covering index is used, the optimizer performs an 'index-only scan' (PostgreSQL) or 'index seek' without lookup (SQL Server). This appears in execution plans and is highly desirable for frequently-executed queries. Monitor for these patterns when tuning.
Non-Clustered Index Maintenance
Non-clustered indexes must be maintained whenever the underlying data changes. Every INSERT, UPDATE, and DELETE on the base table may require corresponding modifications to each non-clustered index. Understanding this overhead is crucial for balancing read and write performance.
INSERT Operations:
When a row is inserted into a table:
- Insert the row into the clustered index (or heap)
- For EACH non-clustered index:
- Extract the indexed column values from the new row
- Navigate the index B+ tree to find insertion point
- Insert new (key, row locator) entry
- Potentially split pages if full
With 5 non-clustered indexes, a single INSERT requires 5 additional B+ tree insertions—each with its own page navigation and potential split.
| Indexes | INSERT Overhead | UPDATE (Key) Overhead | DELETE Overhead |
|---|---|---|---|
| 0 | 1 (base only) | 1 | 1 |
| 1 | 2 operations | 2 (if key changes) | 2 |
| 5 | 6 operations | 6 (if key changes) | 6 |
| 10 | 11 operations | 11 (if key changes) | 11 |
| 20+ | 21+ operations | 21+ (if key changes) | 21+ |
UPDATE Operations:
Update behavior depends on which columns are modified:
Non-indexed column update:
- Update the data row (clustered index or heap)
- Non-clustered indexes unchanged—no overhead
Indexed column update (non-clustered key):
- Update the data row
- For each index containing the changed column:
- Delete old (key, locator) entry
- Insert new (key, locator) entry
- This is essentially DELETE + INSERT within the index
Clustered key update:
- Data row moves to new location
- ALL non-clustered indexes must update their row locators
- This is extremely expensive with many non-clustered indexes
Each non-clustered index imposes a 'tax' on write operations. Tables with many indexes may see INSERT times 10-20x slower than tables with just a clustered index. Always evaluate whether the read performance benefits justify the write overhead.
DELETE Operations:
When a row is deleted:
- Delete (or mark deleted) the data row
- For EACH non-clustered index:
- Navigate to the index entry
- Delete the (key, locator) entry
- Potentially trigger page merges
Strategies to Manage Write Overhead:
- •Limit Index Count: Question every index—does it serve active queries? Remove unused indexes.
- •Drop Before Bulk Load: Disable or drop non-clustered indexes before massive data loads, then rebuild
- •Filtered Indexes: Index only a subset of rows (WHERE clause) to reduce size and maintenance
- •Consolidate Indexes: Merge multiple narrow indexes into covering indexes when possible
- •Monitor Index Usage: Use DMVs or system tables to find indexes with zero seeks/scans
- •Consider Read/Write Ratio: OLTP systems (write-heavy) need fewer indexes than OLAP/reporting systems
Non-Clustered Indexes on Heap Tables
When a table lacks a clustered index, it's stored as a heap—an unordered collection of data pages. Non-clustered indexes on heap tables behave differently than those on clustered tables, with distinct advantages and disadvantages.
Heap Table Structure:
- Data pages are not ordered by any key
- New rows are inserted wherever space is available
- No leaf-level page links for scans (data is not logically ordered)
- Row identifiers are physical: FileID:PageID:SlotNumber (RID)
Non-Clustered Index Row Locators on Heaps:
Instead of storing clustered key values, non-clustered index entries store physical RIDs:
Index Entry = (IndexKeyValue, RID)
RID = (FileID:PageID:SlotNumber)
- •Direct Access: RID lookup is O(1) — direct page/slot access, no tree traversal
- •No Key Overhead: RID is fixed 8 bytes regardless of key width
- •Faster Lookups: Fewer I/Os per individual lookup compared to clustered key navigation
- •Insert Speed: No key ordering required, inserts go to any available space
- •Forwarding Pointers: Row growth causes forwarding, adding I/O
- •No Range Scan Optimization: Heap data is scattered; no sequential benefit
- •No Covering: Must always look up heap for non-indexed columns
- •Page Splits Complex: Can invalidate RIDs, requiring chain updates
The Forwarding Pointer Problem:
When a row in a heap grows (due to an UPDATE) and no longer fits in its current page:
- The row moves to a new page with sufficient space
- A forwarding pointer is left at the original location
- Non-clustered index RIDs still point to the original location
- Lookups now require TWO page accesses: original RID → forwarding pointer → new location
Over time, many updates create long forwarding chains, severely degrading performance. This is a primary reason DBAs prefer clustered tables over heaps for tables with variable-length columns or frequent updates.
When Heaps Make Sense:
- Staging tables for bulk data loading
- Tables always accessed via full scans (no selective queries)
- Append-only logging tables with no updates
- Temporary data with short lifespan
For most production tables, a clustered index (even on an arbitrary or synthetic key) provides better overall performance than a heap. The benefits of ordered storage, eliminated forwarding pointers, and efficient range scans usually outweigh the slight insert overhead.
Practical Considerations and Design Patterns
Designing effective non-clustered indexes requires understanding query patterns, data characteristics, and system workloads. Here are essential patterns and anti-patterns for non-clustered index design.
- •Leftmost Prefix Rule: For composite indexes, queries must use leftmost columns. Index on (A, B, C) supports WHERE A=x, WHERE A=x AND B=y, but NOT WHERE B=y alone.
- •Selectivity First: Place the most selective column first in composite indexes for better filtering.
- •Cover Hot Queries: Identify the 5-10 most frequent queries and ensure they're covered by indexes.
- •Filtered Indexes: Use WHERE clauses to index only relevant rows (e.g., WHERE Status = 'Active').
- •Descending Columns: Specify DESC for columns frequently sorted descending to avoid sort operations.
- •Over-Indexing: Creating indexes for every possible query; write performance suffers enormously.
- •Indexing Low-Cardinality Columns: Index on Status with 3 values provides minimal selectivity; often full scans are faster.
- •Duplicate Indexes: Multiple indexes with same leading columns waste space (e.g., (A) and (A, B) — the second covers the first).
- •Wide Composite Keys: Keys with 5+ columns are often signs of design issues; consider covering columns via INCLUDE instead.
- •Ignoring Usage Data: Creating indexes speculatively without analyzing actual query workloads.
Index Selection Workflow:
- •Capture Workload: Collect actual queries from query logs, profiling, or monitoring tools
- •Identify Slow Queries: Focus on queries with high frequency × high duration
- •Analyze Execution Plans: Look for table scans, expensive lookups, sorts that could be avoided
- •Design Candidate Indexes: Create indexes targeting identified bottlenecks
- •Test in Non-Production: Measure query improvements AND write degradation
- •Monitor Post-Deployment: Track index usage statistics; drop unused indexes
KEEP LEARNING
There’s more to understand.
You’re reading the introduction. Create a free account to read the complete lesson, save notes and keep track of your progress.