Меня спросили об этом на собеседовании. Я хорошо сдал экзамен, но не знал достаточно, чтобы ответить на этот вопрос. Мне любопытно узнать, какие структуры данных я могу использовать для быстрого запроса данных.
По сути, идея заключается в том, что участки дороги (линии, состоящие из точек) хранятся в некоторой структуре данных. Необходимо быстро выяснить, какие участки дороги (или точки) находятся на определенном расстоянии от точки (радиуса).
Ответы:
Типичным способом хранения географических данных является использование пространственной структуры данных, такой как R-дерево (или некоторый вариант, такой как R + дерево, R * дерево и т. Д.). Именно так географические типы данных обычно реализуются в ГИС-совместимых RDBMS. (Я знаю, что и Microsoft SQL Server 2008, и PostGIS используют R-деревья для географических типов.) Они отвечают всем основным требованиям, которые вы описали, и тривиально поддерживают пересечение, местоположение, расстояние и другие типы запросов.
В зависимости от типа данных, вы также можете найти такие вещи, как kD-деревья, quad-деревья, октреи, иерархии ограничивающих томов (включая выровненные по осям ограничивающие прямоугольники) и т. Д. В общем использовании. На самом деле это гораздо более обычное явление в 3D играх, поскольку размер и форма объекта больше подходят для запросов на пересечение. Они реже используются для ГИС, чем R-деревья.
источник
Различные виды операций с данными карты потребуют различных форматов хранения для достижения оптимальных результатов. Рассмотрим, например, следующие три задачи:
Различия в требованиях достаточно велики, так что если вам не нужно будет приспосабливать «живые» изменения к карте, вам, вероятно, будет лучше хранить три отдельных копии данных - каждая оптимизирована для одной из вышеперечисленных задач - чем пытаться придумать формат, который может хорошо справиться со всеми тремя задачами.
источник