Ads
Comments 69
+9
Ога. Только вместо строкового поля с Id тайла лучше привести к числовому (каждый уровень будет занимать по 2 бита в нём).

В результате можем во-первых строить кластерный индекс, во-вторых индексация int явно дешевле, нежели индексация string, в-третьих поиск a < x < b тоже явно дешевле, нежели поиск LIKE '132023231%'
0
Один из вариантов рассматривался.
С учетом максимального уровня маштабирования в 32 можно до 64 бит «упаковать» все.
Как появится чуть больше свободного времени хочу погонять sql тестами: интересны сравнения скорости + жду, когда заказчик сайта наполнит базу реальными данными.
0
Ога. Даже упаковка обеих координат в 32 бита даёт в итоге точность на уровне сантиметров (точно сейчас уже не помню, когда делал — считал), чего для большинства применений более чем достаточно.
+1
У яндекса «максималка» в координатах 6 знаков после запятой — идеально.
Проблема в том, что в qtree sql проходит по дереву и делает выборку всех индексов записей оптом
В случае со сравнением мы получаем фулскан как бы не упаковывали данные (что int, что float — разница незаметна)
0
не фуллскан, а рэндж скан, что в случае с индексом — быстро, а в случае с кластерным индексом — моментально.
0
То ли я вас не понимаю, то ли вы меня.
SQL база ни про какой qtree знать ничего не знает, хоть в строковом виде, хоть в бинарном. Исключение — PostGIS и прочие geo-ориентированные базы со специальными типами.
В вашей реализации мы имеем поиск по строковому индексу, что по сути выливается в range scan по индексу, а далее вытаскивание строк, на которые ссылаются вытащенные записи индекса.
В моей реализации с обычным индексом поиск выливается в такой же точно range scan по индексу, с той лишь разницей, что бинарное сравнение быстрее, чем символьное.
В моей реализации с кластерным индексом — range scan идёт напрямую по строкам, предварительный скан индекса не нужен вообще, что ещё быстрее.
0
Двоичное дерево есть в sql. В данном случае поиск подстроки в строке в первого символа — наш случай.
0
А на инсерт с обновлением индексов разница нет? Это тоже важно.
0
Давайте поподробнее:
у нас есть координаты 10.211111, 11.201010
доводим до целого числа, получаем 10211111 и 11201010 (в 32 битное число влезает как раз каждое значение)

мне нужно узнать какие точки входят в зону между:
10.0, 11.0 и 10.3, 11.3

остается запрос: (a < x < b) and (m < y < n)
4 проверки, пусть даже и 32 битных значений

/todo надо тестировать
0
Нет. Вы упорно игнорируете упаковку координат в один qtreeid.
ГРУБО:
из (10.211111; 11.201010) получаем 1101221011101110.
поиск также будет 1101000000000000 < x < 1111039999999999
Это совсем грубо и на пальцах. В реале как минимум перемешиваем биты, а не цифры и границы интервала координат приводим к границам возможных значений выбранного числового типа.
0
Аналогично можно 1101000000000000 < x < 1111039999999999 заменить на бинарную операцию (проверка по маске), если база сию операцию правильно поймёт и погонит по индексу, а не фулл сканом.
В моём случае применялась ESE DB, она на кластерном индексе такого в принципе не понимает, да и там не SQL ни разу.
0
Я вот и пытаюсь понять.
для упрощения возьмем точку в 12 преобразовываем, получаем 0110b=6 (дес)
есть координаты 00 и 22: на выходе получаем 0000 и 1010 (0 и 17 соответственно в десятичной)
проверяем 0<6<17 сошлось

так?
0
5 сек.
добавляю вторую координату
точка 11,12
получаем битовые 0101 и 0110, перемешиваем и получаем 01010110 — так?
0
Нет, 00110110. Чередуйте биты в координатах. Иначе это будет не qtree, а просто тупо склеенные числа.
0
если точка 11, 13, то конечное значение будет 0101b и 0111b, чередуем -> 00110111b = 55d

если координаты границы 0,0 и 11,21: получаем 0d в первом случае и 0101 1001 -> 01100011b = 99d во втором

так?
0
Принципиально так, если проигнорировать тот факт, что у вас на 21d overflow случился :)

И кстати, я только сейчас обратил внимание, как у вас из 11d получается 0101b??? Да и с другими числами аналогично, равно как и предыдущих сообщений.
0
Ух, последний вопросом наконец поставили точку у меня в голове по поводу перемешивания битов.
0
Т.е. вы в итоге поняли суть моего первого сообщения? Я это к тому, что от написанного в посте метод принципиально ничем не отличается (преобразование двумерных координат в id узла qtree и обратно — оно ж базовое, его по-другому не сделать).

