Мне интересно, как работает геопространственный индекс, например, используемый MongoDB. Может ли кто-нибудь объяснить, какая структура данных/алгоритм используется внутри? С какой временной сложностью выполняется поиск?
Ссылки на ресурсы также будут хороши.
В зависимости от типа данных и шаблона использования либо R-Tree, либо вариант (R *, R +) или quadtree или, возможно, даже kd-tree.
В соответствии с этим другим вопросом SO:
Текущая реализация кодирует географические хеш-коды на стандартных MongoDB B-деревья. Результаты $near queries точны. Одно ограничение с этой кодировкой, в то время как быстро, это то, что префиксные поиски не дают точные результаты, особенно в областях бит флип. MongoDB решает эту проблему путем поиска соседей по сетке после первоначального сканирования префикса для выбора до каких-либо отступлений. Это в целом гарантирует, что производительность остается очень высоким, обеспечивая при этом правильные результаты.