Focus on not getting lost, together From Zero To Hero!

preface

It is believed that everyone has used taxi-hailing software, or used software to search for people and stores nearby, which cannot be done without location-based Service (LBS) applications. Such applications query nearby targets based on latitude and longitude, and Redis GEO is suitable for such scenarios.

The principle is introduced

Redis GEO is not a new data structure, but is implemented based on Sorted Set. We have learned Sorted Set structure in previous articles, which saves data in the form of key-score, that is, an element corresponds to a score value. By default, it is Sorted according to the score value, and range query can be carried out. But latitude and longitude is a data pair, such as (117.25, 40.60), so how does Redis convert latitude and longitude into score value? After the conversion into score value, how to ensure that the distance of the elements adjacent to the score value is also similar? All of this depends on GeoHash encoding.

The range of longitude is [-180,180], and the range of latitude is [-90,90]. When we encode longitude and latitude, we GeoHash the longitude and latitude respectively, and then combine them into one coding value. Let’s take a look at how GeoHash is encoded.

For longitude or latitude, GeoHash encodes it as a binary value of N equals, which is essentially a partition of N times, and N can be customized. Here’s the logic:

  1. First partition: we divide the longitude range [-180,180] into two intervals [-180,0) and [0,180], referred to as the left and right interval for short.

  2. The second partition: suppose the first one falls within the interval of [0,180], we divide the interval into two intervals [0,90) and [90,180], and then get a coding value of 0 or 1 according to the left and right interval.

    .

  3. After N repetitions, we have N code values. Same logic for latitude, you can get N coded values.

For a concrete example, given latitude and longitude [120,40], N=5.

Longitude 120:

Partition number Left interval The right range The interval of longitude 120 Code value
1 [- 180, 0) [0180] right 1
2 [0, living) [90180] right 1
3 (90135) [135180] On the left 0
4 [90112) [112.5, 135] right 1
5 [112.5, 123.75) [123.75, 135] On the left 0

Latitude 40:

Partition number Left interval The right range The interval of longitude 120 Code value
1 [- 90, 0) [0, living] right 1
2 [do) 45, living [] On the left 0
3 [0,22.5) [45] 22.5, right 1
4 [22.5, 33.75) [45] 33.75, right 1
5 [33.75, 39.375) [45] 39.375, right 1

After obtaining the n-bit code values of longitude and latitude respectively, how can they be combined into one code value? The rule is: the length of the final encoding value is 2N, where the even digits are the encoding value of longitude in turn, and the odd digits are the encoding value of latitude in turn (counting from 0, 0 is even), as shown in the diagram below:

After using GeoHash encoding, latitude and longitude [120,40] is encoded as 1110011101, which can be used as the score value corresponding to the key.

As can be seen from the above process, in the process of dividing the interval, we actually divide the whole space into small squares one by one. If you double partition longitude and latitude, you get four. These four partitions correspond to four squares, each of which covers a certain range of latitude and longitude. The more partitions, the smaller and more accurate the geographical space each square can cover. When we map the coding values of all squares to one-dimensional space, the GeoHash coding values of adjacent squares are basically similar, as shown in the figure below:

Therefore, we use Sorted Set range query to obtain similar coding values, which are also adjacent squares in actual geographical space, which can realize the function of “search for people or things nearby” in LBS application.

However, some coded values are close in size, but the actual corresponding squares are far apart. For example, we use 4-bit GeoHash encoding to divide the longitude interval [-180,180] and latitude interval [-90,90] into 4 partitions respectively, with a total of 16 partitions corresponding to 16 squares. The two squares with code values of 0111 and 1000 are far away from each other, as shown in the figure below:

Therefore, in order to avoid the problem of inaccurate query, we can query 4 or 8 squares around the grid with a given latitude and longitude at the same time.

Here we understand the principle of Redis GEO. Through GeoHash coding, we encode the longitude and latitude corresponding to the element, and then store the element ID as the key and the encoding value as the score value into the Sorted Set. Finally, we can complete our initial requirements through the range query of the Sorted Set. Let’s take a look at the Redis GEO command.

GEOADD

Version available: >= 3.2.0

Time complexity: For each element to be added, the time complexity is O(log(N)), where N is the number of existing elements

Version change: NX, XX, and CH parameters are added after version 6.2.0

The command format

GEOADD key [NX|XX] [CH] longitude latitude member [longitude latitude member ...]
Copy the code