Просто мне не понятен был выбор символьного типа для хранения и индексации, вместо простого, более логичного и более быстрого бинарного.
0
Все понял, попытаюсь потестить на больших объемах.
На самом деле были сомнения в верности алгоритма из-за перемешивания битов в случае, когда точка в координатах 10,30 а граница 0,0 и 20, 20.
0
У меня в ESE DB такая адресация работала весьма шустро с загруженным planet.osm. Объём данных > 500 гб.

На sql-базах не пробовал, т.к. они отжирают на хранение и индексы куда больше места, чем я могу им дать :)
+2
Замечание:
LIKE '132023231%' с проиндексированным полем быстрее чем (a < x < b) and (m < y < n)
0
Если это замечание ко мне — то я не предлагаю делать range scan по двум полям, я предлагаю именно по одному.
Координаты переводятся в вид с фиксированной запятой (по сути целые), далее их составляющие биты чередуются (lat1,lon1,lat2,lon2 и т.д.), в результате получаем тот же qtree id, но в целом виде. Из вашего варианта можно получить то же самое, заменив литеры 0, 1, 2 и 3 на соответствующие биты 00, 01, 10, 11. На выходе получите то же самое, но целочисленная арифметика всяко быстрее.

В результате — для выборки точно так же имеем range scan по одному полю.
0
Если строку 01230212312312 упаковывать по 2 бита, то выйдет, что при 21 уровне максимальном у на 42 битное число.
При поиске «подстроки» мы получаем или танцы с битовыми масками или делим число на байты и ищем по полным байтам + сканим найденное по «остатку» в 2/4/6 бит.

Варианты оптимизации?
0
не нужна такая детализация. достаточно 32 бит — это 16-ый зум.
то есть индексируем тайлы до 16 зума. даже если на 18 зуме будет больше точек, их при обработке данных легко исключить.
вот как в php:
конвертите номер тайла в 1313101230130131 (16 зумом)
потом
tileId = base_convert('1313101230130131', 4, 10);
и сохраняете в базе для каждой точкb uint.
выборка точек:
MAX_ZOOM = 16

if ($this->zoom <= Maps2Utils::MAX_ZOOM )
{
$tile_from = base_convert( $this->id. str_repeat('0', Maps2Utils::MAX_ZOOM — $this->zoom), 4, 10);
$tile_to = base_convert($this->id. str_repeat('3', Maps2Utils::MAX_ZOOM — $this->zoom), 4, 10);
} else {
$tile_from = $tile_to = base_convert($this->id, 4, 10);
};

в sql просто BETWEEN $tile_from AND $tile_end
0
Я для iloveukraine.com.ua тоже делал размещение большого кол-ва фотографий на карте, как у Panoramino.
Все никак не выкрою время статью написать об этом.
Спасибо, что напомнили об этой теме, нужно в график воткнуть несколько часов на это дело :)
0
Я, на самом деле, делал все очень просто и практически в лоб:

Один из нюансов — нужно было разбивать карту на секторы по размеру иконки фотогрфии на карте и внутри этого сектора вывести фото с самым высоким рейтингом — т.е. запросы на заполнение секторов получаются не максимально простые и, соответственно, не максимально быстрые.

Я привязывался к координатам тайлов яндекс.карт и для каждого тайла на разных масштабах делелась отдельная выборка с простейшим ln y и т.п.
А затем складывал в кеш по номеру тайла и масштабу. Всё.
В моем случае был обычный кеш (хватало, т.к. охват только страны), если нужно больше (по миру) можно класть в Redis или вообще Tokio/Cabinet или что-то такое супер-быстрое.

Затем при загрузке яндекс.карт вытягиваем масштаб и номера видимых тайлов и запрашиваем. При перемещении кары — дозапрашиваем тайлы, которые проявились.
Практика показала, что работает такой подход очень замечательно. Запросов в базу самый минимум, издержки на получение тайла по номеру — ессно минимальные.
В общем, просто и быстро
0
* хабрапарсер поел стрелочки.

»»отдельная выборка с простейшим ln y и т.п.
в общем, вхождение координат в границы тайла, простым больше-меньше
0
Такой подход имеет один недостаток — у него плохая локальность. Половина возможных значений у вас попадает на юг Южной Америки и южный полюс, где точек явно будут единицы. А мега-кластеры точек — Нью-Йорк, Токио, Лондон и т.п. будут набиты как селедки в бочке в один префикс.
0
Да, есть такое. В конкретном случае будет контроль числа точек по рейтингу с таким расчетом, что бы на карте видимо было не более 1000 точек сразу. При увеличении масштаба новые менее рейтинговые точки проявляться будут, что вполне соответствует потребностям.
0
работаю над браузерной RTS и у меня то-же как-то стала проблема с производительностью и поиском координат.

У меня легче, т.к. нету масштаба, но суть не в этом.

