Geo Index Implementation
This section will cover the MMFiles based geo-index. The algorithm is optimized for in-memory accesses and optimal CPU cache utilization. The main goal for our geo queries is to reject as many distant possible result points as fast as possible.
One limitation of an approach purely using geostrings is, when one is trying to perform a query to find points near a target (see blog post Part I). Sometimes points close together on the surface might end up with entirely different geostring prefixes and cannot be scanned without seeks. We implemented a type of Metric Tree to optimize for nearest neighbor queries.
To consistently achieve fast queries the Hilbert geostrings are combined with a binary search tree, the current implementation chooses an AVL tree structure. Read more