Command description

  • Add the specified spatial elements (longitude, latitude, element name) to the Sorted Set corresponding to the key, and the GeoHash encoding converts latitude and longitude to 52-bit values
  • The argument format of this command is fixed, namely (longitude latitude member), and the longitude precedes the latitude
  • GEOADDCoordinates are finite: regions very close to the poles cannot be indexed. Coordinates are limited by EPSG:900913 / EPSG:3785 / OSGEO:41001 specification, legal values are as follows:
    • The effective longitude is between -180 degrees and 180 degrees
    • The effective latitude ranges from -85.05112878 degrees to 85.05112878 degrees
  • Error is returned when the given latitude and longitude is outside the above legal range
  • Redis GEO does not delete the GEODEL command because the underlying Sorted Set is used, so it can be removed using the ZREM command

Optional parameters

  • XX: Updates only existing elements and does not add new elements
  • NX: Only new elements are added, no existing elements are updated
  • CH: Logic to change the return value of a command (CH is short for change). By default, this command returns the number of new elements to be added, and does not update existing elements. However, if the CH parameter is used, the command returns the number of elements changed, including the number of new elements added + the number of existing elements updated

The return value

Default: Returns the number of new elements

CH parameter: the number of elements to be changed

The sample

127.0.0.1:6379> geoadd city 116.41667 39.91667 beijing  121.43333 34.50000 shanghai 117.20000 39.13333 tianjin
(integer) 3

127.0.0.1:6379> geoadd city NX 116.41667 39.91667 beijing
(integer) 0

Copy the code

GEOPOS

Version available: >= 3.2.0

Time complexity: O(N), where N is the given number of elements

The command format

GEOPOS key member [member ...]
Copy the code

Command description

  • Returns the latitude and longitude of the given element
  • Elements added using GEOADD are converted to 52-bit values by GeoHash, so when you extract values using GEOPOS and convert them to latitude and longitude, they may differ slightly from the added latitude and longitude values
  • The command takes multiple mutable arguments and always returns an array value

The return value

Array: Latitude and longitude are returned for existing elements, nil for non-existing elements

The sample

127.0.0.1:6379> Geoadd City 116.41667 39.91667 Beijing 121.43333 34.50000 Shanghai 117.20000 39.13333 tianjin (integer) Geopos City Beijing Nanjing 1) 1) "116.41667157411575317" 2) "39.91667095273589183" 2) (nil)Copy the code

GEODIST

Version available: >= 3.2.0

Time complexity: O(log(N))

The command format

GEODIST key member1 member2 [m|km|ft|mi]
Copy the code

Command description

  • Returns the distance between two given elements
  • The distance metric supports the following parameters:
    • M: meter (default)
    • Km: km
    • Ft: feet
    • Mi: miles
  • The distance calculation assumes that the Earth is perfectly spherical, which results in an error of up to 0.5% in extreme cases
  • Returns nil if any element of a given element does not exist

The return value

String: the distance of a double precision, returned as a string; If one of the elements does not exist, return nil

The sample

127.0.0.1:6379> geoadd city 116.41667 39.91667 beijing  121.43333 34.50000 shanghai 117.20000 39.13333 tianjin
(integer) 3

127.0.0.1:6379> geodist city beijing shanghai
"748346.9287"
127.0.0.1:6379> geodist city beijing shanghai km
"748.3469"
Copy the code

GEOHASH

Version available: >= 3.2.0

Time complexity: For each element, the time complexity is O(log(N)), where N is the number of existing elements

The command format

GEOHASH key member [member ...]
Copy the code

Command description

  • The GEOADD command encodes latitude and longitude to 52bit and returns the converted GeoHash11Bit string representation, the string form, andwikipediaDescription consistent and compatiblegeohash.orgspecification
  • Using the URL: geohash.org/, you can reverse resolve the latitude and longitude of the 11-bit string returned by the command, such as geohash.org/sqdtr74hy01…

The return value

Array: Returns a string representation of the GeoHash encoded value for a given element

The sample

127.0.0.1:6379> geoadd city 15.08723 37.50265 test
(integer) 1

127.0.0.1:6379> geohash city test
1) "sqdtr74hvb0"
Copy the code

Based on the string “sqdtr74hvB0” returned by the example, go to the page and query. The latitude and longitude obtained are only slightly different from the added latitude and longitude.

GEORADIUS

Version available: >= 3.2.0

Time complexity: O(N+log(M)), where N is the number of elements in the specified range and M is the number of elements

