Multidimensional Indexes

A multidimensional index organizes records described by two or more attributes so that a query engine can efficiently answer two families of queries beyond simple equality lookup. A region query (also called a window query or range query) asks for all records whose attribute vector lies inside a given box, circle, or polygon. A nearest-neighbor (NN) query asks for the record(s) closest to a given point under some distance metric, typically Euclidean distance. Both queries are ubiquitous in geographic information systems, computer-aided design, computer vision (nearest neighbors in feature space), and any relational query with a `WHERE` clause that constrains several correlated columns at once. The fundamental obstacle is that a total order, the mechanism a B+-tree relies on, does not exist in more than one dimension in any way that preserves proximity. You can linearize a plane by scanning row by row, but two points that are close in 2-D (say, diagonally adjacent) can be arbitrarily far apart in the linearization. Multidimensional structures instead partition the data space directly, using geometric objects — grid cells, half-space splits, or minimum bounding rectangles (MBRs) — as the unit of indexing. A search then walks the structure, discarding any partition whose geometry cannot intersect the query region; this is called spatial pruning, and it is the multidimensional analogue of a B+-tree's ability to skip subtrees whose key range excludes the search key. Three structures dominate the classical curriculum. The grid file is a direct generalization of extendible hashing to multiple dimensions: a coarse grid divides space into cells, and a directory maps each cell to a disk bucket, allowing the grid lines to be spaced non-uniformly to absorb data skew. The k-d tree is a binary tree that recursively bisects the data space, alternating the splitting dimension at each depth; it is simple, elegant, and excellent as a main-memory structure but less naturally suited to disk pages. The R-tree generalizes the B+-tree by making each internal entry a bounding rectangle enclosing all the geometry beneath it in the tree; unlike a B+-tree's key ranges, sibling MBRs in an R-tree are allowed to overlap, which is the source of both its flexibility and its central algorithmic challenge.

Grid files

A grid file partitions the domain of each indexed dimension into intervals, forming a grid whose cells are grouped into disk buckets via a directory. Unlike a fixed uniform grid, the dividers themselves adapt: when a bucket overflows, the system can split a grid line, which affects an entire row or column of cells rather than a single cell, keeping the directory structured as a full grid rather than an unbalanced tree. ``` GRID-FILE-SEARCH(query_point q): // Locate the cell containing q using the linear scales for each dimension for each dimension d: i_d = LINEAR-SCALE-LOOKUP(scale[d], q[d]) // O(log n_d) via binary search bucket = directory[i_1][i_2]...[i_k] return SCAN(bucket) // one disk I/O (usually) GRID-FILE-INSERT(record r): bucket = GRID-FILE-SEARCH(r.key) if bucket has space: insert r into bucket else: // split the bucket: choose a dimension, insert a new grid line pick dimension d to split (e.g., round-robin or by variance) insert new boundary value into scale[d] redistribute directory pointers (may double directory along d) redistribute records between old and new bucket ``` A region query (a bounding box) is answered by computing the range of grid indices the box overlaps in each dimension, then visiting every bucket in that sub-grid — an operation that costs one I/O per bucket touched, with buckets outside the query box never visited.

k-d trees

A k-d tree is a binary search tree over points in $k$-dimensional space. Each internal node stores a splitting dimension and a splitting value; it partitions its subspace into two half-spaces, sending points with a smaller coordinate to the left child and the rest to the right. The splitting dimension cycles with depth (dimension 0 at the root, dimension 1 at depth 1, dimension 0 again at depth 2, and so on for 2-D; more generally `depth mod k`). ``` KD-INSERT(node, point p, depth): if node is null: return new leaf storing p d = depth mod k if p[d] < node.splitValue: node.left = KD-INSERT(node.left, p, depth+1) else: node.right = KD-INSERT(node.right, p, depth+1) return node KD-RANGE-SEARCH(node, box, depth): if node is null: return {} result = {} if node.point is inside box: result.add(node.point) d = depth mod k if box.min[d] <= node.splitValue: result += KD-RANGE-SEARCH(node.left, box, depth+1) if box.max[d] >= node.splitValue: result += KD-RANGE-SEARCH(node.right, box, depth+1) return result KD-NEAREST-NEIGHBOR(node, target, depth, best): if node is null: return best if distance(node.point, target) < distance(best, target): best = node.point d = depth mod k (near, far) = (node.left, node.right) if target[d] < node.splitValue else (node.right, node.left) best = KD-NEAREST-NEIGHBOR(near, target, depth+1, best) // only descend into the far side if its region could still // contain a closer point than the current best if |target[d] - node.splitValue| < distance(best, target): best = KD-NEAREST-NEIGHBOR(far, target, depth+1, best) return best ``` The nearest-neighbor pruning rule — comparing the distance to the current best against the distance to the splitting hyperplane — is the crux of why k-d trees can beat a linear scan: an entire subtree is skipped whenever its bounding hyperplane is already farther away than the best answer found so far.

R-trees

