This is Tree-Based Multi-Dimensional Index Structure

Idea:

- for $k$-dimensional space
- each node corresponds to a $k$-dimensional cube
- for 2D it's a square region

Algorithm

- if a number of points in a cube is larger that can fit in a block
- then we create an interior node
- and divide the cube recursively (i.e. we create 4 children for each quadrant)
- otherwise we create a leaf block

Lookups, Insertions and Deletions are very similar to kd-Trees

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