Spatial Data Structures: Quadtrees and KD-Trees

Spatial data structures organize points, lines, and polygons for fast queries. They power maps, games, physics engines, and GPS.

The Problem

Given millions of points or rectangles, find:

• All points within a region (range query)
• The nearest point to a location (nearest neighbor)

Brute force: O(N) per query — too slow for large datasets.

Quadtree

Recursively divides 2D space into four quadrants.

Structure

                    root (entire space)
                   /    |    |    \
                 NW    NE   SW    SE
                 /      |     \    \
               ...     ...    ...  ...

Visual:
┌───────────┬───────────┐
│           │           │
│    NW     │    NE     │
│           │           │
├───────────┼───────────┤
│           │           │
│    SW     │    SE     │
│           │           │
└───────────┴───────────┘

Implementation

class Quadtree:
    def __init__(self, x, y, w, h, capacity=4):
        self.x = x          # Center x
        self.y = y          # Center y
        self.w = w          # Half-width
        self.h = h          # Half-height
        self.capacity = capacity  # Max points before split
        self.points = []
        self.divided = False
    
    def _subdivide(self):
        nw = Quadtree(self.x - self.w/2, self.y - self.h/2,
                      self.w/2, self.h/2, self.capacity)
        ne = Quadtree(self.x + self.w/2, self.y - self.h/2,
                      self.w/2, self.h/2, self.capacity)
        sw = Quadtree(self.x - self.w/2, self.y + self.h/2,
                      self.w/2, self.h/2, self.capacity)
        se = Quadtree(self.x + self.w/2, self.y + self.h/2,
                      self.w/2, self.h/2, self.capacity)
        self.nw, self.ne, self.sw, self.se = nw, ne, sw, se
        self.divided = True
    
    def insert(self, x, y, data=None):
        if not self._contains(x, y):
            return False
        
        if len(self.points) < self.capacity:
            self.points.append((x, y, data))
            return True
        
        if not self.divided:
            self._subdivide()
        
        return (self.nw.insert(x, y, data) or
                self.ne.insert(x, y, data) or
                self.sw.insert(x, y, data) or
                self.se.insert(x, y, data))
    
    def query_range(self, rx, ry, rw, rh, results=None):
        if results is None:
            results = []
        
        # If this node doesn't overlap query range, skip
        if not self._intersects(rx, ry, rw, rh):
            return results
        
        for px, py, data in self.points:
            if (rx - rw <= px <= rx + rw and
                ry - rh <= py <= ry + rh):
                results.append((px, py, data))
        
        if self.divided:
            self.nw.query_range(rx, ry, rw, rh, results)
            self.ne.query_range(rx, ry, rw, rh, results)
            self.sw.query_range(rx, ry, rw, rh, results)
            self.se.query_range(rx, ry, rw, rh, results)
        
        return results

Performance

KD-Tree (K-Dimensional Tree)

A binary tree that splits on alternating dimensions.

Structure

Split on x at median → Split on y → Split on x → ...

Level 0 (split by x):
    ├── Left (x < median)
    └── Right (x > median)

Level 1 (split by y):
    ├── Within each, split by y median
    └── ...

Level 2 (split by x again):
    ...

2D Visualization

First split (x=5):      Second split (y=3):  Third split:
    y|                      y|                   y|
   4 |   B       C          4 |   B       C      4 |   B  |    C
   3 | A              →     3 | A  |      →     3 | A  |  |
   2 |   D                 2 |   D |             2 |   D  |
   1 +---x                 1 +---x               1 +---x
      1 2 3 4 5 6             1 2 3 4 5 6           1 2 3 4 5 6

Implementation (Nearest Neighbor)

import numpy as np

class KDNode:
    def __init__(self, point, data=None):
        self.point = point
        self.data = data
        self.left = None
        self.right = None

class KDTree:
    def __init__(self, points, data=None):
        self.k = len(points[0]) if points else 0
        self.root = self._build(points, data, depth=0)
    
    def _build(self, points, data, depth):
        if not points:
            return None
        
        axis = depth % self.k
        sorted_indices = np.argsort([p[axis] for p in points])
        median = len(sorted_indices) // 2
        median_idx = sorted_indices[median]
        
        node = KDNode(points[median_idx],
                      data[median_idx] if data else None)
        
        left_pts = [points[i] for i in sorted_indices[:median]]
        left_data = [data[i] for i in sorted_indices[:median]] if data else None
        right_pts = [points[i] for i in sorted_indices[median+1:]]
        right_data = [data[i] for i in sorted_indices[median+1:]] if data else None
        
        node.left = self._build(left_pts, left_data, depth + 1)
        node.right = self._build(right_pts, right_data, depth + 1)
        
        return node
    
    def nearest_neighbor(self, query):
        best_dist = float('inf')
        best_node = None
        
        def search(node, depth):
            nonlocal best_dist, best_node
            if node is None:
                return
            
            axis = depth % self.k
            diff = query[axis] - node.point[axis]
            
            # Check this node
            dist = np.linalg.norm(query - node.point)
            if dist < best_dist:
                best_dist = dist
                best_node = node
            
            # Search the closer side first
            first = node.left if diff < 0 else node.right
            second = node.right if diff < 0 else node.left
            
            search(first, depth + 1)
            
            # Check if we need to search the other side
            if diff * diff < best_dist:
                search(second, depth + 1)
        
        search(self.root, 0)
        return best_node.point, best_node.data

