The Problem with Traditional Indexes and Spatial Queries

THE PROBLEM

Let's say you're building an app called "Tomato" to help people find killer Indian Restaurants within 10km (or 6.2 miles) of them.

Normally, your first instinct is to throw a standard B-Tree index on your latitude and longitude coordinates.

CREATE TABLE restaurants (

    id        SERIAL PRIMARY KEY,

    name      VARCHAR(255),

    latitude  DECIMAL(10, 8),

    longitude DECIMAL(11, 8)

);



CREATE INDEX idx_lat ON restaurants(latitude);

CREATE INDEX idx_lng ON restaurants(longitude);

Looks totally fine, right?

But here's where it all falls apart. When you try to run a query to get restaurants within 10km of a specific lat and long, you're going to hit a wall.

-- 10 km radius. Conversions:

--   1° latitude  ≈ 111 km                 → 10 / 111             ≈ 0.0901° lat

--   1° longitude ≈ 111 km × cos(37.77°)   → 10 / (111 × 0.7906)  ≈ 0.1140° lng



SELECT id, name, latitude, longitude

FROM restaurants

WHERE latitude  BETWEEN 37.7749 - 0.0901 AND 37.7749 + 0.0901   -- 37.6848 .. 37.8650

  AND longitude BETWEEN -122.4194 - 0.1140 AND -122.4194 + 0.1140; -- -122.5334 .. -122.3054

You'll probably attempt a range scan on one of the indexes. If it grabs the latitude first, the index does its thing and spits out restaurants between the two latitudes.

But here's the catch: that latitude query returns a massive, wrap-around-the-globe strip of results, bringing in restaurants from Mexico, Dubai, and India all at once.

And as for longitude? It doesn't even do a range query. It drops to a painfully slow per-candidate scan and filter.

Even if you try to get clever and force an index intersection, the database still has to sweat through merging two giant sets of results.

And the best part.... Even if you pull off that intersection perfectly, you get a rectangle, not a true 10km radius circle. You still have to write extra math logic to shave off the corners and filter out the noise.

Links:

• 
  
  

  Links:

  
  
  
  
  
  
  

  • 
    
    

    Links:

    
    
    
    
    
    
    
    • The Original Paper: Guttman 1984 (PDF)
    
    
    
    
    

    
    
    
    TL;DR
    

    
    
    

    The Problem: Standard database indexes (B-Trees) are terrible at handling maps. They process latitude and longitude separately, so asking for a 10km radius usually hands you a useless, globe-spanning strip of data instead of a neat local circle.

    
    
    

    The Fix: You need a spatial index. They actually understand 2D space and keep physically close locations stored close together in the database. Here are the big three:

    
    
    
    
    
    • 
      Geohash: Flattens coordinates into a short text string, acting like a zip code. If two spots share the same starting letters, they're close. It's incredibly easy to drop into any standard database.
    
    
    • 
      Quadtree: Chops the map into four squares, and keeps subdividing squares only where things get crowded. It's awesome for scaling detail based on density, but it requires a custom setup rather than a standard index.
    
    
    • 
      R-tree: Draws snug, nesting boxes around natural clusters of points and completely ignores empty space. It's the heavy-hitting industry standard (used in PostGIS and MySQL), though inserting new data can be a bit heavy on database writes.
    
    
    Vollständiger Original-Bericht

    Ausführliche Details, Code-Beispiele & Hersteller-Stellungnahme auf dev.to.

    ↗ Original-Artikel auf dev.to lesen