Version change: deprecated in version 6.2.0. Consider using the GEOSEARCH and GEOSEARCHSTORE commands

The command format

GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count [ANY]] [ASC|DESC] [STORE key] [STOREDIST key]
Copy the code

Command description

  • By a given latitude and longitude (longitude.latitude) and radius (radius) returns a circular region and returns the elements within the region
  • Simply put, this is to query the elements within a certain distance of the specified location, such as to query the bank within 5 kilometers of the current location
  • The units of radius are as follows:
    • M: m
    • Km: km
    • Ft: feet
    • Mi: miles

Optional parameters

  1. Additional information
  • WITHDIST: Returns the element along with the distance from the specified latitude and longitude, in the same units as given above
  • WITHCOORD: Also returns latitude and longitude information for the element
  • WITHHASH: Returns the Geohash value
  1. The command returns an unordered result set by default. You can use the following two arguments to return ordered data:
  • ASC: Order from near to far from a given latitude and longitude
  • DESC: Order from far to near to a given latitude and longitude
  1. The command returns all qualified elements by default, and can also passCOUNT countSpecifies the number of elements to return

ANY:

  • With this optional parameter, the command does not get all results at query time, but only during the processcountSo the final closest or farthest element may not be included in the result set;
  • If this optional parameter is not used, all results are obtained, sorted, and the first count is returned. Therefore, if the scope of the query is large, even if fewer elements are returned, the performance of the service will be affected.
  1. The command returns only data by default. If you want to save the result, you can use the following two parameters:

  • STORE: Saves the result to the Sorted Set corresponding to the key. STORE is the GeoHash value

  • STOREDIST: Saves the result to the Sorted Set corresponding to the key. Store is the distance and the unit is the same as the given one

    Note: WITHDIST, WITHCOORD, and WITHHASH cannot be used when the above two parameters are used

The return value

Array:

  • When no optional argument is provided: returns a list of elements, such as [“New York”,”Milan”,”Paris”]
  • When provided with optional arguments: Returns an array of arrays, each subarray representing one element of information. The first value of each element information is name, followed by distance, GeoHash encoding, longitude and latitude. For example, GEORADIUS Sicily 15 37 200 km WITHCOORD WITHDIST, even if WITHCOORD is first, it will be in the later position in the return result:
[" Palermo ", "190.4424", [" 13.361389338970184 ", "38.115556395496299"]]Copy the code

The sample

127.0.0.1:6379> geoadd city 116.408 39.904 beijing
(integer) 1
127.0.0.1:6379> geoadd city 116.298 39.959 haidian
(integer) 1
127.0.0.1:6379> geoadd city 116.443 39.922 chaoyang
(integer) 1
127.0.0.1:6379> geoadd city 121.445 31.213 shanghai
(integer) 1
127.0.0.1:6379> geoadd city 121.23 31.07 minhang
(integer) 1
127.0.0.1:6379> geoadd city 117.246 39.117 tianjin
(integer) 1


# withdist
127.0.0.1:6379> GEORADIUS city 116 40 100 km withdist
1) 1) "haidian"
   2) "25.8046"
2) 1) "beijing"
   2) "36.3898"
3) 1) "chaoyang"
   2) "38.7507"

# withdist withhash withcoord127.0.0.1:6379> GEORADIUS City 116 40 100 km Withdist WithHash withcoord 1) 1) "haidian" 2) "25.8046" 3) (integer) 4) 1) "116.29799991846084595" 2) "39.95900079609685207" 2) 1) "Beijing" 2) "36.3898" 3) (INTEGER) 1) "116.40800267457962036" 2) "39.90399988166036138" 3) 1) "38.7507" 3) 2) "39.92199893661282317" 
# DESC127.0.1:6379 > GEORADIUS City 116 40 100 km WithDist DESC 1) 1) "38.7507" 2) 1) "Beijing" 2) "36.3898" 3) 1) "haidian" 2) "25.8046"
#Provided the any parameter, the two elements are returned randomly and sorted, and you can see that the result is not dramatic
127.0.0.1:6379> GEORADIUS city 116 40 100 km withdist COUNT 2 any desc
1) 1) "beijing"
   2) "36.3898"
2) 1) "haidian"
   2) "25.8046"

#Without any, the first two sorted elements are returned
127.0.0.1:6379> GEORADIUS city 116 40 100 km withdist COUNT 2  desc
1) 1) "chaoyang"
   2) "38.7507"
