We already know that all indexes are organized on B-trees except ColumnStore indexes and always have a single root node. SQL Server always uses this root node as the starting point for traversing an Index. In
an Index tree, all the index nodes above the leaf node include the root node
also are known as Non-leaf nodes. The leaf node is the bottom level of the
index structure and contains the key value index entry either reference rows of
the data pages or the complete rows of the data pages.
Nonclustered indexes have the same B-Tree structure
as clustered indexes with one significant difference. The leaf node of the nonclustered
index contains key values not the actual data. These key values map to pointer
or clustering keys that locate rows in the data pages.
How does Nonclustered
index implement?
The implementation of the nonclustered index depends
on whether the data pages of a table are managed as a Heap or as a clustered
index. If nonclustered index is built in a heap then SQL Server uses pointers
in the leaf node index pages that point a row in the data pages.
If we have a table with clustered index, SQLServer builds a nonclustered index on the top of the clustered index structure
and SQL Server uses clustering keys in the leaf node index page of the
nonclustered index to point the cluster index.
How does
Nonclustered index navigate on a Heap?
To understand this, we could take an alphabet
example where all the data on the Nonclustered index is built in a heap as
given below:
In the above Heap based nonclustered index page,
leaf node pages contain the pointers that point a row in the data pages also.
How does
SQL Server navigate a nonclustered index?
To understand this, we are taking the above
example and we need to find out the alphabet ‘M’ from our data table where nonclustered
index is built on the first name data field and we are using below script to
find out the result as given below:
SELECT FirstName, LastName
FROM dbo.DataTable
WHERE FirstName='M'
|
Root node
Navigation
SQL Server starts with Root node of the nonclustered
index and evaluated that ‘M’ is greater than or equal to the key value actor
‘A’ and the compression result is to true. Now, SQL server moves to next key
value ‘M’ on the root node and do the same compression evaluation which is to
true again. Now, SQL server moves to next key value ‘R’ on the root node and do
the same compression evaluation which is false. In this case, SQL Server uses
the previous key value ‘M’ on the root node and moves to intermediate node.
Intermediate
node Navigation
After moving to intermediate node, SQL Server
evaluated that ‘M’ is greater than or equal to the key value actor ‘M’ where
the compression result is to true. Now,
SQL server moves to next key value ‘N’ on the intermediate node and compression
evaluation result is false. In this case, SQL Server uses the previous key
value ‘M’ on the intermediate node and moves to Leaf node.
Leaf node
Navigation
SQL Server reads through the leaf node until it
finds ‘M’ and then uses the point value that allocated with the data page.
Data Page
Navigation
SQL Server reads through the data page until it
finds the key value is equal to ‘M’. SQL Server returns this row to the query
processor. The pages in the data chain and the rows in them are ordered on the
value of the nonclustered index key.
Conclusion
The implementation of the nonclustered index depends
on whether the data pages of a table are managed as a Heap or as a Clustered
index. The leaf node of the nonclustered index contains the key value not the
actual data. These key values map to the pointer or clustering keys that locate
in the data pages.
Index structure in SQL Server
References: https://technet.microsoft.com/en-us/library/ms177443(v=sql.105).aspx
thanx, god
ReplyDelete