For example if you have a set of calendar invites with a start and stop time (say tens of millions of them) and you want to find all invites which span 12pm (that is start before 12 and end after 12) you want an interval tree.
In my recent experience working with collections containing million of documents, each containing a geoJSON-style polygon/multipolygon representing a property (i.e. a block of land), I found invalid geometries to occur for about 1 document in 1 million. For a while, I suspected the data-vendor was the cause, however it became more puzzling when other geospatial software confirmed they were valid. Eventually we traced the issue to the 2d-sphere index.
A very clever workaround was suggested by a colleague of mine, inspired by [1]. It preserved the original geometries. In each document, we added a new field containing the geometry's extent. A 2d-sphere index was then built on the extent field instead of the original geometry field. Invalid geometries were no longer an issue since we were dealing with much simpler geometries that were substantially larger than the max precision of the index.
When running geoIntersects queries on our collection of millions of documents, we did so in 2 steps (aggregation queries):
1. GeoIntersects on the extent field (uses the index).
2. On the result set from the last step, perform geoIntersects on the original geometry field (operates on a much smaller set of records compared to querying the collection directly)
[1] https://www.mongodb.com/docs/manual/tutorial/create-queries-...
A little sleuthing shows that (TIL) they are an application of Z-order curves, which date back to 1906
You could get a single "key" by just having a sequence of bits with most significant bit of x coordinate, most significant bit if of y coordinate, second most significant bit of x coordinate, second most significant bit of y coordinate, third....
Simple explanation:
If you have data with x y coordinates and you know the bounds.
To compute the quad key for a point:
1. The key starts as the empty string. (I've also seen it start with "Z" to handle points outside the bounds)
2. Divide the space into 4 quadrants
3. determine which quadrant the point falls in, append a letter (A-D depending on the quadrant) to the key
4. Repeat step 3 using the quadrant bounds (i.e. recursively smaller area) until you have desired accuracy
This can then be used to efficiently find points within rectangular bounds.