This is Hash-Based Multi-Dimensional Index Structure

In each dimension, using *Grid Lines*, we divide our key space into *stripes*

- lines divide the space into subspaces that are large enough to store
*one block* - if needed, overflow blocks may be used

Each stripe points to some block on disk

- note that we have two empty buckets there, and don't have any pointers to actual blocks
- may allow for overflow blocks

- need to know values for each grid line
- so it's different from just applying a Hash Function
- we look at each component of the tuple and determine the position in the grid
- may add single-dimension index (such as B-Tree) for coordinates of each line to speed up finding the proper coordinate

- Locate the needed bucket
- if there is room - insert
- no room - two options
- Overflow blocks
- Split by creating new grid lines (hard)

Splitting

- causes additional problems:
- content of blocks is linked across dimensions
- so adding a grid line will split all the buckets along this line
- for $n$ dimensions we may choose which dimension to split

- Find the corresponding bucket
- delete the record
- reorganize if needed

Recall the typical of queries we want to answer for Multi-Dimensional Indexes

- (+) good support for
- point queries
- partial match queries (we know where to look to needed data)
- range queries

- (+) reasonable support for
- nearest neighbor queries (first look withing the bucket, then neighbor buckets and so on)

- (-) downsides
- many empty buckets when data is not uniformly distributed
- need to have a good algorithm that splits the space

- Database Systems Architecture (ULB)
- Database Systems: The Complete Book (2nd edition) by H. Garcia-Molina, J. D. Ullman, and J. Widom