This site's Spatial category holds eleven entries, but only eight are compared below. Interval Tree's own opening line draws the boundary itself: "Three of this site's other Spatial entries — KD-tree, Quadtree, R-tree — answer questions about points or rectangles sitting in 2D space. An interval tree answers a related but genuinely different question, in one dimension" — given a pile of ranges (meeting times, IP blocks, chromosome coordinates), which of them overlap a query range? That's a real, related trade (build once, query often, the same shape every entry below shares) but over one-dimensional ranges, not 2D points or rectangles, so it sits outside the comparison below entirely, the same way the Range Query guide sets aside Binary Heap before comparing the five entries that do share a question.
BSP Tree sits outside the comparison for a different reason: it doesn't index a dataset for later "what's near X" queries at all. Its own opening line draws that boundary just as directly: "every other Spatial entry on this site... indexes the data itself, whether by splitting on the data's own median, a fixed region of space, or a sorted interleaved-coordinate key, and answers the same kind of question... A BSP tree splits on something else entirely — the input geometry's own lines — and answers a genuinely different question: in what order do these possibly-overlapping surfaces need to be drawn so that nearer ones correctly paint over farther ones, seen from any viewpoint?" There's no nearest-neighbor or range-overlap query anywhere in that — it's a visibility-ordering structure, useful when the same static geometry gets viewed from a moving, unpredictable position (a player walking through a level), not when a fixed dataset gets queried by many different search rectangles or query points.
Hilbert Curve sits outside the comparison for a third reason, different from both Interval Tree's and BSP Tree's: it answers the exact same "which points are near X" question the remaining six share, but its own Pitfalls section shows the naive way to answer that question with it — porting Z-order Curve's own corner-to-corner range-query trick verbatim — produces real false negatives, not just a slower correct answer. It isn't folded into the funnel below because its own most defensible use (Hilbert R-tree bulk-loading order) isn't really a competing answer to the below's "which structure do I query" question at all.
The remaining eight — KD-tree, Quadtree, R-tree, Range Tree, Ball Tree, VP-Tree, Z-order Curve, and Spatial Hash Grid — all index a fixed dataset once so that many later queries stay cheap, but they split on exactly what they index, how strong a guarantee they make about it, whether a coordinate system exists to split on at all (Ball Tree, VP-Tree), and whether they build a tree at all (Z-order Curve and Spatial Hash Grid alone don't).
The first fork is the data itself. R-tree's own opening states it plainly: "This site's other two Spatial entries — the KD-tree and the Quadtree — both index individual points... A lot of real spatial data isn't points at all, though — buildings on a map, sprite bounding boxes in a game, the footprint of a geometric feature. An R-tree indexes rectangles directly, and it builds its tree a different way entirely." If what you're indexing has real width and height — not a single coordinate — R-tree is the only one of the four built for it, and nothing past this question matters: its own "Where R-trees show up" section names the deciding factor as "data that's naturally rectangular (or has a cheap rectangular bounding approximation) rather than data that's naturally a single coordinate — the case a KD-tree or quadtree already covers well." Range Tree's own page agrees from the other side: "R-tree solves a different problem outright (indexing existing rectangles rather than points, built bottom-up for disk-friendly access) rather than trading the same space-versus-guarantee axis" the other three compete on. The cost of that different build (bottom-up grouping into minimum bounding rectangles instead of top-down space partitioning) is that sibling regions can overlap, which the other three never allow — R-tree's own Pitfalls section measures this directly: a 40-rectangle stress tree found 7 of 136 possible sibling-leaf-MBR pairs actually overlapping, "about 5% of all pairs, from ordinary random placement, no adversarial input required" — real, measured extra query work, but never a correctness cost, since "pruning only ever throws away a subtree once its MBR is proven not to overlap the query, never based on a guess."
For the rest of this guide, the data is points, not rectangles — which is exactly where KD-tree, Quadtree, and Range Tree all compete for the same job: "which points fall inside this rectangle," in Range Tree's own words. Its own page draws the line for when to reach for it, and there's no cleaner way to state it than to quote that page directly: "KD-tree and Quadtree both cost less space (O(n)) and are simpler to build, and do fine on typical data — reach for a range tree specifically when the worst case matters, not just the average, since both of those structures' own Pitfalls sections show real inputs that push them well past their average-case bound." That guarantee — O(log² n + k) query time "no matter how the points are distributed" — is real and measured on adversarial input: Range Tree's own Pitfalls section built a tree over 5,000 collinear points, the exact adversarial shape that made KD-tree visit 11× more nodes than a random set of the same size, and found 9.28 canonical subtrees visited on average — "against log₂(5000) ≈ 12.29, and effectively identical to the 9.29 measured over 5,000 uniformly random points." The guarantee isn't free: Range Tree spends O(n log n) space instead of O(n), because every point is copied into every ancestor's y-sorted array on its path to the root — measured directly at 15.69× the point count at n=100,000. If a worst-case bound is the actual requirement — a service that can't tolerate an occasional slow query, not just a slow average — that space cost is the trade being made for it.
If the worst case doesn't need a hard guarantee, both KD-tree and Quadtree do fine on typical data at O(n) space, and the choice between them comes down to what kind of query dominates and who else needs to agree on the same regions.
Nearest-neighbor is the query, not a rectangular range? That's KD-tree's and Ball Tree's shared territory — both are built and demonstrated around exactly that question, but they split from different raw material. KD-tree's own page frames itself around 2D coordinates: "a KD-tree is what you build when the same point set needs to answer many nearest-neighbor or region queries," and its "Where KD-trees show up" section names nearest-neighbor classification in machine learning, proximity checks in games and physics engines, and ray-tracing acceleration structures. Ball Tree's own opening draws the actual dividing line: "Every point-indexing structure on this site so far... builds its split from the points' coordinates... A Ball Tree builds its entire structure out of nothing but pairwise distances — no axis, no threshold, no coordinate is ever inspected on its own." If there's a real coordinate system to split on — an ordinary 2D point set with an axis-aligned sense of "less than" — reach for KD-tree; its own page's stress test shows the common "ball trees do better in high dimensions" reasoning isn't a reason to reach past it even when dimensionality climbs, since a direct comparison found "a naive axis-cycling tree clearly beat the ball tree at every dimension tested except one" (Ball Tree's own Complexity section). Reach for Ball Tree instead only when there genuinely isn't a coordinate system available at all — an arbitrary distance function like string edit distance, great-circle distance, or an embedding-similarity score — which is exactly its own stated reason to exist, not a dimensionality argument.
No coordinate system available, and the tree's depth needs a guarantee, not just a
heuristic? That's where VP-Tree splits from Ball
Tree, despite answering the identical question. Its own opening states the mechanism difference
directly: "a ball tree anchors each split with two far-apart points and a computed centroid; a VP-tree
anchors it with exactly one point pulled straight from the data... and splits everything else by
whether it's closer than or farther than the median distance to that single point." Median-by-count
means the split is always half the remaining points on each side, so depth is always
⌈log₂ n⌉ — VP-tree's own page measures this directly against Ball Tree on
adversarial clustered-plus-outlier input and finds Ball Tree running 30-60% deeper at every size tested,
not just in theory. Reach for Ball Tree when a heuristic
split is good enough and its own two-anchor scheme happens to fit the data well; reach for VP-Tree when the data might be adversarial and a depth bound
that holds regardless matters more than which specific heuristic produced it.
Not nearest-neighbor — do independent systems need to compute the exact same region boundary without sharing tree state? That's Quadtree's own decisive case, in its own words: "The fixed, coordinate-derived quadrant boundaries matter here specifically because two separate systems (a renderer and a physics engine, say) can independently compute the same region boundary for the same coordinates without sharing tree state — a KD-tree's data-dependent median split can't offer that, since the split points depend on insertion history." A quadtree's split point is always the region's own geometric center, computable from coordinates alone; a KD-tree's split point depends on which points happen to be in the tree, so two systems building "the same" KD-tree independently aren't guaranteed to agree on where a boundary falls.
Neither of those applies — a plain range query over points, one owner, no cross-system agreement needed? Both structures work about equally well on typical data here, so the honest tiebreaker is which adversarial shape your data is more likely to hit. KD-tree's own Pitfalls section shows its pruning nearly stops working when the data has near-zero variance along an axis — "even if every point shares the same y coordinate... the average nodes visited per nearest-neighbor query is 20.1 for the random set versus 222.5 for the collinear one." Quadtree's own Pitfalls section shows the mirror-image failure for points that cluster at or near identical coordinates: a fixed-center split "never separates two points that share one exact coordinate," recursing until floating-point precision underflows the box width, and even with the max-depth guard that stops the crash, "the finished tree has a single leaf holding all 500 points" and degrades to a linear scan. If your data is more likely to line up along an axis, Quadtree's split doesn't care where the values sit; if it's more likely to cluster at near-identical coordinates, KD-tree's median-based split still keeps dividing by position in sorted order rather than getting stuck. Neither risk being obviously more likely than the other is a legitimate answer too — the two structures are close enough here that either is a reasonable default.
Every entry above — including Range Tree's extra y-sorted arrays — is still a pointer
tree someone has to write, own, and keep balanced. Z-order Curve answers the identical "which points fall
inside this rectangle" question with no tree whatsoever: interleave each point's coordinate bits into
one Morton code, sort, and query with an ordinary binary search over a flat array. Its own page states
the actual reason to reach for it plainly: "a Morton code turns a 2D... indexing problem into an
ordinary 1D sorting problem, which means it can piggyback on infrastructure that already exists rather
than requiring new pointer-based tree code" — a plain sorted array, a database column with an ordinary
B-tree index, or a distributed key-value store with no notion of 2D space at all. That's a real,
different reason to choose it than anything above; it isn't a faster or more guaranteed way to answer
the same query, it's a way to answer it without writing (or maintaining) any of the tree code the other
entries require. The honest cost is scan waste, not a wrong answer: the same page measures a
literal-Morton-range scan touching 34.36× as many candidates as it actually matches
for an arbitrarily-placed query rectangle, against a clean 1.00× (zero waste) for an
identically-sized rectangle that happens to align with the curve's own power-of-2 grid — a real,
data-independent tax that KD-tree, Quadtree, and Range Tree never pay, in exchange for needing no
bespoke tree at all.
Spatial Hash Grid reaches the same no-tree destination by a different road, and the choice between the two comes down to how often the data changes. Z-order Curve still needs a full re-sort of the flat array to reflect a moved point — its own tree-free trick is a sorted-order trick, and sorted order doesn't survive a single-element move for free. Spatial Hash Grid's own opening states the difference directly: "every tree-based entry on this site's own Spatial category can restructure around dense regions... A grid's cells never split, because they were never built from the data in the first place" — which is exactly why insert, update, and delete are all O(1) for it, something neither Z-order Curve nor any tree-based entry above offers. The trade for that: no data-adaptivity at all. Z-order Curve degrades gracefully (more scan waste, never a wrong answer, no matter how the points cluster); Spatial Hash Grid's own Pitfalls section measures a fixed cell size touching all 300 points on every query once they cluster into a tenth of one cell's width, against an average of 1.05 touched for the same count spread uniformly — a query cost with no structural ceiling if the cell size doesn't match the data. Reach for Z-order Curve when the data is close to static and reusing existing sorted-storage infrastructure matters most; reach for Spatial Hash Grid when the data moves constantly (every frame, in a game or simulation) and a roughly-uniform density is a safe bet.
| Entry | Indexes | Query | Space | Reach for it when |
|---|---|---|---|---|
| R-tree | rectangles | O(log n + k) typical, degrades toward O(n) under MBR overlap | O(n) | data has real extent, not a single coordinate |
| Range Tree | points | O(log² n + k), guaranteed worst case | O(n log n) | the worst case must be bounded, not just the average |
| KD-tree | points | O(log n) avg, O(n) worst case (axis-degenerate data) | O(n) | nearest-neighbor is the query, typical case is fine, coordinates exist |
| Ball Tree | anything with a distance function | O(log n) avg, O(n) worst case (overlapping balls) | O(n) | nearest-neighbor is the query, no coordinate system exists to split on |
| VP-Tree | anything with a distance function | O(log n) avg, O(n) worst case, depth always O(log n) | O(n) | same as Ball Tree, but the depth bound must hold no matter how the data clusters |
| Quadtree | points | O(log n + k) avg, O(n) worst case (clustered data) | O(n) | regions must be independently addressable across systems, typical case is fine |
| Z-order Curve | points | O(log n + scanned), scanned up to 34x k on an unaligned rectangle | O(n) | reuse an existing sorted store/B-tree/key-value index — no bespoke tree at all |
| Spatial Hash Grid | points | O(k + cells checked) typical, degrades toward O(n) under clustering | O(n) | data moves constantly and O(1) update matters more than a worst-case guarantee |