2) 1) "beijing"
   2) "36.3898"
   
#Using Store, you save the GeoHash by default127.0.0.1:6379> GEORADIUS city 116 40 100 km store city_res (integer) 3 127.0.0.1:6379> zrange city_res 0-1 withscores 1) "haidian" 2) "4069880423958265" 3) "beijing" 4) "4069885369376452" 5) "chaoyang" 6) "4069885695970869"
#Storedist, save the distance127.0.0.1:6379> GEORADIUS City 116 40 100 km storedist city_res (integer) 3 127.0.0.1:6379> zrange city_res 0-1 Withscores 1) "haidian" 2) "25.80461312279574" 3) "Beijing" 4) "36.389782386698734" 5) "chaoyang" 6) "38.750694603755257"Copy the code

GEORADIUSBYMEMBER

Version available: >= 3.2.0

Time complexity: O(N+log(M)), where N is the number of elements in the specified range and M is the number of elements

Version change: deprecated in version 6.2.0. Consider using the GEOSEARCH and GEOSEARCHSTORE commands

The command format

GEORADIUSBYMEMBER key member radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count [ANY]] [ASC|DESC] [STORE key] [STOREDIST key]
Copy the code

Command description

  • The command andGEORADIUSThe commands are basically the same, with the only difference:GEORADIUSBYMEMBERGiven an element in the Sorted Set, andGEORADIUSThey’re given latitude and longitude. Given the element, you can actually get the latitude and longitude of the storage, and then query it.

The sample

127.0.0.1:6379> Geoadd City 116.408 39.904 Beijing 116.298 39.959 Haidian 116.443 39.922 Chaoyang 121.445 31.213 Shanghai 121.23 31.07 Minhang 117.246 39.117 tianjin (INTEGER) 6 127.0.0.1:6379> GEORADIUSBYMEMBER City Beijing 500 km Withdist ASC 1) 1) "Beijing" 2) "0.0000" 2) 1) "3.5948" 3) 1) "haidian" 2) "11.2004" 4) 1) "Tianjin" 2) "113.2837"Copy the code

GEOSEARCH

Version available: >= 6.2.0

Time complexity: O(N+log(M))

The command format

GEOSEARCH key [FROMMEMBER member] [FROMLONLAT longitude latitude] [BYRADIUS radius m|km|ft|mi] [BYBOX width height m|km|ft|mi] [ASC|DESC] [COUNT count [ANY]] [WITHCOORD] [WITHDIST] [WITHHASH]
Copy the code

Command description

  • This command is a combination of GEORADIUS and GEORADIUSBYMEMBER, while providing additional functionality. The whole idea is to return elements within a range of a given location.

Will choose parameters

The central point of the query is specified using the following mandatory parameters:

  • FROMMEMBER: Specifies the element
  • FROMLONLAT: Specify latitude and longitude

The range shape of the query is specified with the following mandatory parameters:

  • BYRADIUS: indicates a circular area. The radius is specified BYRADIUS
  • BYBOX: rectangular area, specifying width and length by width and height

Optional parameters

  1. Additional information
  • WITHDIST: Returns the element along with the distance from the specified latitude and longitude, in the same units as given above
  • WITHCOORD: Also returns latitude and longitude information for the element
  • WITHHASH: Returns the Geohash value
  1. The command returns an unordered result set by default. You can use the following two arguments to return ordered data:
  • ASC: Order from near to far from a given latitude and longitude
  • DESC: Order from far to near to a given latitude and longitude

By default, the COUNT COUNT command returns all elements that meet the criteria. You can also specify the number of elements to return by using COUNT COUNT

ANY:

  • With this optional parameter, the command does not get all results at query time, but only during the processcountSo the final closest or farthest element may not be included in the result set;
  • If this optional parameter is not used, all results are obtained, sorted, and the first count is returned. Therefore, if the scope of the query is large, even if fewer elements are returned, the performance of the service will be affected.

The return value

Array:

  • When no optional argument is provided: returns a list of elements, such as [“New York”,”Milan”,”Paris”]
  • When provided with an optional argument: Returns an array of arrays, where each subarray represents one element of information. The first value of each subarray is name, followed by distance, GeoHash encoding, longitude and latitude. For example, GEORADIUS Sicily 15 37 200 km WITHCOORD WITHDIST, even if WITHCOORD is first, it will be in the later position in the return result:
