Grokking Database Fundamentals for Tech Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Single Level Indexing
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Single-level indexing is a simple and direct method of organizing data to facilitate efficient retrieval. It maps index entries directly to the location of records in a database, making lookups faster and more structured. This indexing technique includes primary, secondary, and clustered indexes.

Below, we will explain each index type, along with relevant examples and illustrations to deepen your understanding.

Types of Single-level Indexing
Types of Single-level Indexing

Primary Index

A primary index is created on the primary key of a table, which uniquely identifies each record. It organizes the data in sorted order based on the indexed field and provides pointers to the physical location of the records.

Key Features

  • Records in the table must be physically sorted by the primary key.
  • Each record corresponds to a single index entry.
  • The primary index ensures efficient search and range queries.

Dense Index

A dense index contains an index record for every search key value in the database. Each index entry maps directly to a specific data record.

Example:

Consider a table with values {A, B, C, D, E, F, G, H} sorted by the primary key. For every key in the table, there is a corresponding entry in the dense index pointing to the location of the record.

The attached image illustrates the structure of a dense index:

  • For every search key value (e.g., A, B, C), there is an index record.
  • This setup ensures quick lookups for all values.
Dense Index
Dense Index

Sparse Index

A sparse index contains index records only for some of the values in the data file. Typically, it points to the first record of each block or page in the data file.

Example:

Using the same dataset {A, B, C, D, E, F, G, H}, a sparse index may only include entries for A, C, E, and G. These entries point to blocks containing the respective values.

The attached image illustrates the sparse index:

  • The index contains fewer entries, reducing storage space.
  • Each index entry points to a block of records, requiring sequential scans within the block to locate specific values.
Sparse iundex
Sparse iundex

Secondary Index

A secondary index introduces another layer of indexing for non-primary key fields. Unlike primary indexes, secondary indexes do not dictate the physical order of data. Instead, they provide an additional lookup mechanism for faster data retrieval.

How Secondary Index Works

Secondary indexing uses multiple levels of mapping to manage large datasets efficiently. By introducing an intermediate index, the database reduces the size of the mapping stored in memory, improving query performance.

Example

Secondary Index
Secondary Index

Suppose we are searching for a record with Roll = 121. The secondary index operates as follows:

  1. At the primary level (RAM), the index searches for the largest value less than or equal to 121. In this case, it locates 100
  2. At the secondary level (Hard Disk), it narrows the range further and locates 120 as the closest value less than or equal to 121.
  3. Using the pointer for 120, the database fetches the data block from memory and scans within the block to locate Roll = 121.

This hierarchical structure ensures efficient use of memory and accelerates the search process, even for large datasets.

Clustered Index

A clustered index arranges data physically in storage to match the order of the indexed column. Unlike other indexes, the clustered index organizes the actual data rows based on the index, making it highly efficient for range-based queries and group-based retrievals. It is commonly used for non-primary key columns by grouping related records, which share similar attributes.

How Clustered Index Works

A clustered index groups records with shared characteristics into clusters, and each cluster is indexed as a whole. When querying data, the database retrieves the entire cluster instead of scanning individual records.

Example

In a company’s database, employees are grouped by Dept_ID. For instance, all employees belonging to Dept_ID = 1 are stored together in one cluster. Similarly, employees in Dept_ID = 2 are stored in another cluster.

Clustered Index
Clustered Index

The diagram demonstrates:

  • A pointer for Dept_ID = 1 directs to all records associated with Department 1.
  • For Dept_ID = 2, another pointer directs to all relevant records grouped under that department.
  • Each cluster is stored in a dedicated disk block for faster access and logical separation.

This approach ensures that querying data for a specific department (e.g., all employees in Dept_ID = 3) is efficient, as the database accesses only the corresponding cluster.

Single-level indexing offers a straightforward way to organize data for efficient access. By leveraging primary, secondary, and clustered indexes, databases can significantly enhance query performance. Each type of index serves specific purposes, and understanding their structures and use cases is essential for designing optimized database systems.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible