Spatial Data Structures
Spatial indexing structures for multi-dimensional data: k-d trees, R-trees, quadtrees, octrees, grid files, and space-filling curves (Z-order, Hilbert).
The data
Structures
| Name | Dimensions | Query time | Space | Description | Operations | Use cases | Notes |
|---|---|---|---|---|---|---|---|
| k-d Tree (k-dimensional tree) | Any k | O(n^(1-1/k)) average for nearest neighbor | O(n) | Binary tree alternating split axis at each level; partitions k-dimensional space |
|
| Not suitable for high dimensions (curse of dimensionality); best for k ≤ 20 |
| R-Tree | 2D/3D spatial | O(log n) average | O(n) | Balanced tree grouping nearby objects with minimum bounding rectangles (MBRs); optimized for disk storage |
|
| Variants: R*-tree (better split strategy), R+-tree (no overlap), STR-packed (bulk loading) |
| Quadtree | 2D | O(log n) average | O(n) | Recursive subdivision of 2D space into 4 quadrants; leaf nodes contain points or regions |
|
| Point quadtree (stores points) vs region quadtree (stores areas); unbalanced without care |
| Octree | 3D | O(log n) average | O(n) | 3D extension of quadtree; recursively subdivides space into 8 octants |
|
| Essential for 3D spatial partitioning; often combined with frustum culling for rendering |
| Grid File | 2D/low-dimensional | O(1) for exact match, O(k) for range | O(n + grid_size) | Uniform grid overlaying space; each cell points to objects within it |
|
| Simple but suffers from curse of dimensionality; cell size critically affects performance |
| Z-Order Curve (Morton Order) | Any k | O(log n) with B-tree | O(n) | Maps multi-dimensional points to 1D by interleaving binary representations; preserves locality |
|
| Can use standard B-tree/B+-tree on Z-values; locality preservation not as good as Hilbert curve |
| Hilbert Curve | 2D (extendable) | O(log n) with B-tree | O(n) | Space-filling curve with better locality preservation than Z-order; maps 2D to 1D continuously |
|
| More complex to compute than Z-order but significantly better spatial locality; used in Google S2 Geometry |
Fetch the same bytes
The static files are identical to what the API returns, but with no rate limit and no server round trip. Use the API when you want a query and a content type; use the files when you want to cache one document.
curl "https://yjtoon.com/api/dataset/spatial-data-structures?format=toon"
const res = await fetch( "https://yjtoon.com/static-data/dataset/spatial-data-structures.toon" ); const toon = await res.text();
Rate limit: 120 requests per minute per IP, no key and no signup. API reference →