MS SQL Server - Index Internals III

Today’s discussion continues on the different types of Indexes available on MS SQL Server.

Unlike from my previous example of index on the back of an Atlas, which normally has one index, a table may have multiple indexes. These indexes can be defined on one or more columns of the tables. The two major types of indexes in SQL Server are Clustered and Non-clustered Indexes.

Clustered Indexes: A clustered when defined on a column of a table, the data of the table in the data pages are sorted in order of the column on which index is defined. This column is referred as an Index Key. Since the data is sorted physically on the disk, the leaf page of the index pages are the data pages of the table.

Inserting a new row in a table with clustered index defined, SQL Server ensures that the row is placed in the correct physical location in key sequence order. Structure of the Clustered Index is as given below:Non-Clustered Indexes: A Non-clustered index contain only the index key (column on which non-clustered index is defined) and a reference to find the data. The items in the index are stored in the order of the index key values, but the information in the table is stored in a different order (which can be dictated by a clustered index). If no clustered index is created on the table, the rows are not guaranteed to be in any particular order.

Non-clustered index structure is depicted as: At any given level in the index, the pages are linked together as shown in Figure below, and this is true regardless of whether the index is a Clustered index or a Non-clustered index.
Both the clustered and non-clustered indexes can be defined on one or more columns of a table, to serve the frequent database queries. However there can be only one clustered index defined on a table while there can be 249 non-clustered indexes created on a table.

MS SQL Server - Index Internals II

Following to my earlier post on how SQL Server stores and access data, lets now get into details of what Indexes and how are they processed by SQL Server for improving performance.

As per the definition “An Index is a pointer to data in a table”. Here when we say pointer it’s not much different from the pointers that we access in programming language like C/C++. If you have worked with pointers, you know that “A pointer is used to store the location of a variable or we say a Data Member”. Similarly in SQL Server an Index stores the locations of the data rows of a table and occupies a discrete memory in SQL Server.

Index is stored separately from the table for which the index is created. When an Index is defined, the Index pages are created by SQL Server to store the address of the data rows, based on the Indexed column. These Indexes are linked to each other in a B-tree structure. Let’s consider a table products with the following structure and data inserted in following order in data pages:


Now Suppose an Index is defined on the UnitPrice field of the table. The Index Pages will be defined for the table as shown below:

SQL Server uses these indexes to find data quickly when a query is processed. Indexes can be created or dropped with no effect on the data, as it is stored as separate entity from the table. Indexes operate 'behind the scenes' in support of the database engine to improve the performance of data retrieval.

Consider the following query on the products table above. This query retrieves products in a specific price range.

SELECT ProductID, ProductName, UnitPrice FROM Products WHERE (UnitPrice > 4.5) AND (UnitPrice <10)

If there was no index defined on the table, a table scan will be performed to find the products with price ranging between 7.5 and 10. There will be 24 iterations (navigating through each row) to find the required result.

With an index defined on the UnitPrice field, navigating through the Main Index Page, the query can be served in 4 iterations. Hence you can distinguish the remarkable difference an Index can make in the performance of a query.

Later in the tread I will be talking about the different types of Indexes in SQL Server.

MS SQL Server - Index Internals I

I dedicate this post of mine to my most interesting subject of MS SQL Server – Index Internals, for everyone interested in getting a depth of how Indexing in SQL Server works.

While running a query in SQL Server, many of them wonder at times “why particular query performs so terrible while the other is just fine”. One of the key factors that can affect a query performance is the Indexing available on the related tables.

Best possible way to recognize how index can benefit queries and what would make things worse; is to understand how SQL Server processes these indexes internally.

Let us dive into the details of how SQL Server stores and access data in database.

SQL Server can store data in two ways:

1. In Heap: The Order in which the data is inserted is stored in the same order in the data pages of the table.


2. Order of the Clustered Indexed Column Key: The data is added to the data pages of a table sorted in the order of the column having clustered index. Index Pages are added for the table to store the indexes.

These data in SQL Server can be accessed in two ways:

1. Table Scan: The data in the heap is accessed by scanning through each row in the data pages of the table to serve a query request.


2. Using Indexes: With the help of Indexes, SQL Server scan through the Index Pages using B-Tree traversing algorithm to arrives to the resultset in the data pages. Index scan helps SQL Server to search data in the table in a similar way as we scan through the Index page of an Atlas to find a location on the book.

Below is an illustration to help you understand the data storage and access in the SQL Server database:

• Let us have two tables, TableA and TableB that collect names of the students, with the field Name.
• TableA stores the data in the Heap
• TableB has a index defined on the field Name


• The data in both the tables are entered in following order: John, Sam, Anna, Denial, Rudd, Andrew, Samantha and Brown.


• 
  
• 
  

Later in this topic I will be discussing in detail what the indexes are, how they are stored in SQL Server and how it help in improving the performance.

continued...