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)$


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


Other Types

Hash-Based Multi-Dimensional Indexes

Tree-Based Multi-Dimensional Indexes