ITP55: Indexing

works in much the same way as the index in any textbook

index

play the same role as book indices in libraries.

Database system indices

are critical for efficient processing of queries in databases.

Indices

Based on a sorted ordering of the values.

Ordered Indices

Based on a uniform distribution of values across a range of buckets.

Hash Indices

The bucket to which a value is assigned is determined by a function

Hash Function

The types of access that are supported efficiently.

Access types

can include finding records with a specified attribute value and finding records whose attribute values fall in a specified range.

Access types

The time it takes to find a particular data item, or set of items, using the technique in question.

Access time

The time it takes to insert a new data item.

Insertion time

This value includes the time it takes to find the correct place to insert the new data item, as well as the time it takes to update the index structure.

Insertion time

The time it takes to delete a data item. This value includes the time it takes to find the item to be deleted, as well as the time it takes to update the index structure.

Deletion time

The additional space occupied by an index structure. Provided that the amount of additional space is moderate, it is usually worthwhile to sacrifice the space to achieve improved performance

Space overhead

an index structure where the search key values are stored in a sorted (ascending or descending) order, and each key value points to one or more records in the data file

Ordered Index (Sorted index)

The attribute(s) used for ordering and searching

Search key

Built on a sorted data file where records are ordered by the search key.

The index contains one entry per block of data, not per record.

The index key is the same as the file’s sorting key.

Primary Index (Clustering Index)

Built on a non-sorted data file.

The search key is different from the file’s ordering key.

Can have multiple secondary indices on the same table.

Secondary Index (Non-Clustering Index)

Used when records are physically ordered based on a non-key attribute that can have duplicate values.

Each entry in the clustering index represents a cluster (group) of records sharing the same value.

Clustering Index

an index entry appears for every search-key value in the file.

Dense Index

contains the search-key value and a pointer to the first data record with that search-key value.

Index Record

an index entry appears for only some of the searchkey values.

Sparse Index

can be used only if the relation is stored in sorted order of the search key; that is, if the index is a clustering index

Sparse Index

a sparse index of the basic index

Outer Index

the basic index file

inner index

If the search-key value does not appear in the index, the system inserts an index entry with the search-key value in the index at the appropriate position.

Dense indices

is an additional index structure built on a non ordering attribute to improve query performance for that attribute

secondary index

the data file is not sorted

secondary index

is a multi-level, balanced search tree structure that maintains sorted data and allows logarithmic-time search, insertion, and deletion operations

B+ Tree Index

It is a dynamic, ordered index — meaning it automatically adjusts its structure as data is inserted or deleted

B+ Tree Index

The top node of the tree

Root Node

Contain search keys and pointers to child nodes.

Guide the search toward the correct leaf.

Do not store actual data records

Internal Node

Contain search keys and pointers to actual data records (or blocks).

Are linked sequentially using pointers to form a linked list — making range queries efficient

Leaf Nodes

Built on an ordered data file (the data is physically sorted by the key).

The search key is the same as the file’s sorting key.

Efficient for both equality and range searches.

Primary B+ Tree Index

Built on a non-sorted attribute.

The data file is unordered, so index entries point to individual records.

Allows searching on non-primary attributes.

Secondary B+ Tree Index

is a database indexing technique that uses a hash function to quickly locate a record in a file.

Hash Index

organize data based on hash values — making them extremely fast for equality searches

Hash index

uses a hash function to compute the address (or bucket) of a record based on the search key

Hash index

is a storage unit that can hold one or more records having the same hash value.

Bucket

Converts a search key into a hash value

Hash Function

Groups or storage locations that hold records with the same hash value.

Buckets

In some schemes (like extendible hashing), a directory keeps track of bucket addresses dynamically

Directory

is a highly efficient indexing technique used in databases — especially for columns with a small number of distinct values

Bitmap Index

It represents data using bitmaps (bit arrays), making it extremely fast for query evaluation and combination using bitwise operations.

Bitmap Index

uses a bit array (0s and 1s) to indicate the presence or absence of a value in a given record (row).

bitmap index