Geo Indexes: Powered by Dragonfly Sorted Sets

In our previous post on bitmaps, we explored how Dragonfly implements a powerful Redis-compatible feature using a simple but flexible data structure: strings. This might have left you wondering: What other advanced data types are built from foundational ones?

Today, we’ll examine geospatial indexes. While they seem specialized, the implementation reveals a clever design: they’re powered by sorted sets. And since Dragonfly’s sorted sets rely on highly efficient B+ trees, you get performant geo queries with minimal overhead.

Let’s look at some examples of how geospatial indexes work and break down the underlying mechanics in this post.

Geospatial Commands in Action: Use Cases and Examples

Geospatial indexes unlock powerful location-based features with just a few commands. Let’s walk through how geospatial commands work together in a real-world scenario. Imagine we’re building a ride-sharing service like Uber or Lyft, and for simplicity, we’ll assume:

• Each city has its own geospatial index, such as drivers:sf, drivers:nyc, etc.
• We only focus on two core operations: adding drivers and finding nearby ones.

Adding Drivers to a City

When drivers start their shift, their app reports their location. We store them in a city-specific geospatial index:

# Command syntax: GEOADD key longitude latitude member

# San Francisco drivers.
dragonfly$> GEOADD "drivers:sf" -122.4194 37.7749 "driver:A"  # Downtown SF
dragonfly$> GEOADD "drivers:sf" -122.4133 37.7765 "driver:B"  # Nearby

# New York drivers.
dragonfly$> GEOADD "drivers:nyc" -74.0060 40.7128 "driver:X"  # Manhattan
dragonfly$> GEOADD "drivers:nyc" -73.9897 40.7411 "driver:Y"  # Brooklyn

Separating cities optimizes queries (e.g., no need to search drivers in New York City when a user is in San Francisco). Although a certain level of data preprocessing is needed, the goal is to optimize fast searches of local drivers in this example. Under the hood, each GEOADD encodes coordinates into a geohash value and stores it in a sorted set, which we will explore in more detail later.

It is also notable that in Dragonfly, Valkey, Redis, and many other database systems (such as PostgreSQL with the PostGIS extension), the conventional order for coordinates is longitude first, then latitude. This follows the standard X (horizontal) and Y (vertical) axis convention.

Finding Nearby Drivers

When a user in San Francisco requests a ride, we query only that city’s index:

# Find drivers within 5 km of Union Square (lng=-122.4074, lat=37.7879).
# We limit the results to the first 10 matching items by using 'COUNT 10'.
# Also, the command returns as soon as enough matches are found because of the 'ANY' option.
dragonfly$> GEOSEARCH "drivers:sf" FROMLONLAT -122.4074 37.7879 BYRADIUS 5 km COUNT 10 ANY

Dragonfly’s geospatial indexes (like our drivers:sf example) enable efficient range queries that filter location data in real-time, delivering fast and consistent response time for nearby-point lookups even under heavy load. This performance characteristic makes it critical for latency-sensitive applications like ride-sharing services, where response delays directly impact user satisfaction.

While we’ve focused on ride-sharing, these geospatial capabilities equally benefit other location-aware services like fleet management systems, logistics/delivery tracking, and location-based social features. Dragonfly’s geospatial commands specialize in efficient point-based proximity queries, making them ideal for nearby searches and basic distance calculations. Nonetheless, for more complex geospatial needs (such as polygon intersections, custom-shaped geofencing, or advanced geographic computations), a dedicated geographic information system (GIS) solution may be more appropriate.

Geospatial Index Internals: Bridging Coordinates to Sorted Sets

Geospatial commands might seem magical at first glance, but their power comes from a clever foundation. While specialized in purpose, their core operations align perfectly with sorted set functionality:

• Range Queries: Geospatial searches like GEOSEARCH fundamentally ask: "Find all points within this area." This mirrors sorted sets’ native ZRANGEBYSCORE operation, which efficiently retrieves elements within a specified value range.
• Ordered Storage: Geographic coordinates naturally benefit from sorting, as nearby locations should be stored contiguously for fast access. Sorted sets automatically maintain elements in order, enabling optimized proximity searches.

The elegance lies in the simplicity: by treating coordinates as sortable values, Dragonfly repurposes sorted sets’ existing capabilities to handle geospatial queries. Just as bitmaps reveal themselves to be strings in disguise, geospatial indexes are essentially sorted sets underneath.

Geohash Representation & Precision

Now a question could naturally come to mind: Sorted sets in Dragonfly use a single floating-point score for ordering, but geolocations require two values (longitude and latitude), so how do we encode both coordinates into one score while ensuring that nearby locations remain adjacent in the sorted set’s order?

It turns out that a public domain technique called Geohash is used. Geohash solves this problem by converting 2D coordinates into a 1D string (and ultimately a numeric score) that preserves spatial proximity. Let’s see what a geohash value looks like first. Continuing from our previous code snippets, the geohash value of a member within the drivers:sf index can be retrieved by the GEOHASH command:

dragonfly$> GEOADD "drivers:sf" -122.4194 37.7749 "driver:A"

dragonfly$> GEOHASH "drivers:sf" "driver:A"
#=> 1) "9q8yyk8ytp0"

We can see that the coordinates (lng=-122.4194, lat=37.7749) are represented by an 11-character string value, 9q8yyk8ytp0, using geohash text encoding. A geohash textual value can be up to 12 characters long, and the length of the geohash string determines the precision or granularity of the geographic location it represents. Here’s how geohash lengths correspond to different levels of precision:

• 1 character: Covers a vast area, such as a continent.
• 2 characters: Represents a smaller region, like a country.
• 3 characters: Corresponds to a large city or broad region.
• 4 characters: Refines the area to a town or small city.
• 5+ characters: Progressively narrows down to street-level precision or even exact coordinates.

For instance, a 6-character geohash might pinpoint a neighbourhood or landmark, while a 12-character geohash can specify a location within just a few meters.

Now that we know Dragonfly’s geospatial indexes use standard geohash representation and have high precision. Let’s see how geohash values are encoded.

How Geohash Encoding Works

Geohash text values use base-32 encoding, which includes digits 0-9 and letters b-z (excluding a, i, l, and o to avoid ambiguity) and requires 5 bits (2^5 = 32) to represent each character. To understand how geohashes refine locations, imagine the Earth divided into a 32-cell grid. The first character in a geohash pinpoints one of these 32 large cells. Each of these cells is further split into 32 smaller cells, and this recursive subdivision continues with each additional character, effectively “zooming in” to a more precise area.

Geohash Encoding & Precision

If we take a geohash text representation and convert it back to the binary format, the resulting binary sequence is actually interleaved bits for longitude and latitude, with longitude digits in even positions and latitude digits in odd positions. If we read the longitude and latitude binary sequences from left to right, they can be interpreted as follows:

• Longitude (−180° to +180°) and Latitude (−90° to +90°) were converted to binary via iterative division.
• For each bit, the range is split in half, and a 0 (lower half) or 1 (upper half) is assigned.

For instance, if we take a look at the first two characters in the ride-sharing service above for driver:A’s location 9q8yyk8ytp0:

• 9q can be converted to 01001 10110 in binary because:
• • The complete base-32 encoding sequence is 0123456789bcdefghjkmnpqrstuvwxyz.
  • 9 is simply 9 in the base-32 encoding sequence, and its binary value is 1001.
  • q is 22 in the base-32 encoding sequence, and its binary value is 10110.
• The longitude can be derived from the digits in even positions of 01001 10110, resulting in 00101.
• The latitude can be derived from the digits in odd positions of 01001 10110, resulting in 10110.

Reading the digits, we know that longitude value 00101 represents:

• 0 → (−180° to 0°), as the lower half of (−180° to +180°).
• 0 → (-180° to -90°), as the lower half of the previous.
• 1 → (-135° to -90°), as the upper half of the previous.
• 0 → (-135° to -112.5°), as the lower half of the previous.
• 1 → (-123.75° to -112.5°), as the upper half of the previous.

Similarly, for the latitude value 10110, we get:

• 1 → (0° to 90°), as the upper half of (−90° to +90°).
• 0 → (0° to 45°), as the lower half of the previous.
• 1 → (22.5° to 45°), as the upper half of the previous.
• 1 → (33.75° to 45°), as the upper half of the previous.
• 0 → (33.75° to 39.375°), as the lower half of the previous.

As demonstrated with our two-character example, the initial geohash 9q produces a relatively large coordinate range. This imprecision is expected when using shorter geohash strings. However, we can verify that our exact coordinates (lng=-122.4194, lat=37.7749) do indeed fall within this calculated bounding box, which essentially means that 9q8yyk8ytp0 is more precise than 9q. The key insight is that geohash strings and their binary representations are fundamentally equivalent—both implement the same recursive spatial partitioning, just using different encoding schemes. Whether expressed in base-32 characters or binary bits, each additional character or 5-bit binary further subdivides the 32-cell grid, progressively zooming in toward our precise location.

Storing in Sorted Sets

After breaking down geohash encoding, we can see how perfectly it maps to Dragonfly’s sorted set implementation. The key insight is that a geohash, whether in its base-32 string form or binary representation, ultimately can be encoded as an integer value that maintains precision and geographic ordering. This integer can be efficiently stored as the score component of a sorted set entry.

By translating geographic searches into score ranges, Dragonfly leverages its optimized sorted set implementation without specialized structures. The result is query performance that maintains all the geographic precision we carefully encoded while benefiting from Dragonfly’s existing high-performance architecture.

Conclusion: The Power of Dragonfly’s Geospatial Design

Geospatial indexes may seem complex, but as we’ve seen, they are implemented through an elegant combination of geohash encoding and sorted sets—proving once again that sophisticated features can be built on simple, robust foundations.

What makes Dragonfly stand out is its B+ tree-backed sorted set implementation. Unlike Redis or Valkey (which use skiplists), Dragonfly’s B+ trees deliver:

• Better memory efficiency (reduced overhead per entry)
• Higher throughput
• Consistent performance

Sorted Set Throughput: Redis v7 vs. Dragonfly with 1 Thread & 8 Threads

This architectural choice ensures that geospatial queries run with low latency and high throughput, even under heavy load. So the next time you use GEOADD or GEOSEARCH, remember: behind those simple commands lies a carefully engineered system that balances precision, speed, and efficiency. That’s the Dragonfly difference.

References

• Geohash | Wikipedia
• What is Geohashing? | by PubNub
• All You Need to Know About Geohash | by Quadrant