Database Reference
In-Depth Information
Another benefit of a nonclustered index is that because it is in a separate structure from the data table, it can be
put in a different filegroup, with a different I/O path, as explained in Chapter 3. This means that SQL Server can access
the index and table concurrently, making searches even faster.
Indexes store their information in a balanced tree, referred to as a B-tree , structure, so the number of reads
required to find a particular row is minimized. The following example shows the benefit of a B-tree structure.
Consider a single-column table with 27 rows in a random order and only 3 rows per leaf page. Suppose the layout
of the rows in the pages is as shown in Figure 8-3 .
Figure 8-3. Initial layout of 27 rows
To search the row (or rows) for the column value of 5, SQL Server has to scan all the rows and the pages, since
even the last row in the last page may have the value 5. Because the number of reads depends on the number of
pages accessed, nine read operations (retrieving pages from the disk and transferring them to memory) have to be
performed without an index on the column. This content can be ordered by creating an index on the column, with the
resultant layout of the rows and pages shown in Figure 8-4 .
Figure 8-4. Ordered layout of 27 rows
Indexing the column arranges the content in a sorted fashion. This allows SQL Server to determine the possible
value for a row position in the column with respect to the value of another row position in the column. For example,
in Figure 8-4 , when SQL Server finds the first row with the column value 6, it can be sure that there are no more rows
with the column value 5. Thus, only two read operations are required to fetch the rows with the value 5 when the
content is indexed. However, what happens if you want to search for the column value 25? This will require nine read
operations! This problem is solved by implementing indexes using the B-tree structure (as in Figure 8-5 ).
Figure 8-5. B-tree layout of 27 rows
A B-tree consists of a starting node (or page) called a root node with branch nodes (or pages) growing out of it
(or linked to it). All keys are stored in the leaves. Contained in each interior node (above the leaf nodes) are pointers
to its branch nodes and values representing the smallest value found in the branch node. Keys are kept in sorted order
within each node. B-trees use a balanced tree structure for efficient record retrieval—a B-tree is balanced when the
leaf nodes are all at the same level from the root node. For example, creating an index on the preceding content will
generate the balanced B-tree structure shown in Figure 8-5 . At the bottom level, all the leaf nodes are connected to
each other through a doubly linked list, meaning each page points to the page that follows it, and the page that follows
it points back to the preceding page. This prevents having to go back up the chain when pages are traversed beyond
the definitions of the intermediate pages.
 
Search WWH ::




Custom Search