# Index Structures

## Various types of indexes

### 1. Clustered (Primary) or Unclustered (Secondary)

This refers to whether the data in the underlying table is **sorted** according to the attribute that we're in the indexing.

### 2. Sparse or Dense

That has to do with whether we have a index entry for every single record in the table, or in the case of dense if we only have index entries for some of them it's sparse.

* If it's dense, every record in the data file or every value of the attribute in question that we're looking for such as Social Security Number in the data file is listed in the index.&#x20;
* Sparse means that we don't list all of the values. But we have some way of finding the unlisted values based on some of the ones that are listed in the index.

### 3. Single Key or Composite or Multi-Dimensional

Whether we're looking at just a single attribute in our index say, is it just an index on ages of people or is it on multiple attributes we could index on, say age and zip code. If we expect to have a lot of queries where we're looking for people with a particular age within some range and a ZIP code.

*There are contexts such as geographical information systems where we might have two or higher dimensional data sets for example. We might want efficient ways of finding a point on a plane or a city on map. However, we're not covering for such multidimensional data here.*

## Different data structures to implement indexes

### Tree Structures

They're a class of **ordered indices** in which we're taking advantage of ordering on the data that. For example, one age is less than another age numerically, or one name is less than another name in alphabetical order.

### Hashing

Different family of indexes that does not rely on the order among elements is a hash table. We don't use any kind of comparison and we are only looking for equality among things.

## Index entries

### An index entry is a pair of key and pointer

**Keys** could be a value of some tuple of attributes like age and zip code that we're going to be searching for. **Pointers** are telling us which block on the disk that the record for that lives in. Actually the pointers might not be a physical pointer like that. There's usually some more indirection that we'll have some kind of an identifier called **record ID** telling us how to find the record on the disk that has the particular key value that we're looking for. Every object in our database is going to have a record ID.

### Index Construction

* Make an index entry for each tuple in the table
* Insert index entries into index structures (B+ tree, Hash Table)

The index is going to be based on the values that are in the table at the time that we build the index. So we'll have an entry for every element that's in the table. If we do insertions into the table, we want to update the index as well, and if we do deletions from the table we want to update the index.

### Example: schema is (age, name) with index on age

1. For example, we'll have the record (8, Tom) and we're going to convert into a an index entry that has the **key** 8 and a **pointer** to the record for (8, Tom).
2. We'll take all of those index entires and put them into some kind of an index structure.

<figure><img src="https://2448120900-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FwmvqVCPWQy9OzOB0fBrv%2Fuploads%2FaKmOc6fzF5qs04oS9h2Y%2Fimage.png?alt=media&#x26;token=978916d0-f467-4286-8246-cf7162aa7f2e" alt=""><figcaption></figcaption></figure>

In this kind of structure was assuming that this works if our key values are unique. If there were Social Security Numbers, that would be a realistic assumption.

<details>

<summary>Sneak Peek at Query Processing</summary>

### How much data we're reading in?

The data is in a table on the disk and the indices are in some blocks on the disk, but we need to read everything into main memory or RAM before we can work.

Note: **block** is a smallest unit of data transferred often 4K bytes (8 sectors).

```sql
SELECT fname, lname FROM Person WHERE ID = 12345
```

<img src="https://2448120900-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FwmvqVCPWQy9OzOB0fBrv%2Fuploads%2FK6FS2xYcxPgYGjDY7wdQ%2Fimage.png?alt=media&#x26;token=b3dbde19-0d72-4fa2-88dd-f1349c244a7c" alt="" data-size="original">

Now, assume that the data table is stored on the disk in contiguous blocks and within the data file, various file layouts are possible.

**If we're not using an index**, we would have one random access (seek time) plus rotational latency to find the first block. If there's blocks of data in the `Person` table, then we will need to **transfer all of blocks**.

</details>

## Basic Setup

> We're not going to be reorganizing the data as part of building the index.

<figure><img src="https://2448120900-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FwmvqVCPWQy9OzOB0fBrv%2Fuploads%2FhdReDOVr5RdNTOYTcuKP%2Fimage.png?alt=media&#x26;token=b30c0899-ab15-4f07-86b7-d3c58683c8ca" alt=""><figcaption></figcaption></figure>

### Types of Data Structures Used

We're just separating out the index **leafs at the end** if it's a B+ tree, if it was a hash table, it would be the key values and pointers **in the buckets** of the hash table. But we actually need another level of indirection before we can get to the data in the case that we have multiple values for an attribute.

For example, we're looking for the name of a person who has a particular Social Security Number. The Social Security number would be used to navigate our way through the index, and then we'll go down to the actual data table (db relation) to find that record and find the person's name.

In which case the picture would still look a lot like above, but *beneath the leaves* we would have something like where we'd have a bucket of pointers to everybody whose age is 6.

### Index vs. File Organization:

> What we're going to be looking at is an index organization that's separate from the file.

You could use it either as an index where the data is the actual data with the other attributes in each record is stored in a separate file, or you could also use this as a way of organizing the actual data table file.

<figure><img src="https://2448120900-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FwmvqVCPWQy9OzOB0fBrv%2Fuploads%2FsLhFCKFdmOjv2xllSRjJ%2Fimage.png?alt=media&#x26;token=ca7df38c-796e-4cf9-b711-ab00f8f112de" alt=""><figcaption><p>We assume index organization.</p></figcaption></figure>

* Index organization where our data table is sitting on the disk in a bunch of contiguous blocks. Index is typically scattered around in some other blocks on the disk. We have to get down to navigate through the index to the leaf level and follow a pointer to the data that we're looking for.&#x20;
* The other option is to actually have the data, in other words, the other attributes as well as the ones that we are keying in living in the tree along with index for navigating to find the right leaf.

## **Where is the index stored?**

If the index is small enough, it could be stored in memory. But the realistic examples, the index is also going to be stored on the disk. Furthermore, it's going to be spread out over the disk where blocks that are not contiguous.

## Index Evaluation Metrics

* Access time
* Insertion time
* Deletion time
* Space overhead
