Clustered and Non-Clustered Implementations

Introduction to Database Indexing

Database indexes help the database locate data faster. Without an index, the database performs a table scan, which means reading all rows one by one. This becomes slow as tables grow in size.

Indexes improve:

• Query performance
• Sorting
• Join operations
• Input/output (I/O) efficiency

They work by organizing data in a structure that supports fast searching.

Clustered and Non-Clustered Implementations

B-Tree Architecture: How Indexes Work

Most relational database indexes use B-Tree (Balanced Tree) structures. A B-Tree allows efficient searching, inserting, and deleting with O(log n) complexity.

How a B-Tree Works

• The root node contains key ranges.
• Each key range points to a child node.
• Leaf nodes contain the actual index entries.
• All leaf nodes stay at the same depth.
• The database automatically handles node splits and merges to keep the tree balanced.

Operation Complexity

Operation      Complexity          Description
-------------------------------------------------------------------
Equality Seek  O(log n)            Direct lookup
Range Query    O(log n + k)        k = number of rows returned
Insert         O(log n)            Includes potential page splits
Delete         O(log n)            Includes potential page merges

Clustered Indexes

A clustered index defines the physical order of the table data. There can only be one clustered index per table because the table can only be physically sorted one way.

Key Characteristics

1. The table’s data rows are stored in order of the clustered index key.
2. If the key is not unique, SQL Server automatically adds a hidden value (uniquifier) to maintain uniqueness.
3. Sequential keys reduce fragmentation and improve insert performance.

Example

CREATE CLUSTERED INDEX IX_Orders_Date 
ON Orders (OrderDate);

What Happens on Disk

Page 1023 → rows for 2024-01-01
Page 1024 → rows for 2024-01-02
Page 1025 → rows for 2024-01-03

Useful Configuration Options

Fill Factor (leave free space for updates)

CREATE CLUSTERED INDEX IX_Customers_Cluster 
ON Customers (LastName)
WITH (FILLFACTOR = 90);

Composite Key Strategy

CREATE CLUSTERED INDEX IX_Orders_Composite
ON Orders (OrderDate DESC, OrderID ASC);

Non-Clustered Indexes

A non-clustered index is a separate structure from the table. It contains:

• The index key
• A pointer (row locator) to the actual row

Example

CREATE NONCLUSTERED INDEX IX_Orders_Customer
ON Orders (CustomerID)
INCLUDE (OrderDate, TotalAmount);

Storage Layout Example

Index Page:
CustomerID | Row Locator
12345      | Page 1023, Slot 5
12345      | Page 1025, Slot 2
12346      | Page 1030, Slot 7

Specialized Index Types

1. Filtered Index

CREATE NONCLUSTERED INDEX IX_Users_Active
ON Users (LastLoginDate)
WHERE IsActive = 1;

2. Columnstore Index

Used for analytics workloads.

CREATE COLUMNSTORE INDEX IX_Sales_Columnstore
ON Sales (ProductID, SaleDate, Quantity, Amount);

Index Selection Guide

Scenario                     Recommended Index            Reason
---------------------------------------------------------------------------------------
Primary Key                 Clustered                    Natural record ordering
Range Queries               Clustered                    Efficient sequential reads
Lookup Columns (OLTP)       Non-Clustered                Fast seeks
Covering Queries            Non-Clustered + INCLUDE      Removes key lookups
Low Cardinality Columns     Filtered Index               Smaller, more efficient

Index Maintenance

Indexes get fragmented over time and need maintenance.

Smart Maintenance Script

DECLARE @IndexName NVARCHAR(255), @Fragmentation FLOAT

DECLARE IndexCursor CURSOR FOR
SELECT name, avg_fragmentation_in_percent
FROM sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, NULL) ps
JOIN sys.indexes i 
  ON ps.object_id = i.object_id AND ps.index_id = i.index_id
WHERE ps.avg_fragmentation_in_percent > 5

OPEN IndexCursor
FETCH NEXT FROM IndexCursor INTO @IndexName, @Fragmentation

WHILE @@FETCH_STATUS = 0
BEGIN
    IF @Fragmentation > 30
        EXEC('ALTER INDEX ' + @IndexName + ' ON Orders REBUILD')
    ELSE
        EXEC('ALTER INDEX ' + @IndexName + ' ON Orders REORGANIZE')

    FETCH NEXT FROM IndexCursor INTO @IndexName, @Fragmentation
END

CLOSE IndexCursor
DEALLOCATE IndexCursor

Performance Comparison (10M Rows)

Operation                     Clustered     Non-Clustered      Heap
-----------------------------------------------------------------------------------
Primary Key Seek             0.003 ms      0.003 + 0.2 ms      2.1 ms
Range Query (10k rows)       12 ms         45 ms               1200 ms
INSERT (sequential)          8 ms          10 ms               5 ms
INSERT (random)              120 ms        15 ms               5 ms
UPDATE (in-place)            6 ms          9 ms                7 ms

Advanced Index Patterns

Indexed View

CREATE VIEW dbo.OrderSummary WITH SCHEMABINDING AS
SELECT CustomerID, COUNT_BIG(*) AS OrderCount, SUM(TotalAmount) AS Total
FROM dbo.Orders
GROUP BY CustomerID;

CREATE UNIQUE CLUSTERED INDEX IX_OrderSummary
ON dbo.OrderSummary (CustomerID);

Partitioned Index

CREATE PARTITION FUNCTION OrderDateRangePF (DATE)
AS RANGE RIGHT FOR VALUES 
('2024-01-01', '2024-02-01', '2024-03-01');

Troubleshooting Index Problems

Useful system views:

SET STATISTICS XML ON;

SELECT * FROM sys.dm_db_missing_index_details;

SELECT * FROM sys.dm_db_index_usage_stats;

Conclusion

A good indexing strategy balances:

• Fast reads
• Acceptable write performance
• Storage usage
• Maintenance overhead

General rules:

1. Use a clustered index on your main access pattern.
2. Create non-clustered indexes for frequent search columns.
3. Use INCLUDE to make queries covering.
4. Remove unused or redundant indexes.
5. Rebuild or reorganize indexes when fragmented.