Department of CSE
COURSE NAME: DATABASE MANAGEMENT SYSTEM
COURSE CODE : 24AD2104R
Topic : INDEX IN DBMS
Session -
AIM OF THE SESSION
To introduce and explain the concept of Indexing in Database Management Systems (DBMS), its
types, functionality, and how it improves query performance and efficiency.
INSTRUCTIONAL OBJECTIVES
This Session is designed to identify different types of indexing (e.g., single-level, multi-level,
clustered, non-clustered) and illustrate how indexing improves search operations.
LEARNING OUTCOMES
At the end of this session, students will be able to apply indexing techniques to optimize database
queries.
INDEX INTRODUCTION
What is Indexing in DBMS?
Indexing is a technique for improving database performance by reducing
the number of disk accesses necessary when a query is run.
Indexes are organized data structures that allow quick searching based on
key values. When an index is created for a database table, it maintains a
sorted order of key values along with pointers to the actual data rows.
This process significantly reduces the number of disk accesses required to
fulfill a query.
Structure of index in DBMS
Structure of index in DBMS
Here, Search Key contains the copy of the Primary Key or the Candidate Key of the database
table. Generally, we store the selected Primary or Candidate keys in a sorted manner so that
we can reduce the overall query time or search time(from linear to binary).
Data Reference contains a set of pointers that holds the address of the disk block. The
pointed disk block contains the actual data referred to by the Search Key. Data Reference is
also called Block Pointer because it uses block-based addressing.
Indexing types
indexing_1.webp
Primary Index
Primary Index
Primary indexing refers to the process of creating an index based on the
table’s primary key. These primary keys are specific to each record and
establish a 1:1 relationship between them.
The searching operation is fairly efficient because primary keys are stored
in sorted order.
There are two types of primary indexes: dense indexes and sparse
indexes.
Dense Index
Dense Index
In dense index, there is an index record for every search key value in the
database.
This makes searching faster but requires more space to store index records
itself.
Index records contain search key value and a pointer to the actual record on
the disk.
Dense Index example
Sparse Index
In sparse index, index records are not created for every search key.
An index record here contains a search key and an actual pointer to the
data on the disk.
To search a record, we first proceed by index record and reach at the actual
location of the data.
If the data we are looking for is not where we directly reach by following
the index, then the system starts sequential search until the desired data is
found.
Sparse Index
Clustered Indexing
Clustered indexing is a technique where multiple related records are stored together
in the same file. This helps reduce the cost of searching because related data is kept
close to each other.
In clustered indexing, the data is stored in an ordered file, usually based on a non-key
field. This ordering can be based on a primary key or, in some cases, a non-primary key.
When an index is created on non-primary key columns, which may not be unique, the
solution is to combine two or more columns together to form a unique value. This
combination is then used to create the index.
Clustered Indexing
Clustered indexing works by grouping records with similar properties
together. For example, students can be grouped by their semester, such as
first-semester, second-semester, and so on.
By grouping related records together, it becomes faster to retrieve them
because the index allows for quicker identification and search of the data.
Clustered Indexing
ezgifcom-gif-maker-(3).webp
ezgifcom-gif-maker-(3).webp Non-clustered or Secondary
Indexing
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.
ezgifcom-gif-maker-(3).webp Non-clustered or Secondary
Indexing
Example:
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.
Non-clustered or Secondary
Indexing
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.
Non-clustered or Secondary
Indexing
Multilevel Index
Multilevel Index
Advantages of Indexing
ezgifcom-gif-maker-(3).webp
•Indexing helps in faster query results or quick data retrieval.
•Indexing helps in faster sorting and grouping of records
•Some Indexing uses sorted and unique keys which helps to retrieve sorted queries even faster.
•Index tables are smaller in size so require lesser memory.
•As Index tables are smaller in size, they are stored in the main memory.
•Since CPU speed and secondary memory speed have a large difference, the CPU uses this main
memory index table to bridge the gap of speeds.
•Indexing helps in better CPU utilization and better performance.
REFERENCES
Reference book :
1. Fundamentals of Database System-Elmasri Ramez , Navathe Shamkant
2. "Database Management Systems" by Raghu Ramakrishnan and Johannes Gehrke -
This book covers the basics of database management systems, including the concept
of index structures.
Terminal QUESTIONS
1. Explain the concept of indexing in DBMS. How does indexing
improve the performance of a database system? Illustrate with an
example.
2. Differentiate between clustered and non-clustered indexes. Explain
with diagrams and suitable examples.
3. Discuss the types of indexing techniques in DBMS. Compare B-Tree
and Bitmap indexing with advantages and disadvantages.
THANK YOU
Team – DBMS
