Database index what is

An Index is a small table having only two columns. The first column comprises a copy of the primary or candidate key of a table. Its second column contains a set of pointers for holding the address of the disk block where that specific key value stored. Indexing in Database is defined based on its indexing attributes.

Two main types of indexing methods are:. Primary Index is an ordered file which is fixed length size with two fields. The first field is the same a primary key and second, filed is pointed to that specific data block. In the primary Index, there is always one to one relationship between the entries in the index table. In a dense index, a record is created for every search key valued in the database. This helps you to search faster but needs more space to store index records. In this Indexing, method records contain search key value and points to the real record on the disk.

It is an index record that appears for only some of the values in the file. You may not notice this improvement with small tables but it can be significant for large tables; however, there can be disadvantages to having too many indexes. Indexes can slow down the performance of some inserts, updates, and deletes when the driver has to maintain the indexes as well as the database tables.

Also, indexes take additional disk space. For indexes to improve the performance of selections, the index expression must match the selection condition exactly. If you often use Where clauses that involve more than one field, you may want to build an index containing multiple fields. This creates a concatenated index. Concatenated indexes can also be used for Where clauses that contain only the first of two concatenated fields. If your index fields include all the conditions of the Where clause in that order, the driver can use the entire index.

The driver uses only one index when processing Where clauses. If you have complex Where clauses that involve a number of conditions for different fields and have indexes on more than one field, the driver chooses an index to use.

The driver attempts to use indexes on conditions that use the equal sign as the relational operator rather than conditions using other operators such as greater than. If no conditions have the equal sign, the driver first attempts to use an index on a condition that has a lower and upper bound, and then attempts to use an index on a condition that has a lower or upper bound.

The driver always attempts to use the most restrictive index that satisfies the Where clause. Note: The data may or may not be stored in sorted order. The second column is the Data Reference or Pointer which contains a set of pointers holding the address of the disk block where that particular key value can be found.

The indexing has various attributes: Access Types : This refers to the type of access such as value based search, range access, etc. Access Time : It refers to the time needed to find particular data element or set of elements. Insertion Time : It refers to the time taken to find the appropriate space and insert a new data.

Deletion Time : Time taken to find an item and delete it as well as update the index structure. Space Overhead : It refers to the additional space required by the index. In general, there are two types of file organization mechanism which are followed by the indexing methods to store the data: 1. Sequential File Organization or Ordered Index File: In this, the indices are based on a sorted ordering of the values. These are generally fast and a more traditional type of storing mechanism.

These Ordered or Sequential file organization might store the data in a dense or sparse format: i Dense Index: For every search key value in the data file, there is an index record. As the name implies, the piles, technically called nodes, are connected in a tree-like fashion. Each pile drastically reduces the number of items you need to scan; actually exponentially so. In this way, by walking down the nodes, doing comparisons along the way we can avoid scanning thousands of records, in just a few easy node scans.

Hopefully, this diagram helps to illustrate the idea…. In the example above consider you need to retrieve the record corresponding to the key-value To do so the following comparisons are made:. As the number of lookups is directly related to the height of the tree, it is imperative to ensure all the branches are of equal height.

This spreads out the data across the entire tree, making it more efficient to look up data within any range. Each time records are added, removed, or keys updates, special algorithms shift data and key values from block to block to ensure no one part of the tree is more than one level higher than the other.

If you are interested in the gritty detail, I would start with the Wikipedia article. I an actual example, each node dark blue would contain many key values light blue.

In fact, each node is the size of a block of a disk, which is traditionally the smallest amount of data that can be read from a hard drive. This is a pretty complicated subject.

I would really like to know. Please leave a comment. Kris Wenzel has been working with databases over the past 30 years as a developer, analyst, and DBA. Kris has written hundreds of blog articles and many online courses. He loves helping others learn SQL. Thank you so much for the example with the book index! It really helped solidify the concept of indexes in my mind. Are there other DB related areas that you would like see articles about?

Thanks for finding the error in the text. I corrected the scenario to finding 15 rather than That works better with the example. Good explanation all around, thanks. Where is 15 found and its corresponding record returned? Would be nice to have a little narrative on that to wrap up the example.

My greater than and less than symbols did not show up. I really appreciate for your efforts and valuable time doing such a great Hard work regarding SQL Server and Thank you so much for educating us.

The card sorting is a great example! Thanks for the explanation and example , the article is very useful , examples which you have used served the subject well. Very well explained. I am just wondering about the multikey indexes. I was trying out a few multikey indexes in mongodb, so could you please explain more about the multikey indexes. Thanks :.