Database Index

A database index is a data structure that improves the speed of operations on a database table. Indexes can be created using one or more columns of a database table, providing the basis for both rapid random look ups and efficient access of ordered records. The disk space required to store the index is typically less than that required by the table (since indexes usually contain only the key-fields according to which the table is to be arranged, and excludes all the other details in the table), yielding the possibility to store indexes in memory for a table whose data is too large to store in memory.
Non-clustered
A non-clustered index normally contains a reference to a block that contains the row data for which the particular index item has been constructed. This block will hold several other rows depending on the row size. For each index lookup on a non-clustered index, a data block that houses the row sought after must also be retrieved.
Clustered
Clustering re-orders the data block in the same order as the index, hence it is also an operation on the data storage blocks as well as on the index. Exact operation of database systems vary, but because the row data can only be stored in one order physically, only one clustered index can be created on a given database table. Clustered indexes can greatly increase access speed, but usually only where the data is accessed sequentially in the same or reverse order of the clustered index, or when a range of items are selected.
Since the physical records are in this sort order on disk the next row item in the sequence is immediately before or after the last one, and so fewer data block reads are required. The primary feature of a clustered index is therefore the ordering of the physical data rows in accordance with the index blocks that point to them. Some databases separate the data and index blocks into separate files, while others intermix the two different types of data blocks within the same physical file(s). Databases that use the latter scheme may be said to store the actual data in the leaf node of the index, whereas, in fact there is still a distinction between the index and the data block, and the data blocks can be traversed without using the index by way of a link list that links the data blocks in order..