Как лучше хранить гео-точки (для последующего отображения на карте)?
Есть необходимость хранить в базе точки (longitude и latitude). Точки привязаны к некоторым другим сущностям (например, точка — филиал магазина).
Нужно придумать способ хранения, чтобы можно было быстро выбирать точки, которые попадают в отображаемый диапазон карты, при этом отфильтровав их по каким-то параметрам (например, тип магазина).
Точек может быть очень много (миллиарды) — нужно как то организовать шардинг.
При этом если отображается вся карта мира целиком — необходимо быстро посчитать примерное количество точек, отфильтрованных по параметрам.
Можно попробовать mongodb. Там есть и географический индекс и шардинг. А вообще набор этих точек часто меняется? И насколько остро стоит вопрос производительности. А то можно и на каждом сервере в память загнать из файла. А также можно разбить их на тайлы и предрасчитать количество точек в каждом тайле. Получится некоторое подобие гиперкуба OLAP.
набор точек меняется часто. думал уже о том чтобы написать мини демона, который будет хранить все точки в памяти.
Если взять расходы по 100байт на точку, то получится 1млрд влезет в 10гб оперативки.
Думал также и об идее разбивать точки на географические квадраты (например по 10 градусов по широте и долготе) и дальше шардить эти квадраты — минус в том что точки неравномерно будут расположены по карте мира и нужно будет хитрым способом определять какие квадраты на какие шарды пихать.
В случае хранения в памяти возможно стоит предусмотреть какие то индексы, чтобы не бегать каждый раз по всей памяти (особенно в случаях когда надо только оценить количество точек, подходящих под критерии поиска). Детально пока не обдумывал этот момент. Но очевидно что из за накладных расходов на индексы — количество хранимых точек в памяти снизится
Индекс в любом случае нужен. Если конечно чтений все-таки больше, чем добавлений. Геометрических индексов существует вагон и маленькая тележка и проблема неравномерности объектов в них решается балансировкой. В частности в деревьях более плотные регионы либо будут иметь больше уровней вложенности (квадродерево), либо меньшие размеры регионов при том же уровне вложенности (rtree). Реализации, я думаю, вы тоже найдете в свободном доступе.
Если изменения частые, я бы стал делать свою реализацию памяти только в крайнем случае. Написать надежное распределеное хранилище — трудная задача. Для начала попробуйте существующеи СУБД с георасширениями и замерьте их производительность. Если устроит — используйте.
Можно PostGIS, как советуют в отдельном ответе. Но в SQL крайне трудно сделать нормальный мультимастер и шардинг. В PostgeSQL и MySQL полноценных реализаций, насколько я знаю, нет. Если нет необходимости в сложных join'ах, то стоит помотреть в сторону nosql баз данных.
Можете попробовать такой подход. habrahabr.ru/post/147744/
Думаю, что даже для миллиардов точек вам подойдет предложенный выше Postgres + Postgis.
Про фильтрацию большого объема данных сошлюсь на другой пост того же автора. habrahabr.ru/post/114113/
Вам лишь стоит объединить эти два подхода, в том числе и в случае использования mongo.
Вместо строк лучше использвоать числа. Будет намного быстрее работать. Но такой способ стоит использовать только если нет возможности поставить расширение с нормальными геоидексами.
Касательно Postgres + Postgis — зависит от требований к системе. Где-то он нужен потому что нужны сложные запросы. А где-то его использовать нельзя из-за определенных требований по нагрузке и отказоустойчивости.
Простой
