Indexing in Databases

  • The first column is the Search key that contains a copy of the primary key or candidate key of the table. These values are stored in sorted order so that the corresponding data can be accessed quickly.
    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.

Please note that the indexes are created on Disk, not in main memory. It is always better to create indexes that are sorted on the basis of keys so that binary search can be applied for searching. It doesn’t make much sense to create unsorted indexes since access time will be 0(n).

Types of Indexing

Primary Index

  • Dense Index
  • Sparse Index

Dense Index

  • For every search key value in the data file, there is an index record.
  • This record contains the search key and also a reference to the first data record with that search key value.
Dense Index

Sparse Index

  • The index record appears only for a few items in the data file. Each item points to a block as shown.
  • To locate a record, we find the index record with the largest search key value less than or equal to the search key value we are looking for.
  • We start at that record pointed to by the index record, and proceed along with the pointers in the file (that is, sequentially) until we find the desired record.
Sparse Index

Secondary Indexing

  • In secondary indexing, our main file is unsorted.
  • Secondary indexing can be done on key as well as non key attribute.
  • A non clustered or secondary index just tells us where the data lies, i.e. it gives us a list of virtual pointers or references to the location where the data is actually stored.
  • We can have only dense ordering in the secondary indexing as sparse ordering is not possible because data is not sorted in the main file.
Secondary Indexing

Clustered Indexing

  • Clustering indexing is defined on a sorted data file. The data file is sorted on a non-key field like age of a student or salary of an employee etc. In real world, there are cases where we want to search on the basis of non unique key. For such cases, the index is created on non-primary key columns which may not be unique for each record.
  • In such cases, in order to identify the records faster, we will group two or more columns together to get the unique values and create index out of them. This method is known as the clustered indexing
  • There will be only one entry for each unique value of non key attribute in the index table.
  • Basically, records with similar characteristics are grouped together and indexes are created for these groups. For example, students studying in each semester are grouped together. i.e. 1st Semester students, 2nd semester students, 3rd semester students etc are grouped.
Clustered Indexing

Multilevel Indexing

Multilevel Indexing

B-Trees

How is indexing done in DBMS using B-Trees

Sample Table

Advantages of Indexing

  • It helps you to reduce the total number of I/O operations needed to retrieve that data, so you don’t need to access a row in the database from an index structure.
  • Offers faster search and retrieval of data to users.

Disadvantages of Indexing

  • To perform the indexing database management system, you need a primary key on the table with a unique value.
  • You can’t perform any other indexes in Database on the Indexed data.
  • SQL Indexing Decrease performance in INSERT, DELETE, and UPDATE query.

References

--

--

--

Software Engineer

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

One Script for Creating MySQL Users on Both Vanilla and RDS MySQL

Sharing Exoscale Docker Machine With Portainer

Buggy Python Code: The 10 Most Common Mistakes That Python Developers Make

python coding help

Simplifying data consumption in Apache Kafka

Exploring HMS App Messaging

Real-Time Application With Socket Programming

Aws Lambda microService in django

Development Log 4

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Aman Jain

Aman Jain

Software Engineer

More from Medium

Cache data with Redis in CakePHP 4

SOLID Principles: Explained

Starting the journey with scalability, horizontally scaling with load balancing

Quick Analysis on Lambda cold start