KD-Tree vs. Quadtree

| Feature | KD-Tree | Quadtree | |

R-Tree

Tree for bounding rectangles (not just points). Used in real-world spatial databases.

Structure

(Root) Bounding box covering all children
    ├── Node: Bounding box A
    │   ├── Leaf: Rectangle 1
    │   ├── Leaf: Rectangle 2
    │   └── Leaf: Rectangle 3
    └── Node: Bounding box B
        ├── Leaf: Rectangle 4
        ├── Leaf: Rectangle 5
        └── Leaf: Rectangle 6

Used by: PostGIS, SQLite (R*Tree), Oracle Spatial.

Applications

Complexity Comparison

k = number of results returned.

Choosing the Right Structure

Spatial data structures turn geographic and geometric queries from linear scans into logarithmic searches.

Advanced Spatial Data Structures

R-Trees and Variants

R-trees are the most widely used spatial indexing structure in database systems. Each node in an R-tree represents a bounding box that encloses all geometries in its children. The tree is balanced and designed for disk-based storage, minimizing the number of node visits during range and nearest neighbor queries. The R*-tree variant improves split heuristics — forced reinsertion of entries from overflowing nodes tends to produce more compact bounding boxes. The R+-tree avoids overlapping bounding boxes at the same level by partitioning geometries, at the cost of potentially duplicating entries across sibling nodes. PostGIS, SQLite, and Oracle Spatial all use R-tree variants as their primary spatial index. Query performance on real-world geographic data is typically logarithmic in the number of indexed geometries.

Grid-Based Approaches

Uniform grids partition space into equal-sized cells, with each cell storing references to geometries that intersect it. Grids are simple to implement and provide efficient query for uniformly distributed data. The key design parameters are cell size — too large wastes query time scanning many candidates, too small wastes memory on empty cells and geometry duplication at boundaries. Adaptive grids address non-uniform distributions by recursively subdividing dense cells. The QTM (Quaternary Triangular Mesh) adapts grid subdivision to spherical coordinates, making it suitable for global geographic applications. Geohash encodes latitude and longitude into a string by recursively dividing the globe into quadrants — nearby points share prefixes, enabling proximity queries through simple string prefix matching.

Trade-offs and Selection

Choosing the right spatial data structure requires understanding the workload characteristics. K-d trees excel for static point data with nearest neighbor queries. R-trees handle both points and polygons equally well and support dynamic insertion and deletion. Grids are optimal for uniformly distributed data with predictable density. Quadtrees and octrees adapt to non-uniform distributions through variable resolution. For memory-constrained environments or disk-based storage, R-trees and their variants dominate. For in-memory analytics on point clouds, k-d trees provide the best query performance. For geospatial web applications where simplicity matters, geohash or grid-based approaches with a standard database index are often the most practical choice.

Frequently Asked Questions

What is the difference between spatial and spatiotemporal data structures? Spatial data structures index static geometry (coordinates, polygons) and support range queries and nearest neighbor search. Spatiotemporal data structures additionally index time — each geometry has a temporal dimension. Examples include trajectory indexing (moving objects), time-sliced R-trees (separate R-tree per time interval), and B-fraktal trees for temporal overlap queries.

How do spatial indexes handle 3D data? 3D spatial indexes extend the same principles with an additional dimension. Octrees replace quadtrees with 8 children per node. 3D R-trees use 3D bounding boxes. For time-varying 3D data, 4D indexing (3D + time) is possible but suffers from the curse of dimensionality — index performance degrades as dimensions increase.

Which spatial index is best for real-time applications? For real-time applications with frequent inserts and queries, R-trees provide balanced performance for both operations. Grid-based approaches offer simpler insertion at the cost of query efficiency. For applications requiring only nearest neighbor queries on static data, an in-memory k-d tree with n log n build time and log n query time is typically the fastest option.

Graph Algorithms Guide — Trees and Graphs Guide — Bloom Filters Guide