Data structure (most commonly a binary tree) that enables fast and efficient storage, manipulation, and querying of large amounts of spatial data (points in space). Commonly used by particle systems.
Common types:
- Quadtree - each node has exactly four children
- Octree - each node has exactly eight children
- k-d tree
- R-tree
Related topics:
- k-nearest neighbhor (knn) search
- Spatial database on Wikipedia
- Binary space partitioning on Wikipedia
Articles:
- Spatial index section on Wikipedia article for Spatial database
Videos: