Indexing in DBMS

Types of Indexing in DBMS

There are 4 types of indexing in DBMS:-

1. Ordered indices
2. Primary Index
3. Clustering Index
4. Secondary Index

1. Ordered Indices

Ordered indices are indices that have been ordered. These indices have been sorted, which makes searching easier and faster. To further understand ordered indices, let's look at an example. Consider a table of Coding Ninjas workers with lakhs of records, each of which is 5 bytes. If the employee with ID 1024 is among those whose IDs start with 1, 2, 3, etc.:

• In the event of a database without an index, we must search the disc block starting at zero and continuing until it reaches 1024. The DBMS will read the record once 1024*5=5120 bytes have been read.
• If there is an index, we will conduct the search using the index, and the DBMS will read the record after reading 1024*2 = 2048 bytes, which is a lot fewer bytes than in the previous example.

2. Primary Index

The term "primary indexing" refers to the process of creating indexes using the table's primary key. A fixed-length, sorted file with two fields—the first field containing the primary key and the second field containing the address pointing to a particular data block—makes up the primary index. Because the primary keys are kept in sorted order, searching is quite effective. The Dense and the Sparse index are the two categories that make up the primary index. Let us see an example to understand the primary index better. 

Here in the above example, you can see that the indexing is done on the basis of the primary key of the table. According to the primary, the address is napped, and searching can be done. 

Dense index

Because every search key value in the data file is present in the dense index, searching is quicker and more effective. The index tables used in dense indexing contain the same number of records as the primary table. It has the search key and a pointer to the disc block that has the record itself, but since storing the index record itself would take up more space, it just holds the search key.

The following figure is an example of understanding dense Indexing.

Sparse index

Only a few of the data file's items-each of which points to a block-have an index record. Instead of pointing to every record in the main database, the index in sparse indexing only points to the entries in the gap.

The following figure is an example of understanding sparse Indexing.

3. Clustering Index

Records, not pointers, are stored in this sort of indexing. An organized data file is another way to describe it. The index is occasionally built on non-primary key columns, which might not be distinct for every record. To obtain the unique values in a case like this, you can group two or more columns and build a type of index called a clustered index. This makes it easier for you to find the record quickly. Records with comparable qualities are grouped, and for these categories only, indexes are made.

For example, students studying in each semester are grouped together, that is, first-semester, second-semester, third-semester, etc. 

In the above example, you can see that more than two rows and columns are clustered. For the first semester, the records are clustered, and the same is for the second and third semesters. 

4. Secondary Index

The secondary index may be produced by a potential key (a field that has a unique value for each record). The Non-clustering index is another name for the secondary index. This reduces the first level's mapping size using a two-level database indexing strategy. As a result, a wide variety of numbers are chosen at the first level, keeping the mapping size short.

Let us understand this Indexing using an example. There is a bank account database where data is stored sequentially by account_no, and you want to find all accounts of a specific branch of any XYZ bank. We can have a secondary index in DBMS for every search key here. The index record is a record that points to a bucket containing pointers to all the records with their specific search-key value.

You can also read about the Multiple Granularity Locking.

Advantages of Indexing

The following are some advantages of Indexing:

• It makes searching faster, and eventually, data retrieval also becomes faster and more efficient.
• Indexing helps reduce the total number of I/O(input-output) operations needed to retrieve data, so we don't need to access a row in the database from an index structure.
• Indexing also helps to reduce tablespace (means storage) as you don't need to link to a row in a table.
• Indexes are also used to enforce primary key and foreign key constraints, which are important for data integrity and maintaining referential integrity in the database.

Disadvantages of Indexing

The following are some cons/disadvantages of Indexing:

• SQL indexing decreases the performance in queries like INSERT, UPDATE, and DELETE.
• Partition of an index-organized table is not allowed.
• A primary key on the table (with a unique value) is required to perform the Indexing in DBMS.
• Indexes can introduce additional conflicts for resources like locks and latches, mostly in high-concurrency database environments.

Also read, File System vs DBMS

Features of Indexing in DBMS

The following are some key features of Indexing in DBMS:-

• Fast Data Retrieval: Indexing provides quick access to data by creating a separate data structure (the index) that stores a subset of the data along with pointers to the actual data rows.
   
• Reduced Disk I/O: By using indexes, the DBMS can minimize the number of disk I/O operations required to retrieve data.
   
• Improved Query Performance: Indexes are also useful for improving the performance of queries that involve search and filter operations, such as WHERE clauses in SQL queries.
   
• Support for Sorting: Indexes can also speed up sorting operations.
   
• Unique Constraints: Indexes enforce the uniqueness of values in a column or set of columns.
   
• Primary and Foreign Keys: Primary key constraints are implemented using indexes, which ensures the uniqueness of values in the primary key column.
   
• Index Types: DBMS typically offers various types of indexes, including B-tree indexes, Hash indexes, Bitmap indexes, and more.

Frequently Asked Questions

What is indexing in DBMS?

Indexing in DBMS is used to swiftly access specific data from a database. Indexing is a method for reducing the amount of time a database query takes to search through data by using data structures. Indexing is used to locate and access the data quickly.

What are the different types of indexing in DBMS?

There are four types of indexing in DBMS which are ordered indices, primary index, clustered index, and secondary index. The primary index is further divided into two types again which are dense index and sparse index. 

What is clustering and indexing in DBMS?

Indexing is a method for reducing the amount of time a database query takes to search through data by using data structures. In clustering, the index is created on the non-primary key columns sometimes, which might not be unique for every record.

What is primary index and secondary index in DBMS?

Primary index in DBMS is on the primary key, organizing data order, while secondary index is on non-primary keys, facilitating faster access.

What is the difference between dense and sparse indexing?

Dense indexing stores index entries for every record, while sparse indexing only stores entries for some records, leading to differing storage and lookup efficiencies.

Conclusion

In this blog, we learned about Indexing in DBMS. It plays a crucial role in optimizing data retrieval and enhancing database performance. Through techniques like primary and secondary indexing, as well as dense and sparse indexing methods, databases can efficiently manage and retrieve data, significantly improving overall system efficiency and user experience.

Recommended Readings:

• Lock based protocol in DBMS
• Types of DBMS

Also, read about the top 100 SQL problems asked in various product and service-based companies like Microsoft, Google, Infosys, TCS, IBM, etc.

Do check out The Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.

You can also consider our DBMS Course to give your career an edge over others.