--- title: 'Spatial Indexes' source: 'https://academia.sh/en/courses/in-memory-stores/spatial-indexes' course: 'In-Memory Stores and Caching Systems' language: en updated: '2026-08-23T07:00:44+00:00' license: 'CC BY-SA 4.0' --- # Spatial Indexes Building a proximity query with an in-memory structure: the same query solved with a flat scan, a cell bucket, and a spatial-keyed sorted set, the extra bytes each of the three structures holds and the candidates scanned per query measured, and what being able to choose the grain at query time costs counted out. Because the stream's id is sortable, the question "everything after now" was a position lookup, not a search. The library has one more question, and it has no natural ordering: a reader wants the loan and return points within one kilometer of where they stand. Every way of sorting a two-dimensional position along a single axis pushes some neighbors far apart; neither a sorted set nor a stream answers this question directly. The solution is to split the plane into cells and write a **spatial key** for every point. How the cell size is chosen is not this lesson's subject; that decision was measured and given in the Case Studies course, in the Data-Intensive Systems topic, in the Location-Based Service case. Here the grain is an **input**, and the question asked is different: which structure builds the same proximity query in an in-memory store, how many bytes extra does that structure hold, and how many candidates does it save from being eliminated in return. ## Spatial Key The key is produced by interleaving the bits of two coordinates: each axis is quantized to sixteen bits, the bits are placed alternately, and the result is a single thirty-two-bit number. This layout has one useful property: every point in a cell shares the key's **leading bits**, so the cell is a **contiguous range** in a sorted array. How many bits are shared determines the grain — the first twelve bits give a 1 km cell, the first sixteen bits give a 0.25 km cell. | Code | Assumption | Value | Rationale | |---|---|---|---| | DS18 | loan and return point | 120,000 | branch, return box, school, and station points | | DS19 | region | 64 × 64 km | a single metropolitan area; the plane approach is a model simplification | | DS20 | base record | 20 bytes | position pair 16 bytes, point id 4 bytes | | DS21 | query radius | 1 km and 0.25 km | walking distance and a building's perimeter | DS21 is this lesson's deciding assumption: with a single radius, two of the three structures would be indistinguishable. ## Three Structures The setup places the same 120,000 points into three separate structures and asks the same 300 queries of all of them. Byte counts are read from the buffers' own size; the hash tables' cost is read from a formula visible in the code. ```js // spatial.mjs — the same proximity query with three in-memory structures: flat scan, cell // bucket, and a spatial-keyed sorted set. Byte counts are read from buffers and an open formula. // The region is modeled as a 64x64 km plane; points are clustered, the seed is visible. const N = 120_000, SIDE = 64, QUERIES = 300, SEED = 20260731, CLUSTERS = 24; let d = SEED; const rand = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d); t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; }; const centers = Array.from({ length: CLUSTERS }, () => [rand() * SIDE, rand() * SIDE]); const point = () => { // 35% uniform, 65% around a cluster if (rand() < 0.35) return [rand() * SIDE, rand() * SIDE]; const [mx, my] = centers[Math.floor(rand() * CLUSTERS)]; const a = rand() * 2 * Math.PI, r = -Math.log(1 - rand()) * 2.5; return [Math.min(SIDE - 1e-9, Math.max(0, mx + r * Math.cos(a))), Math.min(SIDE - 1e-9, Math.max(0, my + r * Math.sin(a)))]; }; const px = new Float64Array(N), py = new Float64Array(N), pid = new Int32Array(N); for (let i = 0; i < N; i += 1) { const [x, y] = point(); px[i] = x; py[i] = y; pid[i] = 100000 + i; } const BASE = px.byteLength + py.byteLength + pid.byteLength; const spread = (v) => { v = (v | (v << 8)) & 0x00ff00ff; v = (v | (v << 4)) & 0x0f0f0f0f; v = (v | (v << 2)) & 0x33333333; v = (v | (v << 1)) & 0x55555555; return v >>> 0; }; const quantize = (u) => Math.min(65535, Math.floor((u / SIDE) * 65536)); const key = (x, y) => ((spread(quantize(y)) << 1) | spread(quantize(x))) >>> 0; // 32-bit spatial key const p2 = (n) => { let k = 1; while (k < n) k *= 2; return k; }; const rawKey = new Uint32Array(N), order = new Int32Array(N); // sorted set: key + member id for (let i = 0; i < N; i += 1) { rawKey[i] = key(px[i], py[i]); order[i] = i; } order.sort((a, b) => rawKey[a] - rawKey[b]); const sortedKey = new Uint32Array(N); for (let i = 0; i < N; i += 1) sortedKey[i] = rawKey[order[i]]; const SCORE_TABLE = p2(2 * N) * 8; // member -> score hash table, slot 8 bytes const SORTED = sortedKey.byteLength + order.byteLength + SCORE_TABLE; const BIT = 6, SHIFT = 2 * (16 - BIT); // 2^6 = 64 cells/axis, cell 1 km const buckets = new Map(); for (let i = 0; i < N; i += 1) { const h = Math.floor(rawKey[i] / 2 ** SHIFT); if (buckets.has(h)) buckets.get(h).push(i); else buckets.set(h, [i]); } const filled = buckets.size; const BUCKET = p2(2 * filled) * 12 + filled * 8 + N * 4; // slot 12 + array metadata 8 + member 4 const queries = Array.from({ length: QUERIES }, point); const fmt = (x) => x.toLocaleString("en-US", { maximumFractionDigits: 2 }); const near = (q, i, R) => (px[i] - q[0]) ** 2 + (py[i] - q[1]) ** 2 <= R * R; const lowerBound = (v) => { let l = 0, r = N; while (l < r) { const m = (l + r) >> 1; if (sortedKey[m] < v) l = m + 1; else r = m; } return l; }; function run(R, bit) { // cells covering the query box const c = SIDE / 2 ** bit, k = Math.ceil(R / c), shift = 2 * (16 - bit); let flatCand = 0, flatMatch = 0, bucketCand = 0, bucketMatch = 0, ssCand = 0, ssMatch = 0, ranges = 0; for (const q of queries) { for (let i = 0; i < N; i += 1) { flatCand += 1; if (near(q, i, R)) flatMatch += 1; } const cx = Math.floor(q[0] / c), cy = Math.floor(q[1] / c); for (let dy = -k; dy <= k; dy += 1) for (let dx = -k; dx <= k; dx += 1) { const x = cx + dx, y = cy + dy; if (x < 0 || y < 0 || x >= 2 ** bit || y >= 2 ** bit) continue; const h = ((spread(y) << 1) | spread(x)) >>> 0; if (bit === BIT) { // cell bucket only knows its own grain for (const i of buckets.get(h) ?? []) { bucketCand += 1; if (near(q, i, R)) bucketMatch += 1; } } const lo = h * 2 ** shift, hi = lo + 2 ** shift; // contiguous range in the sorted set ranges += 1; for (let j = lowerBound(lo); j < N && sortedKey[j] < hi; j += 1) { ssCand += 1; if (near(q, order[j], R)) ssMatch += 1; } } } return { flatCand: flatCand / QUERIES, flatMatch: flatMatch / QUERIES, bucketCand: bucketCand / QUERIES, bucketMatch: bucketMatch / QUERIES, ssCand: ssCand / QUERIES, ssMatch: ssMatch / QUERIES, ranges: ranges / QUERIES, c }; } console.log(`model: ${fmt(N)} points, ${SIDE}x${SIDE} km, ${CLUSTERS} clusters, ${QUERIES} queries, seed ${SEED}`); console.log(`density ${fmt(N / SIDE ** 2)} points/km2, filled cells ${fmt(filled)} (at 1 km granularity)\n`); console.log("structure".padEnd(30) + "base bytes".padStart(12) + "index bytes".padStart(12) + "per member".padStart(15) + "total".padStart(12)); for (const [label, ext] of [["flat scan (array)", 0], ["cell bucket, 1 km cell", BUCKET], ["spatial-keyed sorted set", SORTED]]) console.log(label.padEnd(30) + fmt(BASE).padStart(12) + fmt(ext).padStart(12) + (ext / N).toFixed(2).padStart(15) + fmt(BASE + ext).padStart(12)); console.log("\ncandidates scanned per query (same 300 queries, same radius)"); console.log("radius".padEnd(10) + "cell".padStart(9) + "cells".padStart(7) + "flat".padStart(10) + "bucket".padStart(9) + "s.set".padStart(9) + "matches (flat/bucket/s.set)".padStart(29)); for (const [R, bit] of [[1, BIT], [0.25, BIT], [0.25, 8]]) { const s = run(R, bit), k = bit === BIT; console.log(`${R} km`.padEnd(10) + `${SIDE / 2 ** bit} km`.padStart(9) + s.ranges.toFixed(0).padStart(7) + fmt(s.flatCand).padStart(10) + (k ? fmt(s.bucketCand) : "-").padStart(9) + fmt(s.ssCand).padStart(9) + `${s.flatMatch.toFixed(2)} / ${k ? s.bucketMatch.toFixed(2) : "-"} / ${s.ssMatch.toFixed(2)}`.padStart(29)); } ``` ``` model: 120,000 points, 64x64 km, 24 clusters, 300 queries, seed 20260731 density 29.3 points/km2, filled cells 4,096 (at 1 km granularity) structure base bytes index bytes per member total flat scan (array) 2,400,000 0 0.00 2,400,000 cell bucket, 1 km cell 2,400,000 611,072 5.09 3,011,072 spatial-keyed sorted set 2,400,000 3,057,152 25.48 5,457,152 candidates scanned per query (same 300 queries, same radius) radius cell cells flat bucket s.set matches (flat/bucket/s.set) 1 km 1 km 9 120,000 821.22 821.22 372.25 / 372.25 / 372.25 0.25 km 1 km 9 120,000 821.22 821.22 40.90 / 40.90 / 40.90 0.25 km 0.25 km 9 120,000 - 97.39 40.90 / - / 40.90 ``` These numbers are in the **measurement** class; the candidate and match counts depend on the seed and the clustering parameters, the byte counts do not — they are buffer sizes. The last column says the same thing on every row: all three structures find the same matches — 372.25 at 1 km, 40.90 at 0.25 km. The index is not an approximation, it is a **pre-filter**; the exact distance is computed separately for every candidate, and no structure ever misses a result. ## What the Extra Bytes Buy All three structures carry the same 2,400,000-byte base record; the difference is in the **index bytes** column. The cell bucket adds 5.09 bytes per member and cuts the candidates scanned per query from 120,000 to 821.22 — a hundred and forty-six times fewer. This is the cheapest gain in the lesson: for 611,072 bytes, 99.3 percent of the query cost disappears. The sorted set gains nothing on the same query. At 25.48 bytes per member — five times the cell bucket's cost — it scans the exact same 821.22 candidates on the 1 km query. Read on its own, this row makes the sorted set a poor choice. Where the extra bytes go can also be counted: of the 3,057,152 bytes, 2,097,152 — 68.6 percent — is the hash table from member id to key. This table is held not for querying but for **updating**. When a mobile library stop moves, the member's old position in the sorted array has to be found; without the table, that means scanning the index. If points never moved, the sorted set's overhead would drop from 25.48 bytes per member to 8 — in that case only three bytes of the cell bucket would be the expensive one. ## If the Grain Is Chosen at Query Time The second and third rows show the difference. When a reader asks about a building's perimeter — 0.25 km — the cell bucket still scans 821.22 candidates: the buckets were built at insertion time for a 1 km grain, and asking a finer question still returns the same nine-square-kilometer area. Asking for a finer grain means rebuilding every bucket. In the sorted set, because the key carries the full thirty-two bits, **every prefix length is a valid range**. Asking the same 0.25 km query using the first sixteen bits drops the scanned candidates to 97.39: eight times less work for the same 40.90 matches. What the sorted set buys is not savings on candidates — it is the ability to **choose the grain at query time rather than at insertion time**. This settles the three structures into a decision table. A flat scan holds zero extra bytes and touches a hundred twenty thousand records on every query; it is the right choice if the point count stays under a few thousand. A cell bucket is the cheapest index when the query radius is fixed, eliminating 99.3 percent of candidates for 5.09 bytes. A spatial-keyed sorted set earns its 25.48 bytes when the radius changes from query to query or points relocate; on a fixed-radius, static set, those bytes go to waste. ## Summary - The spatial key produces a single sortable number by interleaving two coordinates' bits; a cell thereby becomes a contiguous range in the sorted array, and the prefix length determines the grain. - All three structures return the same result: 372.25 matches at 1 km, 40.90 at 0.25 km. The index is a pre-filter, not an approximation, and the exact distance is computed separately for every candidate. - The cell bucket is the lesson's cheapest gain: for 5.09 bytes per member, candidates scanned drop from 120,000 to 821.22, meaning 99.3 percent of the query cost disappears. - The sorted set wants 25.48 bytes per member and gains nothing on a query at its own grain; 68.6 percent of those bytes is a hash table held not for querying but for updating a member's position. - What the extra bytes buy shows up once the radius changes: on a 0.25 km query the cell bucket scans 821.22 candidates, the sorted set 97.39, because the grain is chosen at query time rather than insertion time. ## Next Step The proximity query returns a list, and the work does not end there. Once a reader picks a point from the list, the library has to do all of the following: read the copy count at that point, check the reader's open-loan limit, decrement the copy count by one, add the record to the loan set, and write an entry to the activity stream. Every structure so far can make **one** of these steps atomic; nothing has made all five atomic at once. When the steps are sent one at a time, another reader can slip in and take the same copy in between. The next lesson builds this multi-step work in two forms and counts the difference as the number of round trips, the race window, and blocked time.