Каждая группа координат (256 ед.) закреплена за чанком. Чтоб не использовать XY для определения позиции, я решил поюзать другую схему.

Каждая координата XY приобретала свой ID, который элементарно высчитывался
sizeMap * Y + X + 1 // Координаты у меня начинаются с 0, а значит и нужен этот +1

Каждый объект закреплен за чанком, т.е. я всегда могу выбрать данные по чанку так и данные по координате, не используя медленные, человеко-понятные координаты XY. А быстрые индексные ID.
Текущий чанк, тоже можно высчитать по координате.

Никаких строк, быстрая выборка. Правда иногда приходиться запрашивать по 9 чанков, но все равно, скоростей хватает, чтоб быстро загрузить нужные данные.
+1
Без масштаба вообще все просто. Если карта имеет размер 255х255 тайлов (хотя не принципиально), то вообще в 2 байта можно запихнуть данный о принадлежности точки тайлу/чанку. Тогда индексация по 1-му полю и выборки where chankMap=48192 типа такого выходит. Мгновенные выборки.
0
А если это еще подкрепить кэшированием (redis, memcache) то это будет работать как молния.

Но если продолжить идею, то по сути, на разных масштабах, могут быть разные чанки, да распрощаемся мы с нормализацией в этом месте, но получим плюшку в скорости. Т.е. на каждый масштаб, будет свой чанк, но идея сыра, нужно проворачивать ее сначала на бумаге, даб увидеть слабые места.
0
Если начинаете работать с масштабами, то qtree — без вариантов.
0
qtree механизм структуризации данных в основе которого могут лежать и чанки.
0
а с учетом того, что к точке может быть добавлен «балун» с текстовой информацией, то и мегабайты

это явно лишнее. вытягивайте контент балунов аяксом

ну и неплохо, если размер тайла карты совпадает с размером вашего тайла. оно хоть и не несет каких-то дополнительных преимуществ, но как-то фэншуйнее
0
В данном случае тайлы карты совпадают с тайлами «нашими».
С текстовой информацией — несомненно при больших объемах тянуть текст глупо.
0
при любых объемах этот текст гонять глупо, как по мне. ну не будет пользователь кликать на все объекты подряд. если и будет, то либо этот пользователь будет один из многих тысяч, либо объект на карте — один единственный)

а насчет тайлов — извините за неуместное замечание, но из формулировки «вычислять номера диагональных тайлов» не совсем ясно какая логика кроется за этим вычислением. либо же своя какая-то, исходя из масштаба и плотности объектов и (или) иных размышлений, либо же просто номера тайлов карты.
0
В случае с текстом — мы как раз имеем случай когда пользователь будет тыкать на точки постоянно (точки популярных туристических мест)

А с тайлами — не принципиально, совпадает ли размер с картами или нет, особенно если тайлы считать по координатам, а не перехватывать загрузку картинок тайлов самой карты (кстати на Хабре есть пара людей, кто описывали данный способ)
0
Судя по завлекалочке вы агрегируете точки в групповые.
Так вот вопрос — где вы их агрегируете — на клиенте или заранее, по уровням зума?
+1
Очень странное решение, в такой ситуации лучше использовать postgresql + postgis или mongodb с geospatial. Там есть индексы по координатам и возможность быстрого поиска объектов в области координат.
Да и с 2 млн. точек «дешевле» будет делать кластеризацию на сервере и кешировать.
Как-то немного переоптимизировав в одном проекте перенесли генерацию кластеров на тригеры в postgre. Работало очень шустро =)
0
К монго у меня отношщение пока скептическое. На тестовых машинах стояла, падало в неожиданных моментах, после пары десятков сбоев все резко охладели к монго.
Кластеризация на сервере — имеет свою «цену».
Другие разновидности БД — проблемы на арендованных вирт хостингах, так как точки сделаны модулем к популярному фреймворку и не хотелось бы себя загонять в рамки + переоптимизация излишнеранняя — увеличение цены разработки. Для стартапа это порой убийственно.
0
Обрабатывать 2 млн. точек — задача явно не для шаред хостинга, так что база может быть любая.
Сейчас в одном проекте монго крутится как раз для точек — пока не падала. В ней выборка с кластеризацией сделана через map/reduce, работает быстро и можно сказать — решение в лоб =)

Когда делали с тригерами, там уже можно сказать была переделка, так что время было. Но всё это чудо поддерживать немного проблематично.
0
Если можно сделать быстрой работу с 10 тыс точками на простом вирт хосте, то это решение сгодится для почти всех сайтов клиентов: карта розничных точек, работа со слежением за транспортом, карта аренды квартир.
0
почитайте тут.
habrahabr.ru/post/145832/

У меня все 10000 точек на клиенте лежат.
и кластеризуются.