An R-tree is a height-balanced tree, structurally similar to a B+-tree, in which every entry (internal or leaf) is paired with a minimum bounding rectangle (MBR). A leaf entry pairs an MBR with a pointer to (or the coordinates of) an actual data object; an internal entry pairs an MBR with a pointer to a child page, and that MBR tightly encloses the MBRs of everything in the subtree below it. Unlike B+-tree key ranges, MBRs of sibling entries may overlap, because two disjoint rectangles at one level can both legitimately need to enclose overlapping geometry beneath them. Every node holds between $m$ and $M$ entries (parameters analogous to a B+-tree's fanout bounds, with $m \le \lceil M/2 \rceil$), except the root, which may hold fewer than $m$. ``` RTREE-SEARCH(node, queryBox): result = {} if node is a leaf: for entry in node.entries: if entry.MBR intersects queryBox: result.add(entry.object) else: for entry in node.entries: if entry.MBR intersects queryBox: result += RTREE-SEARCH(entry.childPage, queryBox) return result RTREE-INSERT(root, object o): leaf = CHOOSE-LEAF(root, o.MBR) if leaf has room: add (o.MBR, o) to leaf else: (leaf1, leaf2) = SPLIT-NODE(leaf, o) propagate split upward, adjusting/creating parent entries if root itself split: create new root with two children // update MBRs of all nodes on the insertion path so they // tightly enclose their (possibly enlarged) children ADJUST-TREE(leaf-to-root path) CHOOSE-LEAF(node, mbr): if node is a leaf: return node // pick the child entry requiring least MBR enlargement // to include mbr; break ties by smaller resulting area best = argmin over entries e of ENLARGEMENT(e.MBR, mbr) return CHOOSE-LEAF(best.childPage, mbr) ``` Insertion mirrors a B+-tree: descend to a leaf, insert, split on overflow, and propagate splits upward, possibly growing the tree by one level at the root. The R-tree-specific step is CHOOSE-LEAF, which must decide which subtree to descend into using a geometric heuristic (least MBR enlargement) rather than a simple key comparison, and SPLIT-NODE, which must partition entries into two groups whose bounding boxes are small and preferably non-overlapping — a combinatorial optimization problem, usually solved heuristically (the classic quadratic-cost split picks the two "most different" seed entries and grows two groups greedily).

Grid files. Locating the bucket for a point takes $O(\log n_d)$ time per dimension via binary search on that dimension's scale (or $O(1)$ with an array offset if scales are stored densely), so a point query costs $O(k \log n)$ CPU work plus one disk I/O to fetch the bucket — matching a B+-tree's single-page point lookup when data is uniformly distributed. A region query touches every bucket overlapping the query box; in the worst case this is proportional to the volume of the query box relative to cell size, which is efficient for small, localized queries but can degrade for large or thin diagonal query regions that clip many cells. The directory itself, however, can grow superlinearly in the number of records under skewed data: splitting one grid line to fix one crowded bucket affects an entire hyperplane of cells, potentially creating many nearly-empty buckets elsewhere. This is the grid file's chief weakness — directory size is not guaranteed to stay proportional to $n$ under adversarial or highly skewed distributions.

k-d trees. For $n$ points inserted in reasonably random order, expected tree height is $O(\log n)$, giving expected $O(\log n)$ point lookup and $O(\sqrt n + t)$ expected time for orthogonal range queries in 2-D (more generally $O(n^{1-1/k} + t)$ in $k$ dimensions), where $t$ is the output size — the classical result for range trees restricted to axis-aligned k-d partitioning. The intuition: at each level, roughly half the subtree is pruned by the query box unless the box straddles the splitting hyperplane, and the number of "boundary" nodes that must be visited on both sides grows sublinearly. Nearest-neighbor search has expected $O(\log n)$ cost for uniformly distributed data in low dimensions, using the pruning test `|target[d] - splitValue| < distance-to-best` to skip subtrees whose entire region lies farther than the current best candidate. The correctness of this pruning rule follows directly from the triangle inequality: if every point in a subtree's region is provably farther from the target than the current best distance, no point in that subtree can improve the answer. The major caveat is that a plain k-d tree built by naive sequential insertion is only balanced in expectation; adversarial insertion orders (e.g., sorted input) can produce $O(n)$ height, degrading every operation to linear time, and there is no simple local rebalancing analogous to a B+-tree's split/merge — rebuilding the whole tree is the usual remedy. k-d trees also do not natively map to fixed-size disk pages the way B+-trees and R-trees do, which is why disk-resident spatial systems favor R-trees.

R-trees. Because an R-tree is height-balanced with fanout bounded between $m$ and $M$, tree height is $O(\log_m n)$, exactly like a B+-tree, giving $O(\log_m n)$ disk I/Os in the best case for a point/small-region query. The catch is that R-tree sibling entries can overlap, so a query may need to descend into multiple children at each level whose MBRs intersect the query box — worst-case search cost is therefore $O(n)$ if overlap is severe (imagine every leaf's MBR covering the whole space), though well-tuned insertion heuristics (minimizing enlargement and overlap at split time) keep real-world performance close to $O(\log_m n + t/B)$, where $t$ is the result size and $B$ is the page capacity. Insertion and deletion cost $O(\log_m n)$ node visits for the base descent, plus $O(M)$ work per level to run the split heuristic on overflow, matching B+-tree insertion asymptotically while adding a constant-factor overhead for the geometric split computation. Correctness invariant: at every level, the MBR stored with an entry must tightly contain the union of all geometry in the subtree below it; `ADJUST-TREE` maintains this invariant bottom-up after every insertion, and it is precisely this invariant that makes `RTREE-SEARCH`'s pruning step sound — if a query box does not intersect a node's MBR, it provably cannot intersect anything stored beneath that node.

The curse of dimensionality. All three structures share a fundamental limitation as the number of indexed dimensions $k$ grows. Query regions that are small relative to the whole space in each dimension can still occupy a large fraction of the volume once $k$ is large — geometrically, a hypercube covering half the range in every one of $k$ dimensions covers only $(1/2)^k$ of the total volume, but bounding boxes built from real, correlated data tend to become nearly as "wide" as the whole domain in high dimensions because there is so much empty space between points. Practically, this means pruning becomes ineffective, sibling MBRs overlap heavily, and query cost degrades toward a full scan once $k$ exceeds roughly 10–20 for R-trees and k-d trees alike. This is not a bug in any particular implementation; it is an intrinsic geometric phenomenon, which is why very high-dimensional similarity search (e.g., embedding vectors with hundreds of dimensions) instead relies on approximate methods such as locality-sensitive hashing rather than exact multidimensional trees.

Consider inserting five 2-D points representing sensor stations, indexed by `(x, y)` coordinates, into an R-tree with maximum fanout $M = 3$ and minimum fanout $m = 2$:

After step 5 the tree has a root with two children, $L_1=\{p_1,p_2,p_5\}$ (MBR $[2,5]\times[2,7]$, now full at 3 entries) and $L_2=\{p_3,p_4\}$ (MBR $[8,9]\times[3,8]$). Now issue a range query: find all stations inside the box $[4,9]\times[4,9]$. 1. At the root, test the query box against both children's MBRs: $[2,5]\times[2,7]$ intersects $[4,9]\times[4,9]$ (they overlap in $x\in[4,5], y\in[4,7]$), and $[8,9]\times[3,8]$ also intersects. Both subtrees must be visited — this is the overlap cost inherent to R-trees. 2. Descend into $L_1$: check each point individually. $p_1=(2,2)$ fails ($x<4$); $p_2=(3,7)$ fails ($x<4$); $p_5=(5,5)$ passes (inside the box). Emit $p_5$. 3. Descend into $L_2$: $p_3=(8,3)$ fails ($y<4$); $p_4=(9,8)$ passes. Emit $p_4$. 4. Result: $\{p_5, p_4\}$, computed after two page fetches (one per leaf) rather than scanning all five records — the pruning was only partial here because the query box straddled both leaves' MBRs, illustrating the realistic middle ground between a lucky single-subtree hit and a full scan. Compare this to a k-d tree built on the same five points (splitting on $x$ at depth 0, on $y$ at depth 1): a query for the nearest neighbor to $(6,6)$ would descend toward $p_4=(9,8)$ or $p_5=(5,5)$ first depending on the split values chosen, compute the true distance to that candidate, and then use the hyperplane-distance test to decide whether the sibling subtree (containing $p_1,p_2,p_3$) could possibly hold something closer — in this small example it can prune that entire branch once it confirms $p_5=(5,5)$ is closer than the distance from $(6,6)$ to the splitting line, avoiding three additional distance computations.

Spatial and multidimensional indexes are load-bearing infrastructure wherever geometry meets scale. PostGIS (PostgreSQL's spatial extension), Oracle Spatial, and SQLite's R-Tree module all implement R-trees or R-tree variants as the primary access method for `ST_Intersects`, `ST_Contains`, and nearest-neighbor spatial queries; commercial GIS platforms such as Esri's ArcGIS rely on closely related bounding-volume hierarchies. Ride-sharing and delivery platforms use spatial indexes to answer "nearest available driver" queries in real time, and computer-aided design (CAD) and computer graphics systems use bounding-volume hierarchies — a close cousin of the R-tree — to accelerate collision detection and ray tracing. k-d trees remain the workhorse in-memory structure inside libraries like scikit-learn and OpenCV's FLANN for nearest-neighbor classification and feature matching, precisely because those workloads are small enough to fit in memory and low-dimensional enough to avoid the worst of the curse of dimensionality. Grid files, though less common in modern commercial systems, illustrate a design pattern — directory-based partitioning with adaptive cell splitting — that reappears in adaptive spatial partitioning schemes used in distributed spatial data processing frameworks. Choosing which of these structures (or none at all, favoring a scan) best fits a given workload's dimensionality, skew, and query mix is exactly the kind of tradeoff analysis formalized in Index Selection, and understanding these structures also deepens the general contrast between Clustered vs Unclustered Indexes when spatial data must be physically laid out on disk.

Ask the tutor: How do R*-tree split and insertion heuristics reduce MBR overlap compared to Guttman's original R-tree?