Indexing Structures in Databases

Indexing Structures for Files and Physical Database Design

• Indexing is used to speed up record retrieval based on specific search criteria.
• Indexing structures provide secondary access paths.
• Any field can be used to create an index.
• Indexes are usually defined on one field but can be on multiple fields.
• A single-level index is an auxiliary file that enhances record retrieval efficiency in data files.
• A single-level index structure usually contains entries with <field value, pointer to record>, ordered by field value.
• Most indexing structures use tree data structures to organize the index.
• Index file size is typically smaller than the data file size because index entries are smaller.
• Binary searches on the index quickly locate pointers to the desired data records.
• Indexes can be categorized into dense or sparse (non-dense).

Dense vs. Sparse Index

• A dense index has an index entry for every search key value in the data file.
• In a dense index, every data record has a corresponding entry in the index.
• A sparse index, on the other hand, has index entries for only some of the search key values.
• Sparse indexes skip some search key values and only include entries for specific values, often the starting record of a block in the data file.

Types of Single-Level Ordered Indexes

• Primary Index: The index is built on the primary key field, which uniquely identifies each record in the data file. Primary indexes are used when records must be retrieved strictly in sorted order, and the field used as the primary key will uniquely identify each record in the data file.
• Clustering Index: Used efficiently when many records have the same value for the ordering field. It creates an index based on the non-key field, with one index entry for each distinct value. The index entry points to the first data block containing the records having that non-key field value.
• Secondary Index: Provides secondary access paths, independent of the primary key. Secondary indexes can use any non-ordering field in the data file and accommodate duplicate entries.

Primary Index

• Ordered file with two fields: Primary key and pointer to a specific disk block.
• It defines an index based on an ordered data file.
• The data file is ordered on a key field.
• Each entry in the index file maps a unique primary key value to the disk block address that contains the corresponding record.
• One index entry exists for each block in the indexed data file. The index entry holds the key value for the first record within that block (the block anchor).
• It is a nondense index—it doesn't include an entry for every possible search value, but merely the anchor record's key.

Clustering Indexes

• Ordered file with two fields: Non-key field and pointer to a disk block.
• It is built on a non-key field.
• The data file is ordered on a non-key field, unlike a primary index, where records must have unique values.
• One index entry exists for every unique non-key field value, and points to the first data block containing records with that value.
• Insertion and deletion operations are straightforward in clustering indexes.

Secondary Indexes

• Provides secondary means of accessing files for which primary access exists.
• Secondary indexes are ordered files with two fields: a non-key field and a pointer.
• The data file can be ordered or unordered.
• Secondary indexes can be built on non-key fields with unique or duplicate values.
• They typically use more storage space and take more time to search than primary indexes.
• Multiple secondary indexes are possible for the same data file (on different fields).

Multilevel Indexes

• Multilevel indexes are created by indexing the index itself, resulting in multiple levels of indexes. This optimizes the search time significantly when data is huge.
• Each level of a multilevel index (except the base level) is a primary index of the preceding level.
• The process is repeated until the top-level index fits within one disk block.
• Multilevel indexes are generally employed when the size of the index in the initial level is large.
• Dynamic multilevel indexes (like B-trees, and B+ -trees) are designed to efficiently handle insertions and deletions in the index without compromising the tree structure's balance.

Dynamic Multilevel Indexes (B-Trees and B+-Trees)

• B-trees and B+-trees are dynamic multilevel indexes that self-adjust to insertions and deletions of records, maintaining a balanced structure.
• In B-trees, pointers to data records can occur at any level.
• In B+-trees, data pointers are exclusively located at the leaf node level.
• B-Trees and B+-Trees provide balanced structures, allowing fast insertion and deletion of records, while preventing leaf nodes from exceeding maximum capacity.