A B-tree organizes an index into ordered pages across levels: one root page, optional intermediate pages, and a leaf level. The upper levels direct a search toward lower pages, so SQL Server can locate ordered data without reading every data page. section 4.2 section 11.12
Figure 4.6 Clustered index seeks and scans against a B-tree
Use the seek-and-scan diagram to compare following a root-to-leaf path with reading the entire leaf level. section 4.2
Mistake #1: treating every index as if it stores the table in the same way. A clustered index builds a B-tree whose leaf level is the table’s actual data pages, ordered by the clustered key. That physical ordering permits only one clustered index. A nonclustered index is also a B-tree, but its leaf level holds pointers to data pages in a heap or clustered index, so several nonclustered indexes can exist. section 11.0
The structure explains why two apparently similar reads can have very different costs:
- A clustered index seek traverses index levels to locate a row; at most, it reads one page per B-tree level when searching for a single row. section 4.2
- A scan reads leaf-level pages until it finds the requested data or reaches the end, potentially reading every table data page. section 4.2 section 11.12
- For several qualifying rows, a seek finds the starting point and then reads through the leaf level. section 4.2
- A heap has no clustered B-tree ordering; its allocated pages are not stored in a particular order, so many queries must read every data page. section 11.0
Wide clustered keys spread through the tree
A primary key commonly creates the clustered index. If that key is wide, such as an NCHAR(12) value rather than an INT, it consumes more storage in indexed rows. Choose the smallest data type that satisfies the business rules, and consider whether a different unique column should be the clustered key when a wide primary key would make that choice costly. section 4.2 section 11.0
Mistake #2: assuming ordered access stays efficient regardless of page condition. Low page density means more pages must be read. Updates to dense pages can cause page splits; splits in the middle of an index move data and add I/O. Pages out of order cause external fragmentation, which harms scans but not seeks. Rebuild only indexes that need it according to fragmentation statistics rather than rebuilding every index indiscriminately. section 11.12
Figure 11.2 A clustered index creates a B-tree and orders data pages
Use the clustered-index diagram to see that the leaf level is the ordered set of table data pages, not a separate copy of the table. section 11.0
