Quad Trees

Quad Trees

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

Building

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

Operations

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

See also

• Binary Search Trees
• kd-Trees
• R-Tree
• Multi-Dimensional Indexes

Sources

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