[" Palermo ", "190.4424", [" 13.361389338970184 ", "38.115556395496299"]]Copy the code

The sample

127.0.0.1:6379> GEOADD Sicily 13.361389 38.115556 "Palermo" 15.087269 37.502669 "Catania" (integer) 2 127.0.0.1:6379> GEOADD Sicily 12.758489 38.788135 "edge1" 17.241510 38.788135 "edge2" (integer) 2 127.0.0.1:6379> GEOSEARCH Sicily 12.758489 38.788135 "edge1" 17.241510 38.788135 "edge2" (integer) 2 127.0.0.1:6379 FROMLONLAT 15 37 BYRADIUS 200 km ASC 1) "Catania" 2) "Palermo" 127.0.0.1:6379> GEOSEARCH Sicily FROMLONLAT 15 37 BYBOX 400 400 km ASC WITHCOORD WITHDIST 1) 1) 1) "Catania" 2) "56.4413" 3) 1) "15.08726745843887329" 2) "37.50266842333162032" 2) 1) "Palermo" 2) "190.4424" 3) 1) "13.36138933897018433" 2) "38.115556349629859 "3) 1) "edge2" 2) "279.7403" 3) 1) "Palermo" 2) "190.4424" 3) 1) "Palermo" "17.24151045083999634" 2) "4) 1) "edge1" 2) "279.7405" 3) 1) "12.7584877610206604" "38.78813451624225195" 127.0.0.1:6379 >Copy the code

GEOSEARCHSTORE

Version available: >= 6.2.0

Time complexity: O(N+log(M))

The command format

GEOSEARCHSTORE destination source [FROMMEMBER member] [FROMLONLAT longitude latitude] [BYRADIUS radius m|km|ft|mi] [BYBOX width height m|km|ft|mi] [ASC|DESC] [COUNT count [ANY]] [STOREDIST]
Copy the code

Command description

  • The command andGEOSEARCHThe commands are basically the same, with the only difference:GEOSEARCHIs to return the result directly, andGEOSEARCHSTOREThe result can be saved to a given keydestinationIn the.
  • The default command saves the GeoHash value of the location represented, specifiedSTOREDISTParameter, save the distance information.

The sample

127.0.0.1:6379> GEOADD Sicily 13.361389 38.115556 "Palermo" 15.087269 37.502669 "Catania"
(integer) 2
127.0.0.1:6379> GEOADD Sicily 12.758489 38.788135 "edge1" 17.241510 38.788135 "edge2"
(integer) 2

#Query, return only results
127.0.0.1:6379> GEOSEARCH Sicily FROMLONLAT 15 37 BYRADIUS 200 km ASC withhash
1) 1) "Catania"
   2) (integer) 3479447370796909
2) 1) "Palermo"
   2) (integer) 3479099956230698

#Save the query result to Sicily_des, with geohash saved by default
127.0.0.1:6379> GEOSEARCHSTORE Sicily_des Sicily FROMLONLAT 15 37 BYRADIUS 200 km ASC
(integer) 2

#Traverse Sicily_des127.0.0.1:6379> zrange Sicily_des 0-1 withscores 1) "Palermo" 2) "Catania" 3) "Catania" 4)"
#Save distance information127.0.0.1:6379> GEOSEARCHSTORE Sicily_des Sicily FROMLONLAT 15 37 BYRADIUS 200 km ASC STOREDIST (integer) 2 127.0.0.1:6379> zrange Sicily_des 0-1 withscores 1) "Catania" 2) "56.441257870158204" 3) "Palermo" 4) "190.44242984775784"Copy the code

conclusion

This article introduces the basic principles of Redis GEO and related instructions:

Principle: Encoding rules for GeoHash

Command:

  • GEOADD: Adds the specified latitude and longitude element
  • GEOPOS: Queries the latitude and longitude of a given element
  • GEODIST: Queries the distance between two given elements
  • GEOHASH: Returns the encoded string representation of the GEOHASH
  • GEORADIUS: Returns elements within a given radius centered on the specified latitude and longitude
  • GEORADIUSBYMEMBER: Returns elements within the given radius with the specified element as the center
  • GEOSEARCH: Integration of GEORADIUS and GEORADIUSBYMEMBER, while providing rectangular area range queries
  • GEORADIUSBYMEMBER: Consistent with the GEOSEARCH function, provides the ability to save results

More and more

Personal blog: lifelmy.github. IO /

Wechat official account: Long Coding road