29 - Indexes

Physical Database Design

• Primary file organization

  • Unsorted

  • Sorted

  • Hashed

• Auxiliary access structures (Indexes)

  • Single-level indexes

  • Multilevel indexes (B+ trees)

  • Hash indexes

  • Bitmap indexes

A page in a database can contain one or more rows of the database. Pages from a table can be stored anywhere on a disk, meaning that they may be scattered on the disk or right next to each other. In order to retrieve this data, we must access the hard disk.

Index Basics

Why Use an Index?

What if you want to retrieve a record where key = some value? Instead of reading the entire file until the value is found, it would be nice if we had a pointer to that employee, record, and document.

Indexes are also useful when performing joins in the relational model.

Indexes allow us to improve performance by minimizing the amount of data read and the number of disk accesses.

What Is an Index?

An index is itself an ordered file. The index file is physically ordered on disk by the key field. The index file has records of fixed length, containing a key field Ki and a pointer to the data Pi: <Ki, Pi>.

Single Level Index Files

Primary Index

Primary indexes have the index on the ordering key field of an ordered file of records.

Ki represents the value of the primary key for the first record in a block.

Pi represents the physical address of a block (or page).

Clustering Index

Clustering indexes index on the ordering field that is not a key field.

Secondary Index