## Multi-Dimensional Indexes

### Typical Applications

## Typical Queries

### Point Query

Find all values for the (multi-dimensional) search key

- for product "TV" sold in Ireland with ALL for date
- does there exist a star on coordinate (10, 3, 5)

### Partial Match Queries

Not all values of a search key are specified

- return the coordinates pf all stars with $x=5$ and $z=3$

### Range Queries (Dicing)

- return all cube cells with date $\geqslant Q_1$ and date $\leqslant Q_2$ and sales $\leqslant 100$
- return coordinates of all stars with $x \geqslant 10$ and $20 \leqslant y \leqslant 35$

### Nearest-Neighbor Queries

- return closest 3 stars to a star at (10, 15, 20)

## Can Use One-Dimensional Indexes?

One-Dimensional Indexes (such as B-Tree)

- take one single key
- can use one key made of multiple attributes

Need to impose lexicographical order on keys in B-Tree to do that

### Hash Tables

For Hash-Based Indexes we need to compute Hash Function for tuples

- extend hash function: $h(x, y, z) = h_1(x) + h_2(y) + h_3(z)$

Problem

- cannot answer range queries at all
- age < 20
- sal < 30
- age < 20 and sal < 20
- all lead to linear scan

## Types

### Other Types

### Hash-Based Multi-Dimensional Indexes

### Tree-Based Multi-Dimensional Indexes

## Sources