мдя, я думал Вы что-то новое предложите. а у Вас… в квартре газ.
0
К моему методу добавить разделение по уровням масштабирования с кластеризацией на уровне сервера и будет еще быстрее (клиентская часть кластеризатора все же тормозит)
0
проблема с серверной кластеризацией в слипании точек/кластеров по краям тайла.
в лубом случае, 10 точек на клиенте по-любому быстрее, чем постоянная закачка данных с сервера.
0
Тут надо еще смотреть на 2 вещи:
1. минимальный масштаб (есть пара сервисов, где ограничено минимумом в 10-12)
2. сколько всего точек и как они сгруппированы. На 2 млн точек карта «тупит» на ноутбуке около 7-8- секунд, если весь мир показать, если ограничить масштабом в 3-5, то около секунды на обновление карты (включая кластеризацию на js)

Вообще есть куда ускорятся как на стороне сервера, так и у клиента.
0
на масштабах 0-6 можно сделать хитро. делать выборку на масштабе +3 например.
то есть на 0 масштабе сделать выборку по тайлам на масштабе 3, но выбирать не все, а, скажем, 100 новых. получится максимум 6400 объектов. вот их-то и кластеризовать.
смысл в том, что если выбрать на 0 зуме последние 6400 объектов, если большая вероятность, что большинство из них будет в одной части карты (например, в мск) — некрасиво.
другой вариант — каждой точке давать поле с рэндомным значением при сохранении и выбирать по этому полю limit 6400. рэндом ещенощно обновлять.
0
Я склоняюсь к мысли, что при 26-32 уровнях масштабирования сделать пару «слоев» с кластерами на уровне 6 и 18. т.е. на этих уровнях точек не оставлять, а группировать все в кластеры (одиночные точки тоже кластером делать). Кластеры только группировать не по сетке, а по плотности. Муторно, но при нулевом масштабе у нас вылезет около 4-5 тыс кластеров (что многовато и я бы радиус кластера увеличил), что уже супер и быстро будет обработано, а при 7-м уровне мы увидим кластеров уже в районе 60 тыс, то так как мы смотрим уже на карту не всю, а только часть, то при показе карты в ширину 960px и высоту около 300px получим около пары тыс кластеров, что опять же быстро будет обработанно (кластеризатор на стороне клиента удаляем за ненадобностью). При показе масштаба уже более 19-го, возможно стоит кластеризатор включить.
0
Вы забываете одну очень важную вещь — юзабилити.
Каждый ненужный щелчок по карте (на кластер) увеличивает процент отказов вдвое.
так что с 4 до 18 зума у Вас вряд ли кто доберется. если у Вас не останется точек, а будут одни кластеры, юзер плюнет и закроет страницу.
так что подумайте насчет 2000 кластеров. Для специальных сайтов типа недвижимости это еще сработает (там люди знают, что ищут), а для развлекательных — лучше меньше да лучше)
кстати, я работаю с картами уже года 4, как раз учился у kashey лично.
обратитесь к профессионалам, не изобретайте велосипед.
0
1. карта карте рознь
2. все полезно в меру
3. 1 кластер намного лучше чем 120 тыс точек стоящих друг на друге.
0
Был вариант вообще координаты точек приводить к 16-32 битному числу и оба значения «слепливать» в 32-64 битное число.
При этом возникали трудности с маштабированием, но они решались тем, что при добавлении точки на каждый уровень масштабирования готовилась бы свой группа чисел.
фактически поиск осуществлялся бы по составному индексу: «индекс» координат + уровень масштабирования. Или если по разным полям разделить, то еще проще.
0
у постгреса с монго тоже есть, но это не приоритетные куски БД, как правило привязанные к определенным типам сферических координат и т.д., лучше делать реализацию под проект, это несложно.
+1
Давайте по порядку
1. Wikimapia.org — первый известный мне сайт где используется уже очень много лет такая технология запроса данных
2. github.com/theKashey/quadLoader — пример простой и правильной реализации загрузчика
3. В первый раз на хабре я (хренова) описал технологию года 4 назад, года два назад еще раз попробовал. Потом уже рассказывал голосом. Расказывал разные интересности, например что не надо в гео координатах данных аксесить… ymapsapi.ya.ru/replies.xml?item_no=350 ( лучше с CodeFest — звук лучше, времени было больше )
4. Заходя в этот топик я ожидал узнать как такие красивые полосатые кластера отрисовывать( кстати этому помогают запросы в пиксельных координатах, почему? )
0
Начальное изучение мною карт началось с Ваших статей :)

С кластеризатором все проще чем кажется: стандартный гугловский.
0
Ага Кащей всех на харбе картами заразил:). Когда у меня будет мноооого кармы, тоже на пишу «как это было»
0
Подтверждаю 4 года назад описывал как грузить по гуглотайлам. Подозреваю технологии немного изменились.
Only those users with full accounts are able to leave comments.  , please.