Indexing in Databases | Database Management System (DBMS) - Computer Science Engineering (CSE) PDF Download

Indexing is a way 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 which is used to quickly locate and access the data in a database.
Indexes are created using a few database columns.

  1. 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.
  2. 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.

Indexing in Databases | Database Management System (DBMS) - Computer Science Engineering (CSE)

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:
    • Dense Index:
      (i) For every search key value in the data file, there is an index record.
      (ii) This record contains the search key and also a reference to the first data record with that search key value.
      Indexing in Databases | Database Management System (DBMS) - Computer Science Engineering (CSE)
    • Sparse Index:
      (i) The index record appears only for a few items in the data file. Each item points to a block as shown.
      (ii) 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.
      (iii) 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.
      Indexing in Databases | Database Management System (DBMS) - Computer Science Engineering (CSE)
  2. Hash File organization: Indices are based on the values being distributed uniformly across a range of buckets. The buckets to which a value is assigned is determined by a function called a hash function.
    There are primarily three methods of indexing:
    • Clustered Indexing
    • Non-Clustered or Secondary Indexing
    • Multilevel Indexing
      (i) Clustered Indexing
      When more than two records are stored in the same file these types of storing known as cluster indexing. By using the cluster indexing we can reduce the cost of searching reason being multiple records related to the same thing are stored at one place and it also gives the frequent joing of more than two tables(records).
      Clustering index is defined on an ordered data file. The data file is ordered on a non-key field. In some 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 clustering index. 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.
      Indexing in Databases | Database Management System (DBMS) - Computer Science Engineering (CSE)Clustered index sorted according to first name (Search key)
      (a) Primary Indexing: This is a type of Clustered Indexing wherein the data is sorted according to the search key and the primary key of the database table is used to create the index. It is a default format of indexing where it induces sequential file organization. As primary keys are unique and are stored in a sorted manner, the performance of the searching operation is quite efficient.
      (ii) Non-clustered or Secondary Indexing
      A non clustered 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. Data is not physically stored in the order of the index. Instead, data is present in leaf nodes. For eg. the contents page of a book. Each entry gives us the page number or location of the information stored. The actual data here(information on each page of the book) is not organized but we have an ordered reference(contents page) to where the data points actually lie. We can have only dense ordering in the non-clustered index as sparse ordering is not possible because data is not physically organized accordingly.
      It requires more time as compared to the clustered index because some amount of extra work is done in order to extract the data by further following the pointer. In the case of a clustered index, data is directly present in front of the index.
      Indexing in Databases | Database Management System (DBMS) - Computer Science Engineering (CSE)(iii) Multilevel Indexing
      With the growth of the size of the database, indices also grow. As the index is stored in the main memory, a single-level index might become too large a size to store with multiple disk accesses. The multilevel indexing segregates the main block into various smaller blocks so that the same can stored in a single block. The outer blocks are divided into inner blocks which in turn are pointed to the data blocks. This can be easily stored in the main memory with fewer overheads.
      Indexing in Databases | Database Management System (DBMS) - Computer Science Engineering (CSE)
The document Indexing in Databases | Database Management System (DBMS) - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Database Management System (DBMS).
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
62 videos|66 docs|35 tests

Top Courses for Computer Science Engineering (CSE)

FAQs on Indexing in Databases - Database Management System (DBMS) - Computer Science Engineering (CSE)

1. What is indexing in databases?
Ans. Indexing in databases is a technique used to improve the speed and efficiency of data retrieval operations. It involves creating a separate data structure, called an index, which contains a subset of the data from the main database table. This index allows for faster searching and sorting of data based on specific columns or fields.
2. Why is indexing important in databases?
Ans. Indexing is important in databases because it significantly improves the performance of data retrieval operations. By creating indexes on frequently queried columns, the database can quickly locate the desired data without having to scan the entire table. This leads to faster query execution times and enhances the overall efficiency of the database system.
3. How does indexing work in databases?
Ans. Indexing works by creating a separate data structure, known as an index, which contains a subset of the data from the main database table. This index is typically stored in a separate file or memory structure. When a query is executed, the database engine uses the index to quickly locate the relevant data based on the specified search criteria. This avoids the need for a full table scan and significantly speeds up the data retrieval process.
4. What are the different types of indexes in databases?
Ans. There are several types of indexes commonly used in databases, including: 1. B-tree index: This is the most common type of index, suitable for range queries and equality searches. 2. Hash index: This type of index is efficient for exact match queries but not suitable for range queries. 3. Bitmap index: It is suitable for columns with a small number of distinct values and is commonly used in data warehousing. 4. Clustered index: This type of index determines the physical order of data in a table and is particularly useful for improving the performance of frequently used queries. 5. Non-clustered index: Unlike clustered indexes, non-clustered indexes do not determine the physical order of data and are typically used for improving query performance on columns that are not frequently updated.
5. How can I create an index in a database?
Ans. To create an index in a database, you need to use specific SQL statements or commands provided by the database management system (DBMS) you are using. Generally, you would use the CREATE INDEX statement followed by the name of the index, the table name, and the column(s) on which the index is to be created. The DBMS will then create the index and associate it with the specified table, improving the performance of data retrieval operations on the indexed column(s).
62 videos|66 docs|35 tests
Download as PDF
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

study material

,

Extra Questions

,

past year papers

,

Sample Paper

,

ppt

,

mock tests for examination

,

Indexing in Databases | Database Management System (DBMS) - Computer Science Engineering (CSE)

,

Free

,

Semester Notes

,

Summary

,

shortcuts and tricks

,

Important questions

,

practice quizzes

,

Viva Questions

,

Indexing in Databases | Database Management System (DBMS) - Computer Science Engineering (CSE)

,

video lectures

,

Objective type Questions

,

Exam

,

MCQs

,

pdf

,

Indexing in Databases | Database Management System (DBMS) - Computer Science Engineering (CSE)

,

Previous Year Questions with Solutions

;