Table of Contents
Indexing in DBMS is used to optimize the performance of a database by minimizing the number of disk accesses required when a query is processed. It is a data structure technique that is used to quickly locate and access the data in a database.
An index :
- Takes a search key as input
- Efficiently returns a collection of matching records.
Index structure:
Indexes can be created using some database columns.
- The first column of the database is the search key that contains a copy of the primary key or candidate key of the table. The values of the primary key are stored in sorted order so that the corresponding data can be accessed easily.
- The second column of the database is the data reference. It contains a set of pointers holding the address of the disk block where the value of the particular key can be found.
Advantages of indexing
Advantages of indexing are as follows
- Better performance of queries.
- Fast searching from the database.
- Fast retrieval of data.
- Increase performance in SELECT query.
Disadvantages of indexing
Disadvantages of indexing are as follows
- Indexing takes more space.
- Decrease performance in INSERT, DELETE and UPDATE query.
Types of Indexing
*note: It’s Sparse not spare
Ordered indices
The indices are usually sorted to make searching faster. The indices which are sorted are known as ordered indices.
Example: Suppose we have an employee table with thousands of record and each of which is 10 bytes long. If their IDs start with 1, 2, 3….and so on and we have to search student with ID-543.
- In the case of a database with no index, we have to search the disk block from starting till it reaches 543. The DBMS will read the record after reading 543*10=5430 bytes.
- In the case of an index, we will search using indexes and the DBMS will read the record after reading 542*2= 1084 bytes which are very less compared to the previous case.
Primary Index
- If the index is created on the basis of the primary key of the table, then it is known as primary indexing. These primary keys are unique to each record and contain 1:1 relation between the records.
- As primary keys are stored in sorted order, the performance of the searching operation is quite efficient.
- The primary index can be classified into two types:
- Dense index
- Sparse index.
Dense index
- The dense index contains an index record for every search key value in the data file. It makes searching faster.
- In this, the number of records in the index table is the same as the number of records in the main table.
- It needs more space to store the index record itself. The index records have the search key and a pointer to the actual record on the disk.
Sparse index
- In the data file, index record appears only for a few items. Each item points to a block.
- In this, instead of pointing to each record in the main table, the index points to the records in the main table in a gap.
Clustering Index
In a clustered index, table records are sorted physically to match the index.
- A clustered index can be defined as an ordered data file. Sometimes the index is created on non-primary key columns which may not be unique for each record.
- In this case, to identify the record faster, we will group two or more columns to get the unique value and create index out of them. This method is called a clustering index.
- The records which have similar characteristics are grouped, and indexes are created for these group.
Example: suppose a company contains several employees in each department. Suppose we use a clustering index, where all employees which belong to the same Dept_ID are considered within a single cluster, and index pointers point to the cluster as a whole. Here Dept_Id is a non-unique key.
Secondary Index
The index table is stored in main memory and main memory is small in size, and the sparse index is also big in size, so we need to build the secondary index.
- Secondary index manages the index in multi-levels.
- Multi-level indexing is an advancement in the secondary matrix, and we use more and more levels in multi-level indexing.
In sparse indexing, as the size of the table grows, the size of mapping also grows.If the mapping size grows then fetching the address itself becomes slower. In this case, the sparse index will not be efficient. To overcome this problem, secondary indexing is introduced.
In secondary indexing, to reduce the size of mapping, another level of indexing is introduced. In this method, the huge range for the columns is selected initially so that the mapping size of the first level becomes small. Then each range is further divided into smaller ranges. The mapping of the first level is stored in the primary memory, so that address fetch is faster. The mapping of the second level and actual data are stored in the secondary memory (hard disk).
Difference Between Dense Index and Sparse Index
Dense index | Sparse index |
---|---|
The index size is larger in dense index. | In sparse index, the index size is smaller. |
Time to locate data in index table is less. | Time to locate data in index table is more. |
There is more overhead for insertions and deletions in dense index. | Sparse indexing have less overhead for insertions and deletions. |
Records in dense index need not to be clustered. | In case of sparse index, records need to be clustered. |
Computing time in RAM (Random access memory) is less with dense index. | In sparse index, computing time in RAM is more. |
Data pointers in dense index point to each record in the data file. | In sparse index, data pointers point to fewer records in data file. |
Search performance is generally faster in dense index. | In sparse index, search performance may require additional steps, which will result in slowing down the process. |