Part 4 of 8 · 2 min read
Geohash
Dividing the map into cells.
All geospatial indexes share one idea: divide the map into smaller areas, and index the areas. They split into two families: hash-based (even grid, geohash) and tree-based (quadtree, Google S2, R-tree).
Even grid. Divide the world into equal squares. Each place belongs to one square. It works somewhat, but places are spread unevenly: a downtown square may hold thousands and an ocean square none. Finding the neighbours of a square is also awkward.
Geohash. Geohash turns a latitude and longitude into a short string of letters and digits. It splits the world in four, by the equator and the prime meridian. Then it splits each part in four again, and so on. At each split it adds a bit: 0 or 1 for the lower or upper half of latitude, and the same for longitude. The bits are written in base 32. Two example strings from the book, each 6 characters long: 9q9hvu and 9q9jhr, for two company headquarters in the same area.
A longer string means a smaller cell. The book's table gives these sizes:
| Length | Cell size |
|---|---|
| 4 | about 39 km by 19.5 km |
| 5 | about 4.9 km by 4.9 km |
| 6 | about 1.2 km by 0.6 km |
Only lengths 4 to 6 matter for search. Shorter cells are too small, and longer are too big. To choose, take the shortest length whose cell still covers the circle of the radius.
| Radius | Geohash length |
|---|---|
| 0.5 km | 6 |
| 1 km or 2 km | 5 |
| 5 km or 20 km | 4 |
A key property: places that share a longer prefix are closer together. So the index table can hold two columns, the geohash and the business id, with one row per place. A search finds the user's geohash at the right length, and reads all rows with that value.
A worked example (made up). A user at 1 km radius gets a length-5 geohash, say 9q8zn. The query reads all rows where geohash is 9q8zn. Rows may be dozens, not millions.
Geohash
A geohash is a short string that names a rectangular cell of the map. A longer string names a smaller cell inside the cell of its shorter prefix.
Example: the cell 9q8zn lies inside the larger cell 9q8z.
Check yourself: 1. What does one more character of a geohash do to the cell? 2. Which length is used for a 2 km radius? 3. What does a shared prefix tell you?