Pull to refresh

Comments 11

Красиво. А пробовали индексировать более чем двумерные непрерывные множества? Или в непрямоугольных координатах?
Многомерный поиск (в любых координатах), если он приводит к неравномерности распределения, лучше не пробовать на Igloo. Представьте, что у Вас четыре объекта по углам и миллиард кучкуется в центре. Для того, чтобы найти любой объект из центра придется перебрать их все.
Впрочем, эта ситуация разруливается самоподобными индексами.
А не поможет ли в этом случае комбинирование с RTree?
И комбинировать не надо, поможет.
Но R-дерево оно заметно тяжелее нежели простое B-дерево.
В среднем случае комбинирование поможет сократить overhead от дерева, но оставит выигрыш по скорости. В худшем да, будет тяжелая конструкция, хотя думаю можно при желании упаковать как-нибудь, благо модификаций немало.
Смотря что понимается под комбинированием. Можно хранить два индекса, тогда по B-дереву быстро оценить объем перебора и переключиться на R-дерево. А стоит ли оно того?
Покрыть весь мир решеткой и для каждой ячейки держать свое мини дерево. Таким образом по решетке выбираем нужный набор, а далее по дереву.
Природу не обманешь :) Пусть у нас 1000Х1000 ячеек, большинство из них слабозаполнены — 1..2 объекта, некоторые заполнены сильно. Миллион рутовых страниц R-дерева вынь да положь. Плюс еще адреса этих страниц хранить надо. Да транзакциями всё это покрыть. А честное R-дерево просто достроится там где надо. Но приз моих личных симпатий принадлежит обычному B-дереву с самоподобным ключем. При правильной работе с ним оно и для универсальных данных превосходит R-дерево за счет простоты и компактности.
Но это уже совсем другая история.
Пробовали, но не именно таким методом.
Для небесных объектов лучше всего подошли бы трехмерные координаты (как если бы их нанести на сферу). Тогда нет искажений к полюсам, но сложней задавать поисковый экстент.
Спасибо за пример использования самоподобных кривых!
В принципе, кривая Z-order — это один из вариантов реализации квадродерева.
Only those users with full accounts are able to leave comments. Log in, please.