Indexing

Indexing

An index is a data structure that supports efficient retrieval of "certain types of tuples" from a table.

We'll have this index structure, which is indicated by the blue cloud here and it will be able to navigate through it to find pointers to data items that have particular values for a particular attribute or couple of attributes.

If we don't have an index and we're looking for the student_ID is 12345, then we would need to scan the entire table. If this is sitting in memory and the table is sorted, then binary search would be an option as well, but it turns out that binary search doesn't completely translate over to our context here.

Problem

We want to find records of a certain type quickly.

Equality Queries

$$\left.\sigma_{\mathrm{ssn}}=619441789 \text { (Employees }\right)$$

We might have equality queries where we're trying to select from the employees table the person whose Social Security Number or some particular value is 619441789.

Range Queries

We also might have queries where we're looking for all of the records where some attribute is within some range. For example, selecting from employees, the ones whose age is greater than or equal to 10 and less than or equal to 20.

$$\sigma_{10}<=\text { age }<=20 \text { (Employees) }$$

AND and OR or several such conditions

Furthermore, we might have conditions that are Boolean combinations of these basic conditions. For example, I want to find employees whose ages in some range and salary is in some range, and so forth.

We'd like to be able to do selections and joins more efficiently, and index can help processing some of these kinds